Понятие графа

Если снова найдутся ребра, которые не вошли в путь, то найдем новые циклы. Число ребе и вершин конечно, процесс закончится.

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

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

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

Теорема: Если граф Г обладает эйлеровым путем с концами А и В (А не совпадает с В), то граф Г связный и А и В – единственные нечетные его вершины.

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

Верно и обратное.

Теорема: Если граф Г связный и А и В единственные и нечетные вершины его, то граф Г обладает эйлеровым путем с концами А и В.

Доказательство: Вершины А и В могут быть соединены ребром в графе (рис. 2.27), а могут быть и не соединены (рис. 2.28).

Если А и В соединены ребром, то удалим его; тогда все вершины станут четными. Новый граф, согласно предыдущей теореме, обладает эйлеровым циклом, началом и концом которого может служить любая вершина. Найдем эйлеров путь в вершине А и кончим его в вершине А. Добавим ребро (А, В) и получим эйлеров путь с началом в А и концом в В.

Если А и В не соединены ребром, то к графу добавим новое ребро (А, В), тогда все вершины его станут четными. Новый граф, согласно предыдущей теореме, обладает эйлеровым циклом. Начнем его из вершины А по ребру (А, В). Закончится путь тоже в вершине А. Если удалить теперь из полученного цикла ребро (А, В), то останется эйлеров путь с началом в В и концом в А или с началом в А и концом в В.

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

Теорема: Если связный граф имеет 2k нечетных вершин, то найдется семейство из k путей, которые в совокупности содержат все ребра графа в точности по одному разу.

Доказательство: Половину нечетных вершин обозначим А₁, А₂, …, А_k, другую – В₁, В₂, …, В_k (рис 2.29). Если вершины А_l и В_l (1 ≤ l ≤ k) соединены ребром, то удалим из графа Г ребро (А_l, В_l). Если вершины А_l и В_l не соединены ребром, то добавим к Г ребро (А_l, В_l). Все вершины нового графа будут четными, то есть в новой графе найдется эйлеров цикл. При восстановлении графа Г цикл разобьется на k отдельных путей, содержащих все ребра графа.

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

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

Доказательство: Дадим точное правило построения такого пути, предложенное Тарри.

Из произвольной вершины А пройдем вдоль какого-нибудь ребра (А, В), отметив его стрелкой, указывающей направление пути (рис. 2.37). Из В пройдем к третьей вершине, снова отметив стрелкой направление прибытия и так далее. Ребро, по которому впервые прибываем в вершину, будем отмечать стрелкой. Выходя из вершины, выбирают дальнейший путь: либо ребро, еще не проходили ни разу, либо ребро, по которому прибыли в эту вершину. Договариваемся, что ребро, по которому впервые попали в вершину, будем использовать для выхода только тогда, когда оно остается единственным выходом из этой вершины.

Продолжаем строить путь, пока это возможно. Заметим, что в  каждой вершине имеется одинаковое число возможностей для входа  и выхода. Процесс может закончиться  только в исходной вершине А.

На рисунке 2.37 дан связный граф Г, на котором по правилу Тарри построен искомый цикл; для удобства стрелки пронумерованы.

Итак, процесс закончился в А. Теперь необходимо доказать, что  в обоих направлениях пройдены все  ребра. Выхода из А более нет, так как иначе процесс бы не закончился и мы могли бы двигаться дальше. Все входы в вершину А тоже использованы, так как иначе процесс бы не закончился и мы могли бы двигаться дальше. Все входы в вершину А тоже использованы, так как их число равно числу путей, по которому мы выходили из А. В частности,  ребро (А, В) пройдено в обоих направлениях. Следовательно, все ребра, которые которым принадлежит В, тоже пройдены в обоих направлениях, так как первое входящее в В ребро (А, В) по условию могло быть использовано в качестве входящего лишь в последнюю очередь.

То же рассуждение применимо  к третьему в пути ребру (С, D) и следующей вершины С и т. д. Поскольку граф связный и имеет конечное число вершин и ребер, аналогично можно исследовать все его вершины и все его ребра.

Гамильтонов цикл