Курсовая работа: Эйлеровы графы
Доказательство: Вершины А и В могут быть соединены ребром в графе, а могут быть соединены.
Если А и В соединены ребром, то удалим его; тогда все вершины станут чётными. Новый граф (по теореме 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]
Глава 2. Практическая часть
Задачи:
1. Существует ли эйлеров цикл в графе G. Если существует, найдите его.[2]
 |  | |
 | ||