Эйлеров Граф

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

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

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

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

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

Теорема 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 отдельных путей, содержащих все рёбра графа.[2]

 
                                                          

 

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

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

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

 

                              Критерии существования Эйлерова цикла

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

Теорема 1. Чтобы в связанном неориентированном графе G существовал эйлеров цикл, необходимо и достаточно, чтобы число вершин нечетной степени было четным.

Доказательство.

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

Достаточность. Пусть G — связный неориентированный граф, все вершины которого имеют четную степень. Начнем путь из некоторой произвольной вершины x₀ и пойдем по некоторому ранее не использованному ребру к следующей вершине, и так до тех пор, пока не вернемся в вершину x₀ и не замкнем цикл. Если все ребра окажутся использованными, то нужный эйлеров цикл построен. Если же некоторые ребра не использованы, то пусть Ф — только что построенный цикл. Так как граф G связен, то цикл Ф должен проходить через некоторую вершину, скажем x_i, являющуюся конечной вершиной какого-либо до сих пор не использованного ребра. Если удалить все ребра, принадлежащие Ф, то в оставшемся графе все вершины по-прежнему будут иметь четную степень, так как в цикле Ф должно быть четное число ребер (0 является четным числом), инцидентных каждой вершине.

Начиная теперь с x_i, получаем цикл Ф’, начинающийся и оканчивающийся в x_i. Если все оставшиеся ранее ребра использованы для цикла Ф’, то процесс окончен. Нужный эйлеров цикл будет образован частью цикла Ф от вершины x₀ до x_i, затем циклом Ф’ и, наконец, частью цикла Ф от вершины x_i до x₀. Если же все еще остались неиспользованные ребра, то объединение построенных выше циклов Ф и Ф’ дает новый цикл Ф. Мы снова можем найти вершину x_j, принадлежащую циклу и являющуюся концевой вершиной некоторого неиспользованного ребра. Затем мы можем приступить к построению нового цикла Ф’, начинавшегося в x_j, и так до тех пор, пока не будут использованы все ребра и не будет получен таким образом эйлеров цикл Ф. Это доказывает теорему.

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

Следствие #1.

Для связного эйлерова графа G множество ребер можно разбить на простые циклы.

Следствие #2.

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

                                          Теорема Эйлера

В доказательстве теорем Коши и Александрова используется теорема  Эйлера. Эта знаменитая теорема впервые  появилась в 1752 году в журнале  Петербургской академии наук в работах  Леонарда Эйлера 1 "Элементы учения о телах" и "Доказательство некоторых замечательных свойств, которым подчинены тела, ограниченные плоскими гранями".

Теорема Эйлера. Пусть В --- число вершин выпуклого многогранника, Р --- число его ребер и Г --- число граней. Тогда верно равенство 

В-Р+Г=2.

 

Число  =В-Р+Г называется эйлеровой характеристикой многогранника. Согласно теореме Эйлера, для выпуклого многогранника эта характеристика равна 2. То что эйлерова характеристика равна 2 для некоторых знакомых нам многогранников, видно из таблицы.

Многогранник	В	Р	Г
Тетраэдр	4	6	4	2
Октаэдр	6	12	8	2
Параллелепипед	8	12	6	2
n-угольная пирамида	n+1	2n	n+1	2
n-угольная призма	2n	3n	n+2	2

 

Рис. 21.

Для доказательства теоремы  Эйлера возьмем произвольную грань F₁ многогранника, а также смежную с ней по ребру грань F₂. Подчеркнем, что эту пару граней ограничивает связный (т. е. состоящий из одного куска) несамопересекающийся контур из ребер этих граней. Выберем третью грань F₃, которая прилегает к этой паре по некоторому связному куску ломаной, состоящей из ребер (рис. 21). Это, как нетрудно увидеть, всегда можно сделать. Тогда граница тройки этих граней тоже представляет собой связный несамопересекающийся контур. Легко показать, что к уже отобранным граням можно присоединить четвертую грань, затем пятую и т. д. так, чтобы получающаяся на очередном шаге совокупность граней F₁, F₂, ..., F_i была ограничена связным несамопересекающимся контуром.

Подсчитывать эйлерову характеристику многогранника будем поэтапно. На первом этапе вклад грани F₁ в эйлерову характеристику, т. е. число вершин грани минус число ее ребер (такое же) плюс число граней (в данном случае равное 1), равен 1. Присоединяя новую грань F₂, мы прибавляем некоторое число новых вершин, отнимаем число (меньшее числа вершин на единицу) новых ребер и прибавляем единицу, соответствующую новой грани. В итоге, вклад в эйлерову характеристику на втором этапе нулевой. Так как присоединяемая на каждом этапе грань имеет с предыдущими гранями общую границу в виде одной связной ломаной, то на каждом шаге (за исключением последнего) число новых вершин на единицу меньше числа новых ребер. Поэтому на каждом шаге, начиная со второго вплоть до предпоследнего, вклад в эйлерову характеристику нулевой. Присоединение последней грани не дает ни новых вершин, ни новых ребер, добавляя в эйлеровой характеристике к уже имеющейся единице еще одну, соответствующую последней грани. Таким образом, на последнем этапе мы получаем эйлерову характеристику многогранника, равную 2.

 

Рис. 22.

Теорема Эйлера имеет огромное значение в геометрии. Эта теорема  породила новое направление в  математике --- топологию. Эйлерова характеристика не зависит ни от длин ребер, ни от площадей граней, ни от каких-либо углов многогранника. Эйлерова характеристика равна 2 независимо от того, выпуклый это многогранник или нет. Главное --- чтобы поверхность этого многогранника не имела дыр и была " похожа" на сферу, а не на рамку (рис. 22). Для многогранника, " похожего" на рамку, эйлерова характеристика равна 0.

 

                                                   Заключение

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

 

                                     Список Литературы

Харари Ф. Теория графов. – М.: Мир, 1973, http://www.mccme.ru ,