Эйлеровость графов — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Критерий эйлеровости)
Строка 20: Строка 20:
  
 
===Критерий эйлеровости===
 
===Критерий эйлеровости===
Необходимое условия
+
Необходимое условия:
 +
 
 
1. Количество вершин нечетной степени не превосходит двух.
 
1. Количество вершин нечетной степени не превосходит двух.
 +
 
2. Все компоненты связности кроме, может быть одной, не имеют ребер.
 
2. Все компоненты связности кроме, может быть одной, не имеют ребер.
  
[[Файл:not_euler.png|300px|thumb|center| Эйлерова пути нет. Количество вершин нечетной степени больше двух.]]  
+
[[Файл:not_euler.png|200px|thumb|center| Эйлерова пути нет. Количество вершин нечетной степени больше двух.]]  
  
 
{{Теорема
 
{{Теорема

Версия 06:14, 30 ноября 2011

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

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


Эйлеров путь

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


Эйлеров цикл

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


Эйлеров граф

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


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

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

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 г.