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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
==Эйлеров путь==
 
==Эйлеров путь==
 +
{{Определение|definition=
 
[[Основные определения теории графов|Путь]] <math>p</math> <math>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ...-> u</math><sub><math>k-1</math></sub> <math>u_k -> u_k</math> в [[Основные определения теории графов|графе]] <math>G = (V, E)</math>
 
[[Основные определения теории графов|Путь]] <math>p</math> <math>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ...-> u</math><sub><math>k-1</math></sub> <math>u_k -> u_k</math> в [[Основные определения теории графов|графе]] <math>G = (V, E)</math>
 
называется ''Эйлеровым'', если содержит все [[Основные определения теории графов|ребра]] <math>G</math>, причем каждое - только один раз. <br/>
 
называется ''Эйлеровым'', если содержит все [[Основные определения теории графов|ребра]] <math>G</math>, причем каждое - только один раз. <br/>
 
+
}}
 
==Эйлеров цикл==
 
==Эйлеров цикл==
 
+
{{Определение|definition=
 
[[Основные определения теории графов|Цикл]] <math>p</math> <math>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ...-> u_ku_0-> u_0</math> в графе <math>G = (V, E)</math>
 
[[Основные определения теории графов|Цикл]] <math>p</math> <math>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ...-> u_ku_0-> u_0</math> в графе <math>G = (V, E)</math>
 
называется ''Эйлеровым'', если содержит все ребра <math>G</math>, причем каждое - только один раз. <br/>
 
называется ''Эйлеровым'', если содержит все ребра <math>G</math>, причем каждое - только один раз. <br/>
 
+
}}
 
'''Эквивалентно:'''
 
'''Эквивалентно:'''
 
Эйлеровым циклом является Эйлеров путь, являющийся циклом.
 
Эйлеровым циклом является Эйлеров путь, являющийся циклом.
  
 
==Эйлеров граф==
 
==Эйлеров граф==
===Определение===
+
{{Определение|definition=
 
Граф <math>G = (V, E)</math> называется Эйлеровым, если содержит Эйлеров цикл. Граф, содержащий Эйлеров путь, не являющийся циклом, называют полуэйлеровым. <br/>
 
Граф <math>G = (V, E)</math> называется Эйлеровым, если содержит Эйлеров цикл. Граф, содержащий Эйлеров путь, не являющийся циклом, называют полуэйлеровым. <br/>
 +
}}
  
 
===Критерий Эйлеровости===
 
===Критерий Эйлеровости===

Версия 23:32, 13 октября 2010

Эйлеров путь

Определение:
Путь [math]p[/math] [math]u_0 -\gt u_0u_1 -\gt u_1 -\gt u_1u_2 -\gt ...-\gt u[/math][math]k-1[/math] [math]u_k -\gt u_k[/math] в графе [math]G = (V, E)[/math] называется Эйлеровым, если содержит все ребра [math]G[/math], причем каждое - только один раз.

Эйлеров цикл

Определение:
Цикл [math]p[/math] [math]u_0 -\gt u_0u_1 -\gt u_1 -\gt u_1u_2 -\gt ...-\gt u_ku_0-\gt u_0[/math] в графе [math]G = (V, E)[/math] называется Эйлеровым, если содержит все ребра [math]G[/math], причем каждое - только один раз.

Эквивалентно: Эйлеровым циклом является Эйлеров путь, являющийся циклом.

Эйлеров граф

Определение:
Граф [math]G = (V, E)[/math] называется Эйлеровым, если содержит Эйлеров цикл. Граф, содержащий Эйлеров путь, не являющийся циклом, называют полуэйлеровым.


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

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

Теорема:
Неориентированный почти связный [1] граф [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]u[/math], затем обойти [math]e[/math].

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

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

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

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


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

Примечания

  1. 1,0 1,1 1,2 1,3 Неориентированный граф назовем почти связным, если все его компоненты связности, кроме, быть может, одной, имеют размер 1.
    Ориентированный граф назовем почти связным, если все его компоненты слабой связности, кроме, быть может, одной, имеют размер 1.

Источники

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