Том 11. Карты метро и нейронные сети. Теория графов

В этой главе мы рассказали о том, что часто происходит в математике: задача, которая изначально кажется лишь игрой, создает основу для серьезных исследований.

* * *

ЦВЕТА, ГРАФЫ И СТИХОТВОРЕНИЯ

Иногда поэтическое вдохновение и красота стихотворения оказываются перечеркнуты последующими событиями. Именно это произошло с английским поэтом Дж. Линдоном: он, удивленный стремлением многих людей доказать, что четырех цветов достаточно для раскраски любого графа, написал такие строки:

В четыре краски красят математики,

Стремясь найти решение задачи.

Они меняют области местами

Но неизменно терпят неудачу.

Со временем эти стихи потеряли смысл: ученые потратили много сил и времени, но решили задачу о четырех красках.

Глава 3 Графы, циклы и оптимизация

Я верю, что наша нация может взять на себя обязательство достичь поставленной цели — высадить человека на поверхности Луны и благополучно вернуть его на Землю в этом десятилетии.

Джон Ф. Кеннеди, 25 мая 1961 года

Господи, теперь нам действительно нужно это сделать.

Роберт Фрейтаг (NASA)

Вторая половина XX века ознаменовалась не только стремительным развитием теории графов, но и началом ее широкого применения в задачах планирования и оптимизации. Развитию теории графов способствовал технический прогресс и расцвет информатики и вычислительной техники, но никогда прежде не проводилось столь обширного исследования методов и алгоритмов поиска решений, оптимальных по времени или денежным затратам. Масштабная программа NASA по запуску ракеты «Аполлон-2», сбор мусора и уборка улиц в крупных городах, производственные цепочки, системы распределения продукции — для всех этих задач требовались методы, позволявшие найти оптимальное решение. Исследование операций достигло своего расцвета, а теория графов вызвала интерес, который не угасает и поныне. В этой главе мы приглашаем читателя оценить возможности этой теории для решения практических задач оптимизации.

Эйлеровы циклы

В связном графе эйлеровым циклом называется путь, содержащий все ребра графа, начальная и конечная вершины которого совпадают. При этом вершины могут повторяться, а ребра — нет.

На первом из следующих рисунков вы можете видеть эйлеров цикл. Во втором графе эйлерова цикла не существует.

Эйлер с точностью определил, когда в связном графе существует эйлеров цикл. Для этого он использовал понятие степени вершины, равное числу ребер, исходящих из данной вершины. Критерий существования эйлерова цикла выражен теоремой, которая звучит так:

«Связный граф содержит эйлеров цикл тогда и только тогда, когда все его вершины имеют четную степень».

Следует подчеркнуть, что если граф содержит эйлеровы циклы, то каждое ребро при обходе графа имеет «пару». Поэтому логично, что из каждой вершины будет выходить четное число ребер, то есть все вершины будут иметь четную степень. Эта теорема позволяет мгновенно определить, содержит ли граф эйлеров цикл, путем простого подсчета степеней вершин. Эффективный поиск эйлеровых циклов — совершенно другой вопрос.

* * *

ЭЙЛЕРОВЫ ЦИКЛЫ В ЗАНИМАТЕЛЬНЫХ ЗАДАЧАХ

Классическая математическая игра с карандашом и бумагой заключается в том, чтобы обойти все вершины графа и вернуться в исходную, пройдя по всем ребрам ровно один раз, не отрывая карандаша от бумаги. Попробуйте найти такой путь в графе, который показан на рисунке.

* * *

Задача китайского почтальона