31. Острова и мосты

В НАчале XVIII в. была весьма популярна головоломка о Кенигсбергских мостах. В городе Кенигсберге (ныне Ка-лининграде) было два острова, соединенных семью МостаМи с берегами реки Прегеля (ныне Преголь) и МЕжду Собой так, как показано на рис. 8. Задача состояла в ОтыСканИИ маршрута прогулки, начинавшейся и КончавшейСя в одном и том же месте, причем требовалось ровно один раз пройти каждый мост. Все попытки найти подбором такой маршрут кончались неудачей. Причину этих Неудач выяснил в 1736 г. Эйлер, указавший общие условия Разрешимости или неразрешимости подобных задач.

Чтобы прояснить математическую сущность ЗАдачи, Эйлер заменил оба острова, а также участки суши по ОбЕим бЕРегам реки, точками, а мосты изобразил линиями, Соединяющими эти точки (рис. 9). Теперь задача свелась к сЛЕдующему. Имеется несколЬКо точек, некоторые из Которых соЕДинены линиями. При каком условии существует Маршрут, начинающийся и кончающийся в одной и той же точке и проходящий один и толЬКо один раз по каждой линии?

Очевидны два необходимых условия разрешимости Этой задачи: во-первых, система точек и линий не ДолжНа распадаться на несколько отдельных частей (или, как Говорят, оНА должна быть связной), а во-вторых, из КажДой точки должно выходить четное число линий. В самом ДеЛе, при обходе маршрута мы должны столько же раз войти в каждую точку, сколько раз из нее выходим, так Как ИнАче в этой точке маршрут прерветСЯ. Поскольку это условие не выполняется для схемы на рис. 9, то решить Задачу о мостах невозможно. Невозможно найти и Маршрут, проходящий по всем мостам, ДАже есЛИ снять требоВание начинать и кончать его в одноЙ и тоЙ Же точке. В этом случае из двух точек (начала и коНЦа Маршрута) Может выходить нечетНОе число линий. Но на рис. 9 Не две, а четыре такие точки, а потому и эта задача Неразрешима.

Сформулированное выше необходимое условие Является и достаточным: Если в системе точек и линий из Каждой Точки выходит четное число линий, причем эта Cuстема связна, то можно обойти все линии, начав и кончив Маршрут в одной точке и пройдя каждую линию лишЬ одиН раз.

В самом деле, выйдем из какой-нибудь точки А И будем идти до тех пор, пока это возмоЖНо. Так как из Каждой Точки выходит четное число линий, то попав в КакУю-нибудь точку, мы можем из нее и выйти. ЕдинственныМ исключением является исходная точка, в которой и законЧится наш маршрут. Однако может случиться, что маршрут прошел лишь по части линий. Тогда, СтереВ ПройДенные линии, мы получим новую систему, в котороЙ из Каждой точки выходит четное число лиНИй. ПоэтоМУ и в новой системе есть замкнутый маршрут, ВЫходящий, например, из точки В старого маршрута. Тогда выЙдЕм из точки А, пройдем по старому маршруту до точки В. От точки В пройдем новый замкнутый маршрут, а затЕМ пойдем дальше по старому пути, пока НЕ закончим его в ТочКе А. Таким образом исходный маршрут оказался расширенным. Повторяя такие расширения, мы получиМ, В конце концов, замкнутый маршрут, проходящий через все линии системы. Таким ЖЕ образом разбирается случай, когда имеются две точки, из которых выходит Нечетное число лиНиЙ.

Системы точек и лиНИй, аналогичные РассмотРенным выше, встречаются во многих областЯХ МатематИки и ее Приложений — в физике, химиИ, электронике, Теории Связи, геНЕтике, психологии, экономике, Лингвистике И т. Д. Они получили особое назваНИе «графы». В Настоящее время теория графов является одНОй из Стремительно Развивающихся областей математикИ

< Предыдущая		Следующая >