Задача о кёнигсбергских мостах. Эйлеровы линия, граф и путь. Необходимые и достаточные условия существования эйлерового графа и пути

    Многие открытия теории графов были использованы для решения «практических» проблем – задач, головоломок, игр и т.д. Развлечения, в которых требуется обрисовать некоторую фигуру, не прерывая и не повторяя линии, являются по-видимому очень давними. Считается, что фигура, называемая «саблями Магомета», имеет арабское происхождение. 

Рис. 6.7

Задача 1. К одной из таких задач относится знаменитая задача о кёнигсбергских мостах. Теория графов является одной из немногих областей математики, дата рождения которых может быть указана. Первая работа о графах, принадлежащая швейцарскому математику Леонарду Эйлеру (1707–1783), появилась в 1736 году в публикациях Петербургской Академии наук. Эйлер начал свою работу о графах с рассмотрения головоломки – так называемой задачи о «кёнигсбергских мостах». Город Кёнигсберг (ныне Калининград) расположен на берегах реки Прегель и двух островах. Различные части города были соединены семью мостами. По воскресеньям горожане совершали прогулки по городу. Вопрос заключался в том, можно ли совершить прогулки таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту.

Рис. 6.8.а                     Рис. 6.9.б

Схематическая карта Кёнигсберга изображена на рис. 6.9.а. Четыре части города обозначены буквами А, В, С, D. Так как нас интересуют только переходы по мостам, мы можем считать А, В, С, D вершинами некоторого графа, рёбра которого отвечают соответствующим мостам. Этот граф изображён на рис. 6.9.б. Эйлер показал, что задача не имеет решения, т.е. не существует цикла, проходящего по всем рёбрам точно по одному разу. Ведь если бы такой цикл существовал, то в каждой вершине графа было бы столько входящих в неё рёбер, сколько и выходящих из неё, т.е. в каждой вершине графа было бы чётное число рёбер. Однако это условие, очевидно, не выполнено для графа, представляющего карту Кёнигсберга.

   6.4. Эйлерова линия и эйлеров граф.

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

Определение. Эйлеров граф можно обойти полностью, проходя по каждому ребру только один раз.

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

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

Определение. Чтобы граф был эйлеровым, необходимы два условия: связность графа и чётность степеней всех его вершин.

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

Если начать путь из произвольной вершины графа Г, то найдётся цикл, содержащий все рёбра графа. Пусть А произвольная вершина графа Г.

Рис. 6.10

Из А начнём путь I  по одному из рёбер и продолжим его, проходя каждый раз по новому ребру. Так как число рёбер конечно, то этот путь должен окончиться, причём в вершине А (на рис. 6.10 путь I и направление его обхода показаны штриховыми стрелками). Он не может закончиться в другой вершине, так как в этом случае все рёбра инцидентные этой вершине окажутся пройденными по разу и их число будет нечётным.

 Если путь I, замкнувшийся в А, проходит через все рёбра графа, то мы получим искомый эйлеров цикл.

Если остались не пройденные рёбра, то должна существовать вершина В, принадлежащая I и ребру, не вошедшему в I, так как в противном случае граф окажется не связанным, потому что вершина, соответствующая не пройденному ребру, не будет связана маршрутом с любой вершиной пути I. Так как вершина В – чётная, то число рёбер, которым принадлежит В и которые не вошли в путь I, тоже чётное.

    Начнём новый путь s из В и используем только рёбра, не принадлежащие I. Этот путь кончится в В (на рис. 6.10 путь s обозначен сплошными стрелками). Это доказывается рассуждением, аналогичным тому, как доказывалось, что путь кончится в A. Объединим теперь оба цикла: из А пройдём по пути I к В, затем по циклу s и, вернувшись в В, пройдём по оставшейся части пути l обратно в А. Если снова найдутся рёбра, которые не вошли в путь, то найдём новые циклы. Число рёбер и вершин конечно, процесс закончится.

Таким образом, в соответствии с теоремой Эйлера, в задаче о кёнигсбергских мостах нет эйлерова цикла (следует из условий необходимости).

Введем понятие эйлерова пути.

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