3. Эйлеровы и гамильтоновы графы
Многие открытия теории графов были использованы для решения «практических» проблем — задач, головоломок, игр и т. д. К одной из этих задач относится знаменитая задача о кенигсбергских мостах. Ее можно сформулировать следующим образом:
На реке Преголя в Кенигсберге (теперь г. Калининград) было два острова. Они соединялись между собой и с берегами реки семью мостами, как показано на рис. 3.1, а. Задача заключалась в том, чтобы, начав двигаться с одного из четырех участков суши (помеченных на рис. 3.1, а буквами А, В, С и D), только один раз пройти по каждому мосту и снова вернуться в исходную точку, т. е. определить замкнутый маршрут через все семь мостов, дважды не пересекая ни один из них.
Рис. 3.1. а — задача о кенигсбергских мостах; б — граф задачи о кенигсбергских мостах.
Многие были убеждены, что у этой задачи нет решения. Однако лишь в 1736 г. великий швейцарский математик Эйлер доказал возможность решения задачи и тем самым заложил основу теории графов. Эйлер был первым, кто показал, что эта задача эквивалентна созданию замкнутой цепи вдоль ребер графа (рис. 3.1, б), в котором вершины А, В, С и D представляют собой участки суши, а ребра — мосты, соединяющие эти участки. Затем он обобщил эту задачу и охарактеризовал ее с точки зрения графов, в которых существует такая замкнутая цепь. Такие графы стали называться эйлеровыми. В разд. 3.1 мы рассмотрим эти графы.
В 1859 г. другой известный математик — сэр Уильям Гамильтон — придумал игру, в которой требуется обойти замкнутый контур
всех ребер додекаэдра, минуя каждую вершину лишь один раз. В теории графов эта игра эквивалентна определению остовного цикла, содержащего все 20 вершин (рис. 3.2).
Рис. 3.2. Граф игры Гамильтона.
Можно проверить, что последовательность вершин 1, 2,..., 20, образует такой цикл в графе. Все графы, в которых существует подобный остовный цикл, называются гамильтоновыми. Эти графы мы рассмотрим в разд. 3.2.
