Это база: Зачем нужна математика в повседневной жизни

Главное здесь, конечно, не имена, а типы тканей. Альберт – это кто угодно с тем же типом ткани, что у Зои. Берил – это кто угодно с тем же типом ткани, что у донора Альберта; Карл – это кто угодно с тем же типом ткани, что у донора Берил, и т. д. При разумном числе реципиентов и доноров подобные цепочки обычны, и хирурги могут их заметить. Однако это требует времени, даже если поиском цепочек занимается специальный человек, а каждая почка драгоценна, поэтому имеет смысл выбирать цепочки наилучшим возможным способом. Это сложно, поскольку одновременно может существовать несколько потенциальных цепочек. В таком случае хирурги могут начать работу одновременно, если только в их цепочки не входит один и тот же донор, на почку которого будут претендовать два человека. В этой ситуации одна из цепочек рвется.

Оптимизировать выбор цепочек… Это звучит математически. Если вы сможете сформулировать задачу математически и применить подходящие методы, то, возможно, сумеете и решить ее. Более того, решение не обязано быть идеальным. Оно может быть всего лишь лучше, чем результат, полученный вручную. Дэвид Мэнлав нашел способ превратить задачу об обмене почками в вопрос о графах. Теорема Эйлера здесь не помощница, но роль Эйлера неоценима, поскольку он открыл в математике новую область. За прошедшие годы математики развили тему и нашли в теории графов множество новых методов. Поскольку граф – объект дискретный, «на самом деле» всего лишь список вершин, ребер и информации о том, какое ребро соединяет какие вершины, графы замечательно подходят для компьютерной обработки. Разработаны мощные алгоритмы для анализа графов и извлечения из них полезной структуры. В их числе есть и алгоритмы, которые могут отыскивать оптимальные способы распределения доноров по пациентам для графов приемлемых размеров. Эти методы, реализованные на компьютере, применяются сегодня в Великобритании на повседневной основе.

* * *

Два типа обмена

Совместимые пары доноров и реципиентов просто обмениваются почками. Для этого нужно, чтобы два хирурга оперировали одновременно, каждый своего пациента. Так что мы, пытаясь собрать цепочки, можем не обращать внимания на совместимые пары и сосредоточиться только на несовместимых. Эти пары составляют вершины графа.

Предположим, например, что Альберт готов отдать свою почку Амелии, но совместим при этом с Бернардом. Эта ситуация показана на рисунке слева. Я ставлю имя донора вверху, а имя несовместимого с ним родственника – внизу. Стрелка означает, что «донор в ее хвосте совместим с реципиентом на острие». Этот рисунок представляет собой особый тип графа, в котором ребра имеют конкретную направленность. В отличие от мостов Кёнигсберга, эти ребра односторонние: математики называют их направленными, а получившийся граф – ориентированным или, короче, орграфом. На рисунке направленные ребра обозначены стрелками.

Если Берил совместима с Амелией, то правила предписывают нам нарисовать еще одну стрелку в обратном направлении. Таким образом создается двусторонняя связь, как на рисунке справа. Этот рисунок иллюстрирует простейший вариант обмена почками, который специалисты по теории графов называют циклом длины 2. Хирурги могут предложить Альберту пожертвовал свою почку Бернарду с условием, что Берил отдаст свою Амелии. Если все стороны согласны, то Амелия и Бернард получают по новой почке, тогда как Альберт и Берил по одной почке отдают. Хотя это и не родственная пересадка, реципиенты все-таки получают почку, так что большинство потенциальных доноров принимают обмен такого рода.

Цикл обмена почками длины 3

Следующий, более сложный тип обмена – цикл длины 3. Здесь присутствует третья пара с донором Карлом и реципиентом Кэрол. Предположим, что

Альберт совместим с Бернардом;
Берил совместима с Кэрол;
Карл совместим с Амелией.

Тогда хирурги могут предложить, чтобы почка Альберта досталась Бернарду, почка Берил – Кэрол, а почка Карла – Амелии. Это опять приемлемый вариант для большинства доноров.

С донорами-альтруистами вроде Зои работать приходится немного иначе, потому что они изначально ни с кем не связаны и у них нет пары. И здесь на сцену выходит небольшой математический фокус. Мы формируем соответствующую вершину графа, поставив в пару к Зои загадочного неизвестного реципиента, обозначив его подписью «кто угодно», и считаем этого реципиента совместимым с любым из наших неальтруистических доноров. На практике этот псевдореципиент представляет всех стоящих в списке ожидания при условии, что каждый из них совместим с кем-то из неальтруистических доноров. Это вполне реально, поскольку список ожидания велик. Теперь мы проводим стрелку от

вершины-Z = (Зои, кто угодно)

к любой вершине, реципиент которой совместим с Зои. Для последовательной цепочки домино, описанной выше, получаем орграф на рисунке ниже.