Models of the Mind

Эйлер, эрудит, родившийся в Швейцарии, но живший в России, в 1736 году написал работу "Решение задачи о геометрии положения" (Solutio problematis ad geometriam situs pertinentis). В этой работе он дал однозначный ответ на вопрос: кёнигсбержец не может совершить прогулку по своему городу, проходя через каждый мост ровно один раз. Чтобы доказать это, ему пришлось упростить карту города до скелета ее полной структуры и работать с ней логически. Он показал, не используя слово, как превратить данные в граф и как выполнять на нем вычисления (см. рис. 20).

В контексте теории графов слово "граф" не означает график или диаграмму, как это принято в обычном языке. Скорее, граф - это математический объект, состоящий из узлов и ребер (в современном понимании).Узлы - это базовые единицы графа, а ребра представляют связи между ними. В примере с Кенигсбергом мосты служат ребрами, соединяющими четыре различных массива суши - узлы. Степень узла - это количество ребер, которые он имеет; таким образом, "степень" массива суши - это количество мостов, которые к нему подходят.

 

Рисунок 20

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

Затем Эйлер заметил нечто важное в количестве мостов, которые есть у каждого массива суши. Это число связано с тем, сколько раз этот массив должен появиться в списке путей. Например, у массива земли B есть три моста, а значит, "B" должен дважды появиться в любом пути, который пересекает каждый мост по одному разу - то есть нет способа пересечь эти три моста, не посетив B дважды. То же самое верно и для массивов C и D, поскольку у них тоже по два моста. А вот массив A с пятью мостами должен появиться в списке путей три раза.

Вместе взятые, любой путь, удовлетворяющий этим требованиям, будет состоять из девяти (2+2+2+3) букв. Однако список из девяти букв представляет собой путь, пересекающий восемь мостов. Поэтому невозможно построить путь, который пересекает каждый из семи мостов только один раз.

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

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