Эйлеровы графы (стр. 2 из 4)
Если снять ограничения на замкнутость цепи, то граф называется полуэйлеровым.
Теорема 1(критерий):
Граф с более чем одной вершиной имеет эйлеров цикл тогда и только тогда, когда он связный и каждая его вершина имеет чётную степень.
Доказательство: Предположим, что граф G имеет эйлеров цикл. Граф является связным, так как каждая вершина принадлежит циклу. Для всякой вершины v графа G каждый раз, когда эйлеров цикл проходит через v, он вносит 2 в степень v. Поэтому степень v чётная.
Обратно, нужно показать, что каждый связный граф, у которого степени вершин чётные, имеет эйлеров цикл. Докажем эту теорему, используя индукцию по числу вершин. Поскольку теорема тривиально справедлива при n£3, начнём индукцию с n=3. Предположим, что каждый связный граф, имеющий менее k вершин, и все вершины которого обладают чётной степенью, содержит эйлеров цикл. Пусть G – связный граф, содержащий k вершин, степени которых чётные. Допустим, что v1 и v2 - вершины графа G. Поскольку граф G – связный, существует путь из v1 в v2 .Поскольку степень v2 – чётная, существует неиспользованное ребро, по которому можно продолжить путь. Поскольку граф конечный, то путь, в конце концов, должен вернуться в v1 , и эйлеров цикл С1 можно считать построенным. Если С1 является эйлеровым циклом для G, тогда доказательство закончено. Если нет, то пусть G/ - подграф графа G, полученный удалением всех рёбер, принадлежащих С1. Поскольку С1 содержит чётное число рёбер, инцидентных каждой вершине, каждая вершина подграфа G/ имеет чётную степень.
Пусть e – ребро графа G/ , пусть Ge – компонента графа G/ , содержащая е. Поскольку G/ имеет менее, чем k, вершин, и у каждой вершины графа G/ чётная степень, граф G/ имеет эйлеров цикл. Пусть С2 . Далее у С1 и С2 имеется общая вершина, допустим, а. Теперь можно продолжить эйлеров цикл, начиная его в а, пройти С1 , вернуться в а, затем пройти С2 и вернуться в а. Если новый эйлеров цикл не является эйлеровым циклом для 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 путей, которые в совокупности содержат все рёбра графа в точности по одному разу.
Доказательство: Половину нечётных вершин обозначим А1,А2,…,Аk,другую половину В1,В2,…,Вk(рис.7). Если вершины Аi и Вi (1<i<k) соединены ребром, то удалим из графа G ребро (Аi,Вi). Если вершины А и В не соединены ребром, то добавим к G ребро (Аi,Вi). Все вершины нового графа будут чётными, то есть в новом графе найдётся эйлеров цикл. При восстановлении графа G цикл разобьется на k отдельных путей, содержащих все рёбра графа.[2]
 |
Рис.7
Пусть G=(V,E) – ориентированный граф. Ориентированным циклом называется ориентированный путь ненулевой длины из вершины в ту же вершину без повторения ребер.
Пусть G=(V,E) – ориентированный граф. Ориентированный цикл, который включает все рёбра и вершины графа G, называется эйлеровым циклом. Говорят, что ориентированный граф G имеет эйлеров цикл.
Теорема 5: Ориентированный граф имеет эйлеров цикл тогда и только тогда, когда он связный и степень входа каждой вершины равна степени выхода.[1]
Оценка числа эйлеровых графов
Лемма : В любом графе число вершин нечётной степени чётно.
Доказательство: По теореме 1 сумма степеней всех вершин число чётное. Сумма степеней вершин чётной степени чётна, значит, сумма степеней вершин нечётной степени также чётна, значит, их чётное число.
Пусть G(p) – множество всех графов с р вершинами, а Е(р) – множество эйлеровых графов с р вершинами.
Теорема 6: Эйлеровых графов почти нет, то есть
lim
Доказательство: Пусть E/ (р) – множество графов с р вершинами и чётными степенями. Тогда по теореме1 Е(р)ÌЕ/(p) и |Е(р)|£|Е/(p)|.В любом графе число вершин нечётной степени чётно, следовательно, любой граф из Е/(p) можно получить из некоторого графа G(p-1), если добавить новую вершину и соединить её со всеми старыми вершинами нечётной степени. Следовательно, |Е/(p)| £|G(p-1)|. Но |G(p)|=2C(p, 2). Заметим, что
С(k,2)-C(k-1,2)=
=
Далее имеем:
|Е(р)|£|Е/(p)| £|G(p-1)| = 2C( p-1,2) =2C(p,2)-(p-1) = |G(p)|2-(p-1)
и
, откуда lim 
. [3]Алгоритм построения эйлеровой цепи в данном эйлеровом графе.
Этот метод известен под названием алгоритма Флёри.
Теорема 7: Пусть G – эйлеров граф, тогда следующая процедура всегда возможна и приводит к эйлеровой цепи графа G. Выходя из произвольной вершины и, идём по рёбрам графа произвольным образом, соблюдая лишь следующие правила:
1) стираем рёбра по мере их прохождения и стираем также изолированные вершины, которые при этом образуются;
2) на каждом этапе идём по мосту только тогда, когда нет других возможностей.
Доказательство: Покажем сначала, что указанная процедура может быть выполнена на каждом этапе. Предположим, что мы достигли некоторой вершины V; тогда если V¹U, то оставшийся подграф H связен и содержит ровно две вершины нечётной степени, а именно U и V. Согласно теореме 3 и определению полуэйлерова графа, граф H содержит полуэйлерову цепь P из V в U. Поскольку удаление первого ребра цепи Р не нарушает связности графа Н, то описанное в теореме построение (Т 1б)) возможно на каждом этапе. Если же V=U, то доказательство остаётся тем же самым до тех пор, пока есть ещё рёбра, инцидентные вершине U.
Осталось только показать, что данная процедура всегда приводит к полной эйлеровой цепи. Но это очевидно, так как в G не может быть рёбер, оставшихся не пройденными после использования последнего ребра, инцидентного U. В противном случае удаление некоторого ребра, смежного одному из оставшихся, привело бы к несвязному графу, что противоречит условию 2).[5]
Задачи:
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]