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

Не позволяйте автобусу управлять самим собой.

4
Почки Кёнигсберга

Помимо той ветви геометрии, что занимается размерами, есть другая ветвь, которую первым упомянул Лейбниц, назвав ее геометрией положения… Таким образом, когда речь зашла о задаче, которая казалась геометрической, но не требовала измерения расстояния, я не сомневался, что она связана с геометрией положения. Поэтому я решил привести здесь метод, найденный мной для решения такого рода задач.

ЛЕОНАРД ЭЙЛЕР.

Решение задачи, связанной с геометрией положения (1736)

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

Мы воспринимаем эти чудеса современной медицины как нечто само собой разумеющееся, но именно они, по существу, впервые дали возможность врачам и хирургам излечивать болезни. Мы умудрились растранжирить большую часть преимуществ антибиотиков в результате массового скармливания их скоту не ради лечения болезней, а чтобы заставить животных увеличиваться в размерах и расти быстрее. И еще в результате того, что миллионы людей прекращали принимать таблетки, как только им становилось лучше, вместо того чтобы пройти полный курс лечения, предписанный врачом. Обе практики привели к развитию устойчивости к антибиотикам у бактерий. Теперь ученые лихорадочно пытаются получить антибиотики следующего поколения. Если им удастся это сделать, я надеюсь, нам хватит здравого смысла не погубить и эти лекарства.

Сегодня становится реальностью и другая мечта хирургов прошлого: пересадка органов. Пока нам, кажется, удается не испортить здесь ничего. Если обстоятельства складываются благоприятно, вы можете получить новое сердце, или новое легкое, или новую почку. Даже новое лицо. Когда-нибудь добрая свинка даже сможет вырастить для вас орган на замену, хотя и не добровольно.

В 1907 году американский медик-исследователь Саймон Флекснер, рассуждая о будущем медицины, предвидел появление возможности хирургической замены больных органов на здоровые от другого человека. Он называл в их числе артерии, сердце, желудок и почки. Первую пересадку почки провел в 1933 году советский хирург Юрий Вороной, который изъял почку у донора, умершего за шесть часов до этого, и пересадил ее пациентке в область бедра. Пациентка умерла через два дня, когда новая почка была отторгнута, потому что у донора была неподходящая группа крови. Самым серьезным препятствием для успешной пересадки органов является иммунная система организма, которая распознаёт новый орган как чужеродный и отторгает его. Первую успешную пересадку почки осуществил Ричард Лоулер в 1950 году. Донорская почка функционировала 10 месяцев, прежде чем была отторгнута, но к тому времени собственные почки пациентки пришли в норму, и женщина прожила еще пять лет.

Человек имеет две почки и вполне может жить с одной. Так что органы для пересадки могут быть получены от живого донора, что сильно упрощает процесс. Почка – самый простой орган для пересадки. Не так уж сложно убедиться, что ткани донора соответствуют по типу тканям реципиента и не будут отторгнуты, а на случай, если что-то пойдет не так, имеются диализные аппараты, которые выполняют функции почки. До появления в 1964 году иммунодепрессантов, предотвращающих отторжение донорской почки, пересадка почек от умерших доноров не проводилась (по крайней мере, в США и Великобритании). Почки для пересадки жертвовали живые доноры, и таких случаев было немало.

В большинстве случаев донор был близким родственником реципиента. Это повышало вероятность совместимости тканей, но главной причиной было то, что мало кто готов был пожертвовать свою почку чужому человеку. В конце концов, если у вас есть вторая, вы можете и дальше жить нормальной жизнью, если одна почка вдруг откажет. Если отдать одну почку постороннему человеку, резерва не останется. Когда же реципиент – ваша мать, брат или дочь, то спасение их жизни перевешивает риск. Проблема постороннего человека воспринимается не так близко к сердцу, и готовых пойти на риск не так много.

Некоторые страны предлагали стимул: деньги. Можно было заплатить постороннему человеку, чтобы он пожертвовал почку одному из ваших родственников. Опасности, связанные с разрешением такого рода операций, достаточно очевидны: нужда, например, может заставить бедных продавать почки богатым. В Великобритании закон прямо запрещал отдавать почку кому-либо, кроме близкого родственника. Законы, принятые в 2004 и 2006 годах, устранили это препятствие, но добавили дополнительные меры против злоупотреблений. Одним из условий стал запрет на передачу каких бы то ни было денег.

Схема расположения семи мостов Кёнигсберга, сделанная Эйлером

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

* * *

Это хорошо известная история, но я все равно перескажу ее, по двум причинам. Она готовит сцену для математической задачи и, кроме того, часто воспринимается неверно. Я, например, до какого-то момента понимал ее совершенно неправильно.

Калининград, город в сегодняшней России, когда-то назывался Кёнигсбергом и в XVIII веке находился в Пруссии. Через город протекала река Прегель, образуя два острова, Кнайпхоф и Ломзе. В городе было семь мостов: каждый из берегов реки связывали с Кнайпхофом по два моста; с Ломзе берега связывало по одному мосту; и наконец, один мост соединял острова друг с другом. Сегодня топография города выглядит иначе. Во время Второй мировой войны город сильно бомбили, и мосты b и d на схеме были разрушены. Мосты a и c были снесены, чтобы освободить место для прокладки новой дороги, а взамен них были выстроены новые мосты. Вместе с оставшимися тремя мостами, один из которых был перестроен в 1935 году, сейчас в городе на прежних местах находятся пять мостов.

Легенда гласит, что граждан Кёнигсберга давно интересовал вопрос, можно ли совершить пешую прогулку по городу, пройдя по каждому из мостов ровно один раз. Это была простенькая головоломка из разряда тех, что можно увидеть на странице газеты или ее электронного эквивалента. Эксперименты с различными маршрутами не помогают ее решить – попробуйте сами. Однако аналогичные задачи имеют решение, причем иногда найти их непросто. Более того, число маршрутов, которые вы можете выбрать, бесконечно, хотя бы потому, что существует бесконечно много способов переходить с одной стороны улицы на другую или двигаться вперед и назад. Именно поэтому невозможно найти решение или доказать, что такового не существует, путем рассмотрения всех возможных маршрутов.

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

И тут на сцене появляется Эйлер, ведущий математик своего времени. Он работал практически во всех областях математики, существовавших на тот момент, и в некоторых областях, которых не существовало, пока он не положил им начало. Кроме того, Эйлер сумел применить математику к огромному числу разнообразных задач реального мира. Его работы варьируют от энциклопедических томов по основным областям чистой математики и математической физики до диковинок и странностей, которые просто показались ему интересными. В начале XVIII века он обратился к загадке о кёнигсбергских мостах, сформулировал ее как точный математический вопрос и предложил доказательство того, что прогулку с обозначенными условиями совершить невозможно. Причем невозможно даже в том случае, если маршрут будет не круговым и закончится не там, где начался.

Эйлер переехал в Россию, в Санкт-Петербург, в 1727 году, когда в России правила императрица Екатерина I, чтобы стать придворным математиком. Муж Екатерины император Петр I основал Санкт-Петербургскую академию (Academia Scientiarum Imperialis Petropolitinae) в 1724–1725 годах, но умер прежде, чем она успела полностью сформироваться и заработать. Эйлер представил свою работу в Академии в 1735 году, и через год она была опубликована. Будучи математиком, причем, по мнению многих, самым плодовитым в истории, Эйлер извлек из головоломки так много, как только смог: он нашел необходимые и достаточные условия для существования решения, не только для кёнигсбергских мостов, но и для любой задачи подобного рода. Вы можете взять 50 000 мостов, связывающих друг с другом 40 000 островов гигантского комплекса, и теорема Эйлера без проблем скажет вам, существует ли для них решение. Если как следует вникнуть в доказательство, оно даже скажет, как это решение найти, – правда, после некоторой возни. Свое доказательство Эйлер изложил довольно схематично, и прошло почти 150 лет, прежде чем кто-то разобрался во всех его деталях, хотя само по себе доказательство не было слишком сложным.

В настоящее время многие книги по теории графов говорят о том, что Эйлер доказал отсутствие у головоломки решения, сведя ее к более простому вопросу о графах. Граф в этом смысле – это множество точек (называемых вершинами), соединенных линиями (их называют ребрами), и все это вместе образует своего рода сеть{34}34
  Не следует путать граф с графиком функции, который представляет собой кривую, соотносящую переменную x со значением функции f(x). Например, парабола есть график функции f(x)= x².


[Закрыть]. Переформулирование с использованием графов превращает головоломку кёнигсбергских мостов в задачу нахождения пути на конкретном графе, в котором каждое ребро используется ровно один раз. Именно так мы решаем эту задачу сегодня, но Эйлер делал не совсем так. В истории это случается часто. Историки математики с удовольствием рассказывают о том, как все происходило на самом деле, в отличие от общепринятого варианта. В реальности Эйлер решил задачу символически{35}35
  Спасибо Робину Уилсону, который мягко указал мне на ошибку, когда я в одной из своих книг изложил все неправильно.


[Закрыть].

Он обозначил каждый участок суши (остров или берег реки) и каждый мост буквой. Суше достались заглавные буквы A, B, C, D, а мостам – строчные a, b, c, d, e, f, g. Каждый мост соединяет друг с другом два участка суши, например, мост f соединяет A и D. Прогулка начинается в некоторой области и может быть описана последовательным перечислением преодоленных участков и мостов до последнего участка суши. В большей части статьи Эйлер описывает маршруты словесно и в основном работает с последовательностью участков суши. Не имеет значения, по какому мосту вы перейдете с A на B, если число сочетаний AB будет равно числу таких мостов. Или можно, наоборот, использовать последовательность мостов – достаточно обозначить точку начала и подсчитать, сколько раз вы посетите заданный участок. Не исключено, что так было бы проще. Ближе к концу статьи Эйлер использует те и другие символы и приводит пример последовательности

EaFbBcFdAeFfCgAhCiDkAmEnApBoElD,

соответствующий более сложной схеме{36}36
  Если вы знаете, с какого участка начать, достаточно привести список только мостов в том порядке, в каком они используются. Последовательные мосты определяют общий участок суши, с которым оба соединены.


[Закрыть].

В такой формулировке конкретный путь, по которому идет пешеход на каждом участке или по каждому мосту, не имеет значения. Единственное, за чем нужно следить, – это последовательность, в которой посещаются участки и проходятся мосты. Проход по мосту подразумевает, что «две заглавные буквы с обеих его сторон различны». Это исключает возможность зайти на мост и возвратиться на ту же сторону. Решение – последовательность чередующихся заглавных и строчных букв A–D и a–g, в которой каждая строчная буква появляется ровно один раз, а заглавные буквы до и после любой заданной строчной соответствуют тем двум участкам берега, которые связаны данным мостом.

Мы можем составить список связей для каждой строчной буквы:

Допустим, мы начинаем с участка B. Три моста связывают B с другими участками: a, b и f. Предположим, мы выбираем f, тогда наша последовательность начинается с Bf. На другом конце моста f находится участок D, так что мы получаем Bf D. У нас имеются два неиспользованных моста, связывающие D с другими участками: e и g. (Мы не можем использовать f второй раз.) Попробуем g, и наш маршрут будет выглядеть как BfDg. На другом конце g находится C, что дает нам BfDgC. Теперь единственная возможность для продолжения у нас – мосты c и d (вновь по g мы идти не можем). Возможно, мы попробуем мост c, что приведет нас к BfDgCc, а затем к BfDgCcA. От участка A идут четыре возможных моста: a, b, d и e (мост c мы уже использовали).

Можем ли мы теперь выбрать мост d? Нет, потому что это даст нам BfDgCcAd и затем BfDgCcAdC. Но все три моста, связанные с C, а именно c, d и g, уже использованы. Но мы не решили головоломку, потому что мост b остался незадействованным: мы по нему не прошли. Стираем мост d. По аналогичным причинам мы не можем воспользоваться и мостом e: это приведет нас на D, где мы и застрянем; более того, по b опять пройти не удалось. Как насчет моста a? Это дает нам BfDgCcAaB, и единственным неиспользованным выходом остается мост b, что дает нам BfDgCcAaBbA. Возможные выходы здесь – d или e. Первый ведет к BfDgCcAaBbAdC, и дальше выхода не остается, но мы не прошли по мосту e. Второй ведет к BfDgCcAaBbAeD, и тоже выхода нет, но мы не прошли по мосту d.

Ну хорошо, такая последовательность выбора не работает, но ведь мы могли выбрать другие мосты раньше. Можно проработать систематически все возможные последовательности… и окажется, что все они не годятся и могут быть исключены. В какой-то момент вы оказываетесь в тупике, не имея разрешенного выхода с текущего участка, но при этом по крайней мере один мост остается непройденным. Список возможных последовательностей конечен и не так уж велик, чтобы протестировать их все. Попробуйте, если хотите.

Если вы это сделаете, то увидите, что у данной головоломки нет решения. Это могло бы удовлетворить граждан Кёнигсберга, но не Эйлера. Во-первых, неясно, почему вы каждый раз упираетесь в тупик. Во-вторых, этот ответ ничего не говорит о том, в каких случаях можно или нельзя решить другие подобные головоломки. Поэтому Эйлер задал единственный и самый важный вопрос, который математики всегда задают после решения задачи: «Да, но почему это сработало?» За ним обычно следует другой, не менее важный вопрос: «Можно ли улучшить решение?»

Эйлер после размышлений сделал три простых наблюдения:

• Если решение существует, то каждый участок должен быть соединен с остальными какой-то последовательностью мостов. Например, если бы в городе было еще два острова E и F, соединенных друг с другом одним или несколькими новыми мостами h, i, j, …, при отсутствии новых мостов между этими островами и остальными участками суши, то пройти по ним можно было бы, лишь курсируя по ним с E на F и обратно. Ни на один из старых мостов попасть оттуда было бы невозможно.

• Считая, что предыдущее условие («связность») соблюдено, можно сказать, что, исключая участки в начале и в конце прогулки, всякий раз, когда вы входите на какой-то участок суши, с него нужно выйти по другому мосту.

• Всякий раз, когда вы это делаете, вы используете два моста, примыкающие к данному участку, которые перестают быть доступными.

Таким образом, двигаясь по маршруту, вы используете мосты парами. Это ключевой вывод. Если на участке суши четное число мостов, вы можете использовать их все и не оказаться в тупике. Если там нечетное число мостов, то вы можете использовать их все, кроме одного, и не застрять. Но вы должны пройти по этому мосту в какой-то момент. Но стоит это сделать – и вы в тупике.

Застревание фатально, если вы находитесь в середине пути. Однако это не проблема в конце. Если же пройти маршрут в обратном направлении, то станет понятно, что это не проблема и в начале прогулки. Из этих рассуждений следует, что если маршрут существует, то максимум два участка суши в нем могут быть связаны нечетным числом мостов. В задаче о мостах Кёнигсберга:

Здесь число участков суши с нечетным количеством мостов равно четырем, а это больше двух. Так что нужного нам маршрута не существует.

Разомкнутый маршрут с использованием пяти оставшихся мостов

Эйлер также заявил без доказательства, что это же условие четности/нечетности является достаточным для существования маршрута. Это немного сложнее, и я не буду здесь останавливаться. Доказал это утверждение Карл Хирхольцер незадолго до своей смерти в 1871 году, а опубликовано доказательство было посмертно в 1873 году. Эйлер также заметил, что если искать замкнутый маршрут, который заканчивался бы там же, где начался, то необходимое и достаточное условие его существования состоит в том, что на каждом участке суши должно быть четное число мостов{37}37
  Это довольно легко доказать, пользуясь эйлеровой характеристикой разомкнутых маршрутов. Основная идея состоит в том, чтобы разбить гипотетический замкнутый маршрут, удалив один мост. Теперь у вас имеется разомкнутый маршрут, а удаленный мост соединял прежде его концы.


[Закрыть].

Если использовать только те пять мостов, которые (в том или ином виде) существуют и сегодня, то B и C оказываются связанными двумя мостами. В таком виде эта задача должна иметь решение, но только для разомкнутого маршрута. Конечные точки должны располагаться на A и D, потому что именно эти участки суши по-прежнему связаны нечетным числом мостов. На рисунке показано такое решение. Существуют и другие: сможете ли вы найти все?

Слева: граф, показывающий связи для мостов Кёнигсберга.

Справа: пример попытки составить маршрут – мост d пропущен

Эйлер сформулировал все вышеизложенное в виде символьных последовательностей вроде BfDgCcAaBbAeD. Некоторое время спустя кто-то догадался, что всему этому можно дать графическую интерпретацию. Кто был первым – неясно, поскольку в середине XIX века эта идея уже витала в воздухе, однако известно, что термин «граф» предложил в 1878 году Джеймс Джозеф Сильвестр. Нарисуйте картинку с четырьмя точками A–D и семью линиями a–f. Сделайте так, чтобы каждая линия соединяла две области на концах соответствующего моста. Карта островов и мостов при этом упрощается, как на рисунке слева. Только что упомянутая символьная последовательность соответствует маршруту на картинке справа с началом в точке B и концом в точке D, где движение прекращается.

Это визуальное упрощение и есть граф кёнигсбергских мостов. В данном представлении неважно, где вы поставите четыре точки (хотя их следует ставить на некотором расстоянии друг от друга, чтобы избежать путаницы), да и конкретная форма линий тоже не имеет значения. Важно лишь, какие именно точки соединяет данная линия. В этой визуальной среде доказательство Эйлера становится очень естественным. Любой маршрут, который входит на участок суши по одному мосту, должен уйти с него по другому, если это не конец разомкнутого маршрута. Аналогично любой маршрут, покидающий участок по одному мосту, должен был ранее входить на него по другому, если это не начало разомкнутого маршрута. Так что мосты должны существовать парами, за исключением двух концов. Следовательно, все участки суши, расположенные не на концах маршрута, связаны с четным числом мостов. Если на концах число мостов нечетное, возможен только незамкнутый маршрут. В противном случае начало и конец могут находиться в одной области и соединяться без всяких мостов, образуя замкнутый маршрут. Теперь к каждой области подходит четное число мостов.

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

Мне кажется замечательным, что простая головоломка может привести к таким значительным нововведениям. Воистину непостижимая эффективность. Кроме того, в этой истории содержится важный урок, который внешний мир зачастую не воспринимает. Не стоит недооценивать математику, которая выглядит просто и больше похожа на детскую игрушку, чем на что-нибудь серьезное. Дело не в том, насколько проста игрушка, а в том, как вы ее используете. Мало того, одна из главных задач хорошей математики состоит в том, чтобы сделать все как можно более простым. (Вы можете усмехнуться, и это будет справедливо, если вспомнить, насколько сложно выглядит значительная часть математики. Я просто должен здесь добавить оговорку, приписываемую Эйнштейну: как можно более простым, но не слишком простым.) Превращение островов в точки, а мостов в линии не меняет сути головоломки, а помогает отбросить лишнюю информацию: какая стоит погода? Грязно ли на улице? Мост металлический или деревянный? Эти вещи важны, если вы собираетесь на субботнюю прогулку или строите мост. Но если вы хотите ответить на вопрос, который ставил в тупик добрых граждан Кёнигсберга, все это лишь помехи.

* * *

Ну а какое отношение мосты Кёнигсберга имеют к трансплантации почек? Непосредственно почти никакого. Косвенно статья Эйлера положила начало развитию теории графов, которая открывает перед нами эффективный способ подбора доноров для реципиентов даже при условии, что большинство доноров готовы отдать свою почку только близкому родственнику{38}38
  Оставшаяся часть этой главы основана на статье: D. Manlove. «Algorithms for kidney donation», London Mathematical Society Newsletter 475 (March 2018) 19–24.


[Закрыть]. Когда в Великобритании в 2004 году вступил в действие Закон о тканях человека, люди получили возможность законным образом отдавать почки не только родственникам.

Очень серьезную проблему представляет поиск подходящих пар доноров и реципиентов, потому что даже в тех случаях, когда имеется донор, тип его тканей и крови может не совпасть с типом тканей и крови предполагаемого реципиента. Представьте себе, что дядюшка Фред нуждается в почке, а его сын Уильям готов пожертвовать свою, но не хочет делиться почкой с чужим человеком. К несчастью, у почки Уильяма не тот тип ткани. До 2004 года на этом все кончалось, и Фред был обречен на частые сеансы диализа на специальном аппарате. Такой же была судьба многих других потенциальных реципиентов, у которых тип ткани совпадает с типом ткани Уильяма. Теперь представьте, что Джон Смит, не состоящий в родстве с Фредом и Уильямом, сталкивается с той же проблемой: его сестра Эмили нуждается в новой почке и он готов отдать ей свою, но, опять же, не готов делиться почкой с чужим человеком. И у него тип ткани отличается от типа ткани Эмили. В итоге никто не получает почку для пересадки.

Предположим, однако, что типы тканей у Джона и у Фреда, а также у Уильяма и Эмили совпадают. После 2004 года это создает условия для законного обмена почками. Задействованные в операциях хирурги могут встретиться и предложить, чтобы Джон разрешил передать его почку Фреду при условии, что почка Уильяма достанется Эмили. Оба донора с гораздо большей вероятностью согласятся на такие условия, поскольку их родственники получат новую почку, а они пожертвуют свою, иначе говоря, сделают то, что собирались сделать с самого начала. Кто именно получит чью почку, не слишком волнует ни доноров, ни реципиентов, хотя это принципиально важно с точки зрения совместимости тканей.

При современных средствах коммуникации хирурги могут обнаружить подобное совпадение, если будут вести реестр потенциальных доноров и реципиентов с указанием типа их ткани. Если число реципиентов и потенциальных доноров невелико, вероятность такого обмена также невелика, но она становится гораздо больше, когда их число растет. Число потенциальных реципиентов весьма велико: в 2017 году в Великобритании в списке ожидающих пересадку почки значилось более 5000 человек. Почка при этом могла поступить как от умершего донора, так и от живого, но число доноров меньше числа реципиентов – около 2000 на тот же момент времени. В результате среднее время ожидания превышает два года для взрослого и девять месяцев для ребенка.

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

Зои передает свою почку Амелии.

Альберт, донор Амелии, соглашается отдать свою почку Бернарду.

Берил, донор Бернарда, соглашается отдать свою почку Кэрол.

Карл, донор Кэрол, соглашается отдать свою почку Дейдре.

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

В целом всех все устраивает. Амелия, Бернард, Кэрол и Дейдра получают новую почку. Альберт, Берил, Карл и Дайана жертвуют свою почку, хотя и не родственнику, но в рамках цепочки, которая принесет ему пользу. Часто доноров это вполне устраивает, что и делает подобные обмены возможными – ведь, если они не согласятся, их родственник не получит почку в этот раз. Зои рада, что ее альтруистический порыв принесет кому-то пользу, и ей все равно, кому именно. В данном случае – Амелии. Наконец, лишняя почка поступает в список ожидания, а это всегда полезно.

Если бы вместо этого Зои просто пожертвовала почку в список ожидания, единственное, что могли бы сделать Амелия, Бернард, Кэрол и Дейдра, – это записаться в список ожидания. Не сделав этого, они высвобождают четыре дополнительные почки. Это называется цепочкой последовательной уступки по принципу домино. Зои роняет первую костяшку, и вслед за ней падает еще несколько. Назовем этот принцип просто цепочкой.

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

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

* * *

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

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

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

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