Задача о кенигсбергских мостах. Постановка и решение Эйлером этой задачи знаменует начало разработки теории графов. Расположение мостов приведено на рис. 3.15, а.
Рис. 3.15. Расположение мостов: а - схема мостов, б - граф F, соответствующий схеме мостов
Требуется пройти каждый мост по одному разу и вернуться в исходную часть города. Можно построить граф задачи, в котором каждой части города соответствует вершина, а каждому мосту - ребро, инцидентное вершинам, относящимся к соединяемым им частям (рис. 3.15, б).
Обходу мостов соответствует последовательность рёбер графа F, в которой два соседних ребра имеют общую вершину, т.е. маршрут. Так как в конце обхода нужно вернуться в исходную часть города и на каждом мосту побывать по одному разу, то этот маршрут является циклом, содержащим все рёбра графа. Такие циклы называются эйлеровыми, а графы, имеющие эйлеровы циклы, - эйлеровыми графами.
Эйлеров цикл можно считать следом карандаша, вычерчивающего этот граф, не отрываясь от бумаги, причём процесс изображения графа начинается и кончается в одной и той же точке.
Примером эйлерова графа является фигура, которая называется сабли Магомета и имеет арабское происхождение (рис. 3.16).
Рис. 3.16.
Условия, при которых псевдограф эйлеров
Теорема 3.3 (Эйлера). Конечный неориентированный псевдограф F эйлеров, тогда и только тогда, когда он связный и степени всех его вершин чётны.
ÿ Необходимость. Пусть конечный неориентированный граф F эйлеров.
По определению, эйлеров граф имеет цикл, содержащий все рёбра этого графа. Это значит, что в эйлеровом графе всегда найдётся маршрут, соединяющий любые две его вершины. Следовательно, эйлеров граф связен.
Рассмотрим какую-нибудь произвольную вершину vi графа F, отличную от начала эйлерова цикла. Каждый раз, когда эйлеров цикл приходит в эту вершину по одному ребру, он должен выйти из неё по другому ребру; поэтому каждый такой проход даёт вклад 2 в степень вершины. Если вершину vi прошли в общей сложности k раз, то степень этой вершины равна 2k, т.е. чётна.
Рассмотрим теперь вершину v0, которая является началом (и концом) эйлерова цикла. Каждый выход из этой вершины по одному ребру плюс возврат в неё по другому ребру даёт вклад 2 в степень этой вершины. Если из начальной вершины выходили m раз, то и возвращались в неё m раз, следовательно, степень этой вершины равна 2m (тоже чётна).
Достаточность. Пусть граф F связный и степени всех его вершин чётны.
Начнём построение эйлерова цикла с произвольной вершины v0 графа F. Каждый раз, когда мы добавляем к маршруту новое ребро и приходим в новую вершину vi (vi¹v0), число “свободных” (непройденных) рёбер в этой вершине уменьшается на единицу. Так как до этого оно было чётным, то теперь становится нечётным, а значит, не может оказаться нулём; поэтому закончиться в вершине vi эйлеров цикл не может. Напротив, каждый выход из исходной вершины v0 плюс возврат в неё уменьшает число “свободных” (непройденных) рёбер на 2 и, в конце концов, станет нулём, а значит, процесс построения цикла может закончиться только в вершине v0.
Совсем не обязательно, что построенный таким образом цикл проходит через все рёбра графа F. Параллельно дальнейшему изложению будем рассматривать простой пример, который облегчит понимание последней части доказательства.
Рис. 3.17. Эйлеров граф F.
Предположим, что, выйдя из вершины v0 (рис. 3.17) и пройдя по маршруту 1-2-3-4, мы вернулись в v0. Принадлежащие построенному циклу рёбра порождают связную часть C графа F, в которой степени всех вершин чётны (на рис. 3.17 рёбра графа C проведены сплошной линией). Значит, чётными будут и степени вершин графа F1=F\C (на рис. 3.17 рёбра графа F1обозначены пунктирной линией).
Так как F, по условию, связный граф, то в C найдётся хотя бы одна вершина v*, инцидентная также рёбрам из F1. Начиная с этой вершины, можно, как и ранее, построить цикл C* в F1, кончающийся также в v* (на рис. 3.17 цикл C* - 5-6-7).
Эта вершина, кроме того, разбивает цикл C на 2 участка: C1 с началом в v0 и концом в v* (на рис. 3.17 участок C1 - 1-2-3) и C2 с началом в v* и концом в v0 (на рис. 3.17 участок C2 - 4). Тогда C1È C*È C2 также является циклом, начинающимся и кончающимся в вершине v0, но имеющим большее число рёбер (на рис. 3.17 цикл 1-2-3-5-6-7-4 - включает все рёбра графа F).
В общем случае и этот цикл не обязательно проходит через все рёбра графа F. Тогда процесс расширения цикла аналогичным образом повторяют. Каждый раз число рёбер в цикле увеличивается не менее чем на два, следовательно, в конце концов, эйлеров цикл будет построен.
ÿ
В графе задачи о кенигсбергских мостах все вершины имеют нечётную степень, значит, решение этой задачи невозможно.
Флёри дал очень простой алгоритм построения эйлерова цикла в неор. графе (если такой цикл существует). Этот алгоритм можно легко распространить и на орграфы. Начать с некоторой вершины p и каждый раз вычеркивать пройденное ребро. Не проходить по ребру, если удаление этого ребра приводит к разбиению графа на 2 связные компоненты (не считая изолир-х вершин).
Эйлеровой называют цепь, включающую все рёбра данного конечного неориентированного графа G, но имеющую различные начало v’ и конец v’’.
Необходимыми и достаточными условиями существования в конечном неориентированном псевдографе эйлеровой цепи являются его связность и чётность степеней всех его вершин, кроме начальной v’ и конечной v’’. Последние две вершины должны иметь нечётные степени.
Рис. 3.16.
Рис. 3.17. Эйлеров граф F.