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