До предела чисел. Эйлер. Математический анализ (Наварро) - страница 28

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

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

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

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

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

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

РИС. 1

РИС . 2

РИС. 3

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

Поскольку в данном случае 4, то жители Кенигсберга остались без идеального пути. Если бы они спросили совета у Эйлера, он ответил бы, что задачу можно решить, добавив или убрав один мост.

Еще один вопрос, занимавший Эйлера и связанный с графами, — задача о ходе коня в шахматах. Ученый разобрал ее в 1759 году в работе Solution d’une question curieuse que ne soumise a aucune analyse ("Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию"). Задача состоит в поиске маршрута, при котором конь пройдет по всем клеткам, независимо от начальной позиции. Эйлер нашел решение и попутно заложил основу того, что впоследствии было названо гамильтоновыми графами — путями, проходящими по одному разу через все узлы и возвращающимися к исходной точке (рисунок 4).

РИС. 4

Эйлер называл все задачи, связанные с задачей о мостах, geometriam situs, а термин "топология", использующийся до сих пор, ввел в 1847 году Иоганн Бенедикт Листинг (1808-1882). Сейчас топология — развитая область математики, объединяющая понятия, которые обычно считаются не совсем геометрическими: внутри и снаружи, близко и далеко, ориентируемое и нео- риентируемое, связанное и несвязанное, непрерывное и разрывное. Топология занимается вопросами, на первый взгляд далекими от традиционной математики. Таким образом, в рамках этой дисциплины были найдены решения самых разных задач, таких как поиск минимального количества цветов, необходимого для раскрашивания любой произвольной карты (их нужно четыре). Было также найдено строгое доказательство того, что на Земле всегда существуют диаметрально противоположные точки с одинаковым давлением и одинаковой температурой или что если уменьшить листок бумаги, а потом положить на него исходный лист, то всегда будет точка первого, которая коснется соответствующей точки второго. В этой же области была сформулирована задача о причесывании ежа, в которой понятие направления рассматривается с типично топологической точки зрения. Эйлер не просто попытался объяснить существующую Вселенную — он открыл двери в миры, до той поры неизвестные.