Эйлеровы и гамельтовы графы

 

Теорема 1(критерий):

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

Доказательство:  Предположим, что  граф G имеет эйлеров цикл. Граф является связным, так как каждая вершина принадлежит циклу. Для всякой вершины v графа G каждый раз, когда эйлеров цикл проходит через v, он вносит 2 в степень v. Поэтому степень v чётная.

Обратно, нужно показать, что каждый связный граф, у которого степени вершин чётные, имеет эйлеров цикл. Докажем эту теорему, используя индукцию по числу вершин. Поскольку теорема тривиально справедлива при n£3, начнём индукцию с n=3. Предположим, что каждый связный граф, имеющий менее k вершин, и все вершины которого обладают чётной степенью, содержит эйлеров цикл. Пусть G – связный граф, содержащий k вершин, степени которых чётные. Допустим, что v₁ и v₂ - вершины графа G. Поскольку граф G – связный, существует путь из v₁ в v₂ .Поскольку степень v₂ – чётная, существует неиспользованное ребро, по которому можно продолжить путь. Поскольку граф конечный, то путь, в конце концов, должен вернуться в v₁  , и эйлеров цикл С₁ можно считать построенным. Если С₁ является эйлеровым циклом для G, тогда доказательство закончено. Если нет, то пусть G^/ - подграф графа G, полученный удалением всех рёбер, принадлежащих С₁. Поскольку С₁ содержит чётное число рёбер, инцидентных каждой вершине, каждая вершина подграфа G^/ имеет чётную степень.

Пусть e – ребро графа G^/ , пусть G_e – компонента графа G^/ , содержащая е. Поскольку G^/ имеет менее, чем k, вершин, и у каждой вершины графа G^/ чётная степень, граф G^/ имеет эйлеров цикл. Пусть С₂ . Далее у С₁ и С₂ имеется общая вершина, допустим, а. Теперь можно продолжить эйлеров цикл, начиная его в а, пройти С₁ , вернуться в а, затем пройти С₂ и вернуться в а. Если новый эйлеров цикл не является эйлеровым циклом для G , продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, к конце концов, не получим эйлеров цикл для G .

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

Следствие 1(а):  Пусть G- связный граф, в котором 2n вершин имеют нечётные степени, n>1. Тогда множество рёбер графа G можно разбить на n открытых цепей.

Следствие 1(б):   Пусть G- связный граф, в котором две вершины имеют нечётные степени. Тогда в G есть открытая цепь, содержащая все вершины и все рёбра графа G (и начинающаяся в одной из вершин с нечётной степенью, а кончающаяся в другой).[6]

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

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

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

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

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

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

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

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

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

Доказательство: Половину нечётных вершин обозначим А₁,А₂,…,А_k,другую половину В₁,В₂,…,В_k(рис.7). Если вершины А_i и В_i (1<i<k) соединены ребром, то удалим из графа G ребро (А_i,В_i). Если вершины А и В не соединены ребром, то добавим к G ребро (А_i,В_i). Все вершины нового графа будут чётными, то есть в новом графе найдётся эйлеров цикл. При восстановлении графа G цикл разобьется на k отдельных путей, содержащих все рёбра графа.

 

 

 

                                                           Рис.7

Пусть G=(V,E) – ориентированный граф. Ориентированным циклом называется ориентированный путь ненулевой длины из вершины в ту же вершину без повторения ребер.

Пусть G=(V,E) – ориентированный граф. Ориентированный цикл, который включает все рёбра и вершины графа G, называется эйлеровым циклом. Говорят, что ориентированный граф G имеет эйлеров цикл.

Теорема 5:  Ориентированный граф имеет эйлеров цикл тогда и только тогда, когда он связный и степень входа каждой вершины равна степени выхода.

2.3  Оценка числа эйлеровых графов

 

Лемма : В любом графе число вершин нечётной степени чётно.

Доказательство:      По теореме 1 сумма степеней всех вершин число  чётное. Сумма степеней вершин чётной степени чётна, значит, сумма степеней вершин нечётной степени также чётна, значит, их чётное число.

Пусть G(p) – множество всех графов с р вершинами, а Е(р) – множество эйлеровых графов с р вершинами.

Теорема 6: Эйлеровых графов почти нет, то есть

     lim

Доказательство:    Пусть E^/ (р) – множество графов с р вершинами и чётными степенями. Тогда по теореме1 Е(р)ÌЕ^/(p) и |Е(р)|£|Е^/(p)|.В любом графе число вершин нечётной степени чётно, следовательно, любой граф из Е^/(p) можно получить из некоторого графа G(p-1), если добавить новую вершину и соединить её со всеми старыми вершинами нечётной степени. Следовательно, |Е^/(p)| £|G(p-1)|. Но |G(p)|=2^{C(p, 2)}. Заметим, что

 

    С(k,2)-C(k-1,2)=

=               

Далее имеем:  

      |Е(р)|£|Е^/(p)| £|G(p-1)| = 2^{C( p-1,2)} =2^C(p,2)-(p-1) = |G(p)|2^-(p-1)

и   

, откуда     lim   . [3]       

2.4   Алгоритм построения эйлеровой цепи в данном эйлеровом графе.

 

Этот  метод известен под названием  алгоритма Флёри.

Теорема 7:   Пусть G – эйлеров граф, тогда следующая процедура всегда возможна и приводит к эйлеровой цепи графа G. Выходя из произвольной вершины и, идём по рёбрам графа произвольным образом, соблюдая лишь следующие правила:

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

Доказательство:    Покажем сначала, что указанная  процедура может быть выполнена  на каждом этапе. Предположим, что мы достигли некоторой вершины V; тогда если V¹U, то оставшийся подграф H связен и содержит ровно две вершины нечётной степени, а именно U и V. Согласно теореме 3 и определению полуэйлерова графа, граф H содержит полуэйлерову цепь P из V в U. Поскольку удаление первого ребра цепи Р не нарушает связности графа Н, то описанное в теореме построение (Т 1б)) возможно на каждом этапе. Если же V=U, то доказательство остаётся тем же самым до тех пор, пока есть ещё рёбра, инцидентные вершине U.

Осталось  только показать, что данная процедура  всегда приводит к полной эйлеровой  цепи. Но это очевидно, так как  в G не может быть рёбер, оставшихся не пройденными после использования последнего ребра, инцидентного U. В противном случае удаление некоторого ребра, смежного одному из оставшихся, привело бы к несвязному графу, что противоречит условию 2).

 

 

 Практическая  часть

 

Задачи:

1. Существует ли эйлеров цикл в графе G. Если существует, найдите его.[2]

 

 

 

 

 

 

       Решение:

    А) Так как  каждая вершина имеет чётную  степень, то по критерию в  этом графе существует эйлеров  цикл: 1,4,6,9,10,8,5,3,2,4,7,10,11,8,6,5,2,1

    Б) В этом  графе также каждая вершина  имеет чётную степень, значит, существует и эйлеров цикл:  1,2,3,4,5,3,1,4,5,2,1

    В) Здесь каждая  вершина имеет степень 5, то  есть нечётную, следовательно, в этом графе (по критерию) нет эйлерова цикла.

2. Где на выставке следовало бы сделать вход и выход (рис.8) , чтобы можно было провести экскурсию по всем залам, побывав в каждом из них в точности один раз?[2]

 

 

 

 

 

                                                           Рис.8

Решение:

В этом графе вершины А  и В имеют степень 3, то есть нечётную, следовательно, в нём существует эйлеров путь с началом в одной из этих вершин и концом в другой. Значит, вход и выход следует установить в вершинах А и В.

. Среди приведённых ниже  графов найдите те, которые имеют  эйлеров цикл.[1]

 

 

Решение:

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

     a b e j i f c b d h j g f a c d e h g i a

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

в)  Этот граф связный, но т.к. все его вершины имеют степень 3, то есть нечётную, то он не имеет эйлерова цикла.

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

 

4. Среди приведённых ниже  графов найдите те, которые имеют  эйлеров цикл.[1]

 

Решение:

а)  Граф не является связным, то есть не выполняется первое условие  критерия, значит, он не имеет эйлерова цикла.

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

      a c f h I j k g d c b f I l j g e d a

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

г)  Граф является связным, но так как все его вершины  имеют нечётную степень, то граф не имеет эйлерова цикла.

 

5. Среди приведённых ниже  графов найдите те, которые имеют  собственный эйлеров путь.[1]

Решение:

а)  Граф связный, и только две его вершины (a и f) имеют нечётную степень, следовательно, то по теореме 3, граф имеет собственный эйлеров путь.

б)  Граф связный; deg(a)=3, deg(b)=3, deg(c)=3, то есть более двух вершин имеют нечётную степень, значит, не имеет эйлерова пути.

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

г)  Граф связный; deg(a)=3, deg(b)=4, deg(c)=1, deg(d)=3, то есть более двух вершин имеют нечётную степень, следовательно, в этом графе нет эйлерова пути.

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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

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

 

 

 

Литература

 

1. Андерсон, Джеймс А. Дискретная математика и комбинаторика: пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 960с.
2. Березина Л. Ю. Графы и их применение. – М.: Просвещение, 1979.
3. Новиков С.А. Дискретная математика для программистов – СПб.: Питер, 2001. – 304с.
4. Оре о. Графы и их применение. – М.: Мир,1973.
5. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.
6. Харари Ф. Теория графов. – М.: Мир, 1973.

 

 

 

 

 

 

 

 

 

	Страница