Эйлеровость графов

Материал из Викиконспекты
Версия от 06:22, 30 ноября 2011; 192.168.0.2 (обсуждение) (Критерий эйлеровости)
Перейти к: навигация, поиск

Эйлеров обход

Определение:
Эйлеров обход - обход графа, посещающий эйлеров путь.


Эйлеров путь

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


Эйлеров цикл

Определение:
Эйлеров цикл - эйлеров путь, который является циклом.


Эйлеров граф

Определение:
Граф называется эйлеровым, если он содержит эйлеров цикл. Граф, содержащий эйлеров путь, не являющийся циклом, называют полуэйлеровым.


Критерий эйлеровости

Необходимое условия:

1. Количество вершин нечетной степени не превосходит двух.

2. Все компоненты связности кроме, может быть одной, не имеют ребер.

Эйлерова пути нет. Количество вершин нечетной степени больше двух.
Теорема:
Неориентированный почти связный граф [math]G = (V, E)[/math] является эйлеровым тогда и только тогда, когда не содержит вершин нечетной степени.
Доказательство:
[math]\triangleright[/math]

Достаточность:

Рассмотрим эйлеров цикл [math]p[/math] в [math]G[/math]. Каждое вхождение вершины в цикл(кроме первого и последнего вхождения начальной вершины) добавляет 2 к ее степени.
Для начальной вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени. В итоге, каждая вершина имеет четную степень.

Необходимость:

Докажем утверждение по индукции.

База:
Лес из [math]N[/math] деревьев, каждое из 1 вершины.

Переход:
Рассмотри граф, в котором степени всех вершин четные.

В нем найдется простой цикл, т.к. иначе граф является лесом, и тогда в нем есть хотя бы два листа, что противоречит четности степеней всех вершин. Рассмотрим цикл [math]c[/math] такой, что при удалении его ребер не образуется двух компонент связности размера больше 1. Такой всегда существует, т.к. граф блоков и точек сочленения произвольного почти связного графа является деревом, а т.к. все вершины [math]G[/math] имеют четные степени, то не могут являться в нем листами. Значит, листами в дереве блоков и точек сочленения такого графа будут циклы, а в любом цикле есть подмножество, являющееся простым циклом.

Рассмотрим вершину [math]u[/math] со степенью больше 2. После удаления цикла [math]c[/math] из графа степени всех вершин останутся четными, при этом количество ребер в графе уменьшится. Для [math]G - c[/math], по предположению индукции, существует эйлеров цикл [math]e[/math]. Тогда в [math]G[/math] тоже существует эйлеров обход - сначала обойти цикл [math]c[/math], начиная с вершины [math]u[/math], затем обойти [math]e[/math].

Переход доказан.
[math]\triangleleft[/math]

Следствие

Неориентированный почти связный граф [math]G = (V, E)[/math] является полуэйлеровым тогда и только тогда, когда содержит ровно две вершины нечетной степени.

Ориентированный граф

Теорема:
Ориентированный почти связный граф [math]G = (V, E) [/math] является эйлеровым тогда и только тогда, когда входная степень любой вершины равна ее выходной степени.
Доказательство:
[math]\triangleright[/math]
Аналогично неориентированному графу.
[math]\triangleleft[/math]


Следствие
Ориентированный почти связный граф [math]G = (V, E)[/math] является полуэйлеровым тогда и только тогда, когда содержит ровно одну вершину, входная степень которой на единицу больше выходной, и ровно одну вершину, выходная степень которой на единицу больше входной.

Источники

1. Ф.Харари. Теория графов. Москва, издательство "Едиториал УРСС". 2003 г.