Это база: Зачем нужна математика в повседневной жизни - Йэн Стюарт
Шрифт:
Интервал:
Закладка:
Можем ли мы теперь выбрать мост 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, где движение прекращается.
Это визуальное упрощение и есть граф кёнигсбергских мостов. В данном представлении неважно, где вы поставите четыре точки (хотя их следует ставить на некотором расстоянии друг от друга, чтобы избежать путаницы), да и конкретная форма линий тоже не имеет значения. Важно лишь, какие именно точки соединяет данная линия. В этой визуальной среде доказательство Эйлера
