Эйлер. Математический анализ | страница 29

Через город протекала река Преголя, притоки которой образовывали остров и делили город на три части, соединенные семью мостами, по которым жители могли переходить реку, как видно на рисунке на предыдущей странице. В таком идиллическом городском пейзаже можно было проложить множество разных маршрутов, но некоторые жители задались вопросом, можно ли создать замкнутую траекторию, то есть такой маршрут, который начинался бы и заканчивался в одной и той же точке так, чтобы при этом нужно было проходить всего один раз по каждому мосту. Это был математический вызов. Мостов было всего семь, а возможных маршрутов — несколько тысяч. Но абсурд ситуации заключался в том, что, по какому бы пути вы ни пошли, из какой бы точки ни стартовали, проходя всего один раз по каждому мосту, вы оказываетесь каждый раз не там, откуда начали. Многие стали сомневаться (и довольно справедливо) в том, что искомый маршрут существует, как замок в книге Кафки. Во времена Эйлера ученые нередко задавали себе подобные загадки. Если, не без помощи удачи, решение находилось, это могло привести к появлению новых математических теорий. Гораздо реже такие задачи открывали дорогу новой, благодатной и плодотворной области науки, и именно это случилось с задачей о мостах Кенигсберга. Исходя из схематичного плана города (рисунок 1 на следующей странице), Эйлер решил абстрагироваться от формы всех его составляющих и заменить их графом так, чтобы точки на суше стали вершинами, а мосты — путями (см. рисунок 2). Работая с получившимся графом, Эйлер пришел к своим выводам.

Граф — это рисунок в виде сети, состоящий из двух элементов: точек, называемых узлами или вершинами, и связей между ними — дуг или ребер. Степень узла — это количество исходящих из него дуг. Путь, по которому идет пешеход, будет называться эйлеровым, если он проходит по одному разу по каждой дуге. Если же маршрут начинается и заканчивается в одном и том же узле, то мы имеем дело с эйлеровым циклом (рисунок 3). Из-за особенностей этого цикла его называют идеальным путем.

Рассуждения Эйлера можно записать таким образом.

Обозначим через п количество узлов четной степени.

а) Если n = 0, то в графе содержится хотя бы один эйлеров цикл.

б) Если n = 2, то в графе содержится хотя бы один эйлеров путь, но ни одного цикла.

в) Если n > 2, то в графе нет ни пути, ни цикла.

РИС. 1

РИС . 2

РИС. 3

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