105
правок
Изменения
Нет описания правки
==Эйлеров путь==
[[Основные определения теории графов|Путь ]] <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>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/>
===Критерий Эйлеровости===
====[[Основные определения теории графов|Неориентированный граф]]====
{{Теорема
|statement=
Неориентированный почти связный <ref name = "almost">
Неориентированный граф назовем почти связным, если все его [[Отношение_связности,_компоненты_связности|компоненты связности]], кроме, быть может, одной, имеют размер 1.<br/>Ориентированный граф назовем почти связным, если все его [[Отношение_связности,_компоненты_связности|компоненты слабой связности]], кроме, быть может, одной, имеют размер 1.</ref> граф <math>G = (V, E)</math> является Эйлеровым тогда и только тогда, когда не содержит вершин нечетной [[Основные определения теории графов|степени]].<br/>
|
proof=
Рассмотрим Эйлеров цикл <math>p</math> в <math>G</math>.
Каждое вхождение вершины в цикл(кроме первого и последнего вхождения начальной вершины) добавляет 2 к ее степени.<br/>
Для начальной вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени.<br/>В итоге, каждая вершина имеет четную степень.
<br/>
'''Необходимость:'''
<br/>
Докажем утверждение по индукции.<br><br/>
''База:''<br/>
Лес из <math>N</math> деревьев, каждое из 1 вершины.<br/><br/>''Переход:''<br/>
Рассмотри граф, в котором степени всех вершин четные.<br/>
В нем найдется простой цикл, т.к. иначе граф является лесом, и тогда в нем есть хотя бы два листа, что противоречит четности степеней всех вершин.
Рассмотрим цикл <math>c</math> такой, что при удалении его ребер не образуется двух компонент связности размера больше 1.Такой всегда существует, т.к. [[Граф_блоков-точек_сочленения|граф компонент двусвязности блоков и точек сочленения]] произвольного почти связного графа является деревом, а т.к. все вершины <math>G</math> <br/>имеют четные степени, то не могут являться в нем листами. Значит, листами в дереве блоков и точек сочленения такого графа будут циклы, а в любом цикле есть подмножество, являющееся простым циклом.
Рассмотрим вершину <math>u</math> со степенью больше 2. После удаления цикла <math>c</math> из графа степени всех вершин останутся четными,
Неориентированный почти связный<ref name = "almost"/> граф <math>G = (V, E)</math> является полуэйлеровым тогда и только тогда, когда содержит ровно две вершины нечетной степени.<br/>
====[[Основные определения теории графов|Ориентированный граф]]====
{{Теорема
|statement=
<br/>
'''Следствие'''<br/>
Ориентированный почти связный<ref name = "almost"/> граф <math>G = (V, E)</math> является полуэйлеровым тогда и только тогда, когда содержит ровно одну вершину, [[Основные_определения_теории_графов|входная степень ]] которой на единицу больше [[Основные_определения_теории_графов|выходной]], и ровно одну вершину, выходная степень которой на единицу больше входной.<br/>
== Примечания ==
<references/>
==Источники==
1. Ф.Харари. Теория графов. Москва, издательство "Едиториал УРСС". 2003 г.
