Йэн Стюарт – Это база: Зачем нужна математика в повседневной жизни (страница 17)

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

EaFbBcFdAeFfCgAhCiDkAmEnApBoElD,

соответствующий более сложной схеме{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}.

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

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

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

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

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

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