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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 136 промежуточных версий 12 участников)
Строка 1: Строка 1:
−
==Эйлеров путь==
+
==Основные определения==
−
[[Основные определения теории графов|Путь]] <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>
+
{{Определение|definition=
−
называется ''Эйлеровым'', если содержит все [[Основные определения теории графов|ребра]] <math>G</math>, причем каждое - только один раз. <br/>
+
'''Эйлеровым путем''' (англ. ''Eulerian path'') в графе называется [[Основные определения теории графов|путь]], который проходит по каждому ребру, причем ровно один раз.
 +
}}
 +
 
 +
{{Определение|definition=
 +
'''Эйлеров обход''' (англ. ''Eulerian circuit'') {{---}} обход графа, посещающий эйлеров путь.
 +
}}
 +
 
 +
{{Определение|definition=
 +
'''Эйлеров цикл''' (англ. ''Eulerian cycle'') {{---}} замкнутый эйлеров путь.
 +
}}
  
−
==Эйлеров цикл==
+
{{Определение
 +
|id = euler_graph
 +
|definition=
 +
Граф называется '''эйлеровым''' (англ. ''Eulerian graph''), если он содержит эйлеров цикл. Граф называется '''полуэйлеровым''', если он содержит эйлеров путь, но не содержит эйлеров цикл.
 +
}}
  
−
[[Основные определения теории графов|Цикл]] <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/>
+
{{Теорема
 +
|id = eulerTheorem
 +
|statement=
 +
Для того, чтобы граф <tex>G = (V, E) </tex> был эйлеровым необходимо чтобы:
 +
1. Все вершины имели четную степень.
  
−
'''Эквивалентно:'''
+
2. Все компоненты связности, кроме, может быть, одной, не содержали ребер.
−
Эйлеровым циклом является Эйлеров путь, являющийся циклом.
+
|proof=
 +
1. Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два (помечаем уже пройденые ребра), если эта вершина не является стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение неверно.
  
−
==Эйлеров граф==
+
2. Если в графе существует более одной компоненты связности с ребрами, то очевидно, что нельзя пройти по их ребрам одним путем.
−
===Определение===
+
}}
−
Граф <math>G = (V, E)</math> называется Эйлеровым, если содержит Эйлеров цикл. Граф, содержащий Эйлеров путь, не являющийся циклом, называют полуэйлеровым. <br/>
 
  
−
===Критерий Эйлеровости===
+
[[Файл:Euler_path_1.png|160px|thumb|left|Эйлерова пути нет.<br>Количество вершин нечетной степени больше двух.]]
−
====[[Основные определения теории графов|Неориентированный граф]]====
+
[[Файл:Euler_path_2.png|230px|thumb|none|Две компоненты связности, одна имеет ребра.]]
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
−
Неориентированный почти связный <ref name = "almost">
+
В графе <tex>G = (V, E) </tex> существует эйлеров цикл тогда и только тогда, когда:
−
Неориентированный граф назовем почти связным, если все его [[Отношение_связности,_компоненты_связности|компоненты связности]], кроме, быть может, одной, имеют размер 1.<br/>
+
 
−
Ориентированный граф назовем почти связным, если все его [[Отношение_связности,_компоненты_связности|компоненты слабой связности]], кроме, быть может, одной, имеют размер 1.
+
1. Все вершины имеют четную степень.
−
</ref> граф <math>G = (V, E)</math> является Эйлеровым тогда и только тогда, когда не содержит вершин нечетной [[Основные определения теории графов|степени]].<br/>
+
 
−
|
+
2. Все компоненты связности, кроме, может быть, одной, не содержат ребер.
−
proof=
+
 
−
'''Достаточность:'''
+
|proof=
−
<br/>
+
 
−
Рассмотрим Эйлеров цикл <math>p</math> в <math>G</math>.
+
Необходимость мы доказали ранее. Докажем достаточность, используя индукцию по числу вершин <tex>n</tex>.
−
Каждое вхождение вершины в цикл(кроме первого и последнего вхождения начальной вершины) добавляет 2 к ее степени.<br/>
 
−
Для начальной вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени. В итоге, каждая вершина имеет четную степень.
 
−
<br/>
 
−
'''Необходимость:'''
 
−
<br/>
 
−
Докажем утверждение по индукции.<br><br/>
 
−
''База:''<br/>
 
−
Лес из <math>N</math> деревьев, каждое из 1 вершины.<br/><br/>
 
−
''Переход:''<br/>
 
−
Рассмотри граф, в котором степени всех вершин четные.<br/>
 
−
В нем найдется простой цикл, т.к. иначе граф является лесом, и тогда в нем есть хотя бы два листа, что противоречит четности степеней всех вершин.
 
−
Рассмотрим цикл <math>c</math> такой, что при удалении его ребер не образуется двух компонент связности размера больше 1.
 
−
Такой всегда существует, т.к. [[Граф_блоков-точек_сочленения|граф блоков и точек сочленения]] произвольного почти связного графа является деревом, а т.к. все вершины <math>G</math> имеют четные степени, то не могут являться в нем листами. Значит, листами в дереве блоков и точек сочленения такого графа будут циклы, а в любом цикле есть подмножество, являющееся простым циклом.
 
  
−
Рассмотрим вершину <math>u</math> со степенью больше 2. После удаления цикла <math>c</math> из графа степени всех вершин останутся четными,
+
База индукции: <tex>n = 0</tex> цикл существует.
−
при этом количество ребер в графе уменьшится. Для <math>G - c</math>, по предположению индукции, существует эйлеров цикл <math>e</math>.
+
 
−
Тогда в <math>G</math> тоже существует Эйлеров обход - сначала обойти цикл с, начиная с вершины <math>u</math>, затем обойти <math>e</math>.<br/>
+
Предположим что граф имеющий менее <tex>n</tex> вершин содержит эйлеров цикл.
−
Переход доказан.
+
 
 +
Рассмотрим связный граф <tex>G = (V, E)</tex> с <tex>n > 0</tex> вершинами, степени которых четны.
 +
 
 +
Пусть <tex>v_1</tex> и <tex>v_2</tex> {{---}} вершины графа. Поскольку граф связный, то существует путь из <tex>v_1</tex> в <tex>v_2</tex>. Степень <tex>v_2</tex> {{---}} чётная, значит существует неиспользованное ребро, по которому можно продолжить путь из <tex>v_2</tex>. Так как граф конечный, то путь, в конце концов, должен вернуться в <tex>v_1</tex>, следовательно мы получим замкнутый путь (цикл). Назовем этот цикл <tex>C_1</tex>. Будем продолжать строить <tex>C_1</tex> через <tex>v_1</tex> таким же образом, до тех пор, пока мы в очередной раз не сможем выйти из вершины <tex>v_1</tex>, то есть <tex>C_1</tex> будет покрывать все ребра, инцидентные  <tex>v_1</tex>. Если <tex>C_1</tex> является эйлеровым циклом для <tex>G</tex>, тогда доказательство закончено. Если нет, то пусть <tex>G'</tex> {{---}} подграф графа <tex>G</tex>, полученный удалением всех рёбер, принадлежащих <tex>C_1</tex>. Поскольку <tex>C_1</tex> содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа <tex>G'</tex> имеет чётную степень. А так как <tex>C_1</tex> покрывает все ребра, инцидентные <tex>v_1</tex>, то граф <tex>G'</tex> будет состоять из нескольких компонент связности.
 +
 
 +
Рассмотрим какую-либо компоненту связности <tex>G'</tex>. Поскольку рассматриваемая компонента связности <tex>G'</tex> имеет менее, чем <tex>n</tex> вершин, а у каждой вершины графа <tex>G'</tex> чётная степень, то у каждой компоненты связности <tex>G'</tex> существует эйлеров цикл. Пусть для рассматриваемой компоненты связноти это цикл <tex>C_2</tex>. У <tex>C_1</tex> и <tex>C_2</tex> имеется общая вершина <tex>a</tex>, так как <tex>G</tex> cвязен. Теперь можно обойти эйлеров цикл, начиная его в вершине <tex>a</tex>, обойти <tex>C_1</tex> , вернуться в <tex>a</tex>, затем пройти <tex>C_2</tex> и вернуться в <tex>a</tex>. Если новый эйлеров цикл не является эйлеровым циклом для <tex>G</tex>, продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для <tex>G</tex>.
 +
 
 +
}}
 +
{{Теорема
 +
|about=следствие
 +
|statement=
 +
В графе <tex>G = (V, E) </tex> существует эйлеров путь тогда и только тогда, когда:
 +
1. Количество вершин с нечетной степенью меньше или равно двум.
 +
2. Все компоненты связности кроме, может быть одной, не содержат ребер.
 +
|proof=
 +
Добавим ребро, соединяющее вершины с нечетной степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.
 
}}
 
}}
−
'''Следствие'''<br/>
 
−
Неориентированный почти связный<ref name = "almost"/> граф <math>G = (V, E)</math> является полуэйлеровым тогда и только тогда, когда содержит ровно две вершины нечетной степени.<br/>
 
  
 
====[[Основные определения теории графов|Ориентированный граф]]====
 
====[[Основные определения теории графов|Ориентированный граф]]====
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
−
Ориентированный почти связный<ref name = "almost"/> граф <math>G = (V, E) </math> является Эйлеровым тогда и только тогда, когда входная степень любой вершины равна ее выходной степени.<br/>
+
В ориентированном графе <tex>G = (V, E) </tex> существует эйлеров цикл тогда и только тогда, когда:
 +
 
 +
1. Входная степень любой вершины равна ее выходной степени.
 +
 
 +
2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
 
|proof=
 
|proof=
−
Аналогично неориентированному графу.
+
Доказательство аналогично случаю неориентированного графа.
 
}}
 
}}
  
−
<br/>
+
{{Теорема
−
'''Следствие'''<br/>
+
|about=
−
Ориентированный почти связный<ref name = "almost"/> граф <math>G = (V, E)</math> является полуэйлеровым тогда и только тогда, когда содержит ровно одну вершину, [[Основные_определения_теории_графов|входная степень]] которой на единицу больше [[Основные_определения_теории_графов|выходной]], и ровно одну вершину, выходная степень которой на единицу больше входной.<br/>
+
cледствие
 +
|statement=В ориентированном графе <tex>G = (V, E)</tex> существует эйлеров путь если:
 +
1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа, для одной из которых <tex>\operatorname{deg}^+ - \operatorname{deg}^- = 1</tex>, а для другой <tex>\operatorname{deg}^+ - \operatorname{deg}^- = -1</tex>.
 +
2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
 +
|proof=Соединим ориентированным ребром вершину с большей входящей степенью с вершиной с большей исходящей степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.
 +
}}
 +
 
 +
==См. также==
 +
 
 +
* [[Алгоритм построения Эйлерова цикла]]
 +
 
 +
== Источники информации==
  
−
== Примечания ==
+
* Ф.Харари Теория графов. Глава 7. Обходы графов. Эйлеровы графы.
−
<references/>
+
* Уилсон Р. Введение в теорию графов. {{---}} М.: Мир, 1977
 +
* [http://e-maxx.ru/algo/euler_path Нахождение эйлерова пути]
  
−
==Источники==
+
[[Категория: Алгоритмы и структуры данных]]
−
1. Ф.Харари. Теория графов. Москва, издательство "Едиториал УРСС". 2003 г.
+
[[Категория: Обходы графов]]
 +
[[Категория: Эйлеровы графы]]

Текущая версия на 19:18, 4 сентября 2022

Основные определения

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


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


Определение:
Эйлеров цикл (англ. Eulerian cycle) — замкнутый эйлеров путь.


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


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

Теорема:
Для того, чтобы граф [math]G = (V, E) [/math] был эйлеровым необходимо чтобы:

1. Все вершины имели четную степень.

2. Все компоненты связности, кроме, может быть, одной, не содержали ребер.
Доказательство:
[math]\triangleright[/math]

1. Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два (помечаем уже пройденые ребра), если эта вершина не является стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение неверно.

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

1. Все вершины имеют четную степень.

2. Все компоненты связности, кроме, может быть, одной, не содержат ребер.
Доказательство:
[math]\triangleright[/math]

Необходимость мы доказали ранее. Докажем достаточность, используя индукцию по числу вершин [math]n[/math].

База индукции: [math]n = 0[/math] цикл существует.

Предположим что граф имеющий менее [math]n[/math] вершин содержит эйлеров цикл.

Рассмотрим связный граф [math]G = (V, E)[/math] с [math]n \gt 0[/math] вершинами, степени которых четны.

Пусть [math]v_1[/math] и [math]v_2[/math] — вершины графа. Поскольку граф связный, то существует путь из [math]v_1[/math] в [math]v_2[/math]. Степень [math]v_2[/math] — чётная, значит существует неиспользованное ребро, по которому можно продолжить путь из [math]v_2[/math]. Так как граф конечный, то путь, в конце концов, должен вернуться в [math]v_1[/math], следовательно мы получим замкнутый путь (цикл). Назовем этот цикл [math]C_1[/math]. Будем продолжать строить [math]C_1[/math] через [math]v_1[/math] таким же образом, до тех пор, пока мы в очередной раз не сможем выйти из вершины [math]v_1[/math], то есть [math]C_1[/math] будет покрывать все ребра, инцидентные [math]v_1[/math]. Если [math]C_1[/math] является эйлеровым циклом для [math]G[/math], тогда доказательство закончено. Если нет, то пусть [math]G'[/math] — подграф графа [math]G[/math], полученный удалением всех рёбер, принадлежащих [math]C_1[/math]. Поскольку [math]C_1[/math] содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа [math]G'[/math] имеет чётную степень. А так как [math]C_1[/math] покрывает все ребра, инцидентные [math]v_1[/math], то граф [math]G'[/math] будет состоять из нескольких компонент связности.

Рассмотрим какую-либо компоненту связности [math]G'[/math]. Поскольку рассматриваемая компонента связности [math]G'[/math] имеет менее, чем [math]n[/math] вершин, а у каждой вершины графа [math]G'[/math] чётная степень, то у каждой компоненты связности [math]G'[/math] существует эйлеров цикл. Пусть для рассматриваемой компоненты связноти это цикл [math]C_2[/math]. У [math]C_1[/math] и [math]C_2[/math] имеется общая вершина [math]a[/math], так как [math]G[/math] cвязен. Теперь можно обойти эйлеров цикл, начиная его в вершине [math]a[/math], обойти [math]C_1[/math] , вернуться в [math]a[/math], затем пройти [math]C_2[/math] и вернуться в [math]a[/math]. Если новый эйлеров цикл не является эйлеровым циклом для [math]G[/math], продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для [math]G[/math].
[math]\triangleleft[/math]
Теорема (следствие):
В графе [math]G = (V, E) [/math] существует эйлеров путь тогда и только тогда, когда:

1. Количество вершин с нечетной степенью меньше или равно двум.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.
Доказательство:
[math]\triangleright[/math]
Добавим ребро, соединяющее вершины с нечетной степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.
[math]\triangleleft[/math]

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

Теорема:
В ориентированном графе [math]G = (V, E) [/math] существует эйлеров цикл тогда и только тогда, когда:

1. Входная степень любой вершины равна ее выходной степени.

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

1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа, для одной из которых [math]\operatorname{deg}^+ - \operatorname{deg}^- = 1[/math], а для другой [math]\operatorname{deg}^+ - \operatorname{deg}^- = -1[/math].

2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
Доказательство:
[math]\triangleright[/math]
Соединим ориентированным ребром вершину с большей входящей степенью с вершиной с большей исходящей степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.
[math]\triangleleft[/math]

См. также

Источники информации

  • Ф.Харари Теория графов. Глава 7. Обходы графов. Эйлеровы графы.
  • Уилсон Р. Введение в теорию графов. — М.: Мир, 1977
  • Нахождение эйлерова пути
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Эйлеровость_графов&oldid=84843»