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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
==Эйлеров путь==
 
==Эйлеров путь==
 
{{Определение|definition=
 
{{Определение|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>
+
[[Основные определения теории графов|Путь]] <tex>p</tex> <tex>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ...-> u</tex><sub><tex>k-1</tex></sub> <tex>u_k -> u_k</tex> в [[Основные определения теории графов|графе]] <tex>G = (V, E)</tex>
−
называется ''Эйлеровым'', если содержит все [[Основные определения теории графов|ребра]] <math>G</math>, причем каждое - только один раз. <br/>
+
называется ''Эйлеровым'', если содержит все [[Основные определения теории графов|ребра]] <tex>G</tex>, причем каждое - только один раз. <br/>
 
}}
 
}}
 
==Эйлеров цикл==
 
==Эйлеров цикл==
 
{{Определение|definition=
 
{{Определение|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>
+
[[Основные определения теории графов|Цикл]] <tex>p</tex> <tex>u_0 -> u_0u_1 -> u_1 -> u_1u_2 -> ...-> u_ku_0-> u_0</tex> в графе <tex>G = (V, E)</tex>
−
называется ''Эйлеровым'', если содержит все ребра <math>G</math>, причем каждое - только один раз. <br/>
+
называется ''Эйлеровым'', если содержит все ребра <tex>G</tex>, причем каждое - только один раз. <br/>
 
}}
 
}}
−
'''Эквивалентно:'''
+
==Эквивалентное определение Эйлерова цикла==
 +
{{Определение|definition=
 
Эйлеровым циклом является Эйлеров путь, являющийся циклом.
 
Эйлеровым циклом является Эйлеров путь, являющийся циклом.
 +
}}
  
 
==Эйлеров граф==
 
==Эйлеров граф==
 
{{Определение|definition=
 
{{Определение|definition=
−
Граф <math>G = (V, E)</math> называется Эйлеровым, если содержит Эйлеров цикл. Граф, содержащий Эйлеров путь, не являющийся циклом, называют полуэйлеровым. <br/>
+
Граф <tex>G = (V, E)</tex> называется Эйлеровым, если содержит Эйлеров цикл. Граф, содержащий Эйлеров путь, не являющийся циклом, называют полуэйлеровым. <br/>
 
}}
 
}}
  
Строка 25: Строка 27:
 
Неориентированный граф назовем почти связным, если все его [[Отношение_связности,_компоненты_связности|компоненты связности]], кроме, быть может, одной, имеют размер 1.<br/>
 
Неориентированный граф назовем почти связным, если все его [[Отношение_связности,_компоненты_связности|компоненты связности]], кроме, быть может, одной, имеют размер 1.<br/>
 
Ориентированный граф назовем почти связным, если все его [[Отношение_связности,_компоненты_связности|компоненты слабой связности]], кроме, быть может, одной, имеют размер 1.
 
Ориентированный граф назовем почти связным, если все его [[Отношение_связности,_компоненты_связности|компоненты слабой связности]], кроме, быть может, одной, имеют размер 1.
−
</ref> граф <math>G = (V, E)</math> является Эйлеровым тогда и только тогда, когда не содержит вершин нечетной [[Основные определения теории графов|степени]].<br/>
+
</ref> граф <tex>G = (V, E)</tex> является Эйлеровым тогда и только тогда, когда не содержит вершин нечетной [[Основные определения теории графов|степени]].<br/>
 
|
 
|
 
proof=
 
proof=
 
'''Достаточность:'''
 
'''Достаточность:'''
 
<br/>
 
<br/>
−
Рассмотрим Эйлеров цикл <math>p</math> в <math>G</math>.
+
Рассмотрим Эйлеров цикл <tex>p</tex> в <tex>G</tex>.
 
Каждое вхождение вершины в цикл(кроме первого и последнего вхождения начальной вершины) добавляет 2 к ее степени.<br/>
 
Каждое вхождение вершины в цикл(кроме первого и последнего вхождения начальной вершины) добавляет 2 к ее степени.<br/>
 
Для начальной вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени. В итоге, каждая вершина имеет четную степень.
 
Для начальной вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени. В итоге, каждая вершина имеет четную степень.
Строка 38: Строка 40:
 
Докажем утверждение по индукции.<br><br/>
 
Докажем утверждение по индукции.<br><br/>
 
''База:''<br/>  
 
''База:''<br/>  
−
Лес из <math>N</math> деревьев, каждое из 1 вершины.<br/><br/>
+
Лес из <tex>N</tex> деревьев, каждое из 1 вершины.<br/><br/>
 
''Переход:''<br/>
 
''Переход:''<br/>
 
Рассмотри граф, в котором степени всех вершин четные.<br/>
 
Рассмотри граф, в котором степени всех вершин четные.<br/>
 
В нем найдется простой цикл, т.к. иначе граф является [[Дерево, эквивалентные определения|лесом]], и тогда в нем есть хотя бы два листа, что противоречит четности степеней всех вершин.
 
В нем найдется простой цикл, т.к. иначе граф является [[Дерево, эквивалентные определения|лесом]], и тогда в нем есть хотя бы два листа, что противоречит четности степеней всех вершин.
−
Рассмотрим цикл <math>c</math> такой, что при удалении его ребер не образуется двух компонент связности размера больше 1.
+
Рассмотрим цикл <tex>c</tex> такой, что при удалении его ребер не образуется двух компонент связности размера больше 1.
−
Такой всегда существует, т.к. [[Граф_блоков-точек_сочленения|граф блоков и точек сочленения]] произвольного почти связного графа является [[Дерево, эквивалентные определения|деревом]], а т.к. все вершины <math>G</math> имеют четные степени, то не могут являться в нем листами. Значит, листами в дереве блоков и точек сочленения такого графа будут циклы, а в любом цикле есть подмножество, являющееся простым циклом.
+
Такой всегда существует, т.к. [[Граф_блоков-точек_сочленения|граф блоков и точек сочленения]] произвольного почти связного графа является [[Дерево, эквивалентные определения|деревом]], а т.к. все вершины <tex>G</tex> имеют четные степени, то не могут являться в нем листами. Значит, листами в дереве блоков и точек сочленения такого графа будут циклы, а в любом цикле есть подмножество, являющееся простым циклом.
  
−
Рассмотрим вершину <math>u</math> со степенью больше 2. После удаления цикла <math>c</math> из графа степени всех вершин останутся четными,
+
Рассмотрим вершину <tex>u</tex> со степенью больше 2. После удаления цикла <tex>c</tex> из графа степени всех вершин останутся четными,
−
при этом количество ребер в графе уменьшится. Для <math>G - c</math>, по предположению индукции, существует эйлеров цикл <math>e</math>.
+
при этом количество ребер в графе уменьшится. Для <tex>G - c</tex>, по предположению индукции, существует эйлеров цикл <tex>e</tex>.
−
Тогда в <math>G</math> тоже существует Эйлеров обход - сначала обойти цикл с, начиная с вершины <math>u</math>, затем обойти <math>e</math>.<br/>
+
Тогда в <tex>G</tex> тоже существует Эйлеров обход - сначала обойти цикл с, начиная с вершины <tex>u</tex>, затем обойти <tex>e</tex>.<br/>
 
Переход доказан.
 
Переход доказан.
 
}}
 
}}
 
'''Следствие'''<br/>
 
'''Следствие'''<br/>
−
Неориентированный почти связный<ref name = "almost"/> граф <math>G = (V, E)</math> является полуэйлеровым тогда и только тогда, когда содержит ровно две вершины нечетной степени.<br/>
+
Неориентированный почти связный<ref name = "almost"/> граф <tex>G = (V, E)</tex> является полуэйлеровым тогда и только тогда, когда содержит ровно две вершины нечетной степени.<br/>
  
 
====[[Основные определения теории графов|Ориентированный граф]]====
 
====[[Основные определения теории графов|Ориентированный граф]]====
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
−
Ориентированный почти связный<ref name = "almost"/> граф <math>G = (V, E) </math> является Эйлеровым тогда и только тогда, когда входная степень любой вершины равна ее выходной степени.<br/>
+
Ориентированный почти связный<ref name = "almost"/> граф <tex>G = (V, E) </tex> является Эйлеровым тогда и только тогда, когда входная степень любой вершины равна ее выходной степени.<br/>
 
|proof=
 
|proof=
 
Аналогично неориентированному графу.
 
Аналогично неориентированному графу.
Строка 63: Строка 65:
 
<br/>
 
<br/>
 
'''Следствие'''<br/>
 
'''Следствие'''<br/>
−
Ориентированный почти связный<ref name = "almost"/> граф <math>G = (V, E)</math> является полуэйлеровым тогда и только тогда, когда содержит ровно одну вершину, [[Основные_определения_теории_графов|входная степень]] которой на единицу больше [[Основные_определения_теории_графов|выходной]], и ровно одну вершину, выходная степень которой на единицу больше входной.<br/>
+
Ориентированный почти связный<ref name = "almost"/> граф <tex>G = (V, E)</tex> является полуэйлеровым тогда и только тогда, когда содержит ровно одну вершину, [[Основные_определения_теории_графов|входная степень]] которой на единицу больше [[Основные_определения_теории_графов|выходной]], и ровно одну вершину, выходная степень которой на единицу больше входной.<br/>
  
 
== Примечания ==
 
== Примечания ==

Версия 23:37, 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 г.

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Эйлеровость_графов&oldid=3856»