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

Подобные цепочки непрактичны: для реализации данного варианта потребовалось бы 10 одновременно оперирующих хирургов. Операции должны проводиться одновременно, иначе, скажем, как только Кэрол получит почку от Берил, Карл может передумать и отказаться отдавать свою почку Дейдре. Люди не всегда выполняют свои обещания, если теряется выгода, даже после подписания необходимых юридических документов. При желании всегда можно найти предлог. Сказаться больным или еще что-нибудь. Сломать ногу.

Эта цепочка слишком длинная, чтобы быть практичной

По этой причине обмены в настоящее время законодательно ограничиваются четырьмя сценариями: это циклы длины 2 и 3, которые мы уже видели, и соответствующие им циклы с участием донора-альтруиста, которые называются короткими и длинными цепочками. В короткой цепочке были бы задействованы только Зои, Альберт, Амелия и кто-то из списка ожидания. В длинную цепочку были бы включены еще Берил и Бернард. Под обменом понимается любой из этих четырех сценариев.

Обратите внимание на небольшое лукавство. Я показал эту цепочку как цикл с пятью вершинами. При реализации обмена это не совсем так, потому что у Зои нет конкретного реципиента. Зои готова уступить свою почку любому, и в конце цепочки Дайана действительно отдает почку любому (то есть списку ожидания в целом). Но на самом деле «кто угодно», кому уступает почку Зои, оказывается Амелией, и это не тот же самый человек, кому жертвует в конечном итоге последний в цепочке – Дайана. С этим помогает разобраться математика, потому что в каждом случае мы определяем занимающего позицию «кто угодно» из структуры орграфа.

Орграф обмена почками, использовавшийся в июле 2015 года, и оптимальное решение (показано сплошными черными линиями). Белые точки – доноры и реципиенты, не имеющие пары, серые точки – доноры-альтруисты, черные точки – доноры и реципиенты, получившие пару[5]

В приведенных выше орграфах отдельные циклы и цепочки показаны при помощи небольшого числа вершин и стрелок. В реальности пар много, доноров-альтруистов заметно меньше, а вот стрелок просто громадное количество. Это происходит потому, что орграф должен иметь стрелку между двумя любыми вершинами X и Y, где донор X совместим с реципиентом Y. Один и тот же донор может быть совместим со множеством реципиентов. Например, в октябре 2017 года было зарегистрировано 226 неальтруистических пар и 9 доноров-альтруистов, между которыми было проведено в совокупности 5964 стрелки. Рисунок иллюстрирует сложность структуры на другую дату. Математическая задача состоит в том, чтобы найти в этом орграфе не просто один обмен, а наилучшее возможное подмножество обменов.

* * *

Чтобы решить эту задачу математически, необходимо точно определить понятие «наилучший возможный». Это не просто множество обменов, при котором задействовано максимальное число людей. Есть и другие соображения, такие как стоимость и вероятный процент успеха. Здесь в дело вступают медицинская консультация и опыт. Служба переливания крови и трансплантации Министерства здравоохранения Великобритании (NHSBT) разработала стандартную систему количественной оценки пользы от каждой пересадки органа. Во внимание принимаются такие факторы, как срок ожидания пациента в очереди, уровни несовместимости по типу тканей и разница в возрасте между донором и реципиентом. При помощи статистического анализа эти факторы собираются в единую числовую оценку – действительное число, которое называют весом. Вес вычисляется для каждой стрелки на орграфе, то есть для каждой потенциальной пересадки.

Имеется одно очевидное условие: одна и та же вершина графа не может быть задействована в двух цепочках, поскольку невозможно отдать одну и ту же почку двум людям. Математически это равноценно утверждению, что циклы, составляющие множество, не пересекаются. Остальные условия тоньше. Некоторые циклы длины 3 имеют дополнительную полезную черту: лишнюю стрелку в обратном направлении между двумя вершинами. На рисунке показан случай, когда, помимо стрелок предыдущего цикла длины 3, в цикле имеется еще одна от пары Берил к паре Амелии. Это означает, что Берил совместима не только с Кэрол, но и с Амелией. Если где-то на поздней стадии Карл вдруг выпадет из договоренности по обмену, то Кэрол тоже можно исключить; останется цикл длины 2, в котором Альберт передает почку Бернарду, а Берил – Амелии, и этот обмен по-прежнему может быть реализован. Математически эти три вершины образуют цикл длины 3, и дополнительно две из его вершин образуют цикл длины 2. Подобная дополнительная стрелка называется обратной дугой. Любой цикл длины 3 с обратной дугой и циклом длины 2 называется эффективным циклом длины 2.

Согласно определению Консультативной группы по почкам при NHSBT, множество обменов почками является оптимальным, если оно:

(1) максимизирует число эффективных циклов длины 2;

(2) содержит как можно больше циклов, при выполнении условия (1);

(3) использует как можно меньше циклов длины 3, при выполнении условий (1) и (2);