Изменения

==Эйлеров путьОсновные определения==

[[Основные определения теории графов|Путь]] <tex>p</tex> <tex>u_0 \rightarrow u_0u_1 \rightarrow u_1 \rightarrow u_1u_2 \rightarrow '''Эйлеровым путем''' (англ...\rightarrow u_{k-1}u_k \rightarrow u_k</tex> в [[Основные определения теории графов|графе]] <tex>G = (V, E)</tex>называется ''ЭйлеровымEulerian path'', если содержит все ) в графе называется [[Основные определения теории графов|ребрапуть]] <tex>G</tex>, который проходит по каждому ребру, причем каждое - только ровно один раз. <br/>

[[Основные определения теории графов|Цикл]] <tex>p</tex> <tex>u_0 \rightarrow u_0u_1 \rightarrow u_1 \rightarrow u_1u_2 \rightarrow ..'''Эйлеров обход''' (англ.\rightarrow u_ku_0\rightarrow u_0</tex> в графе <tex>G = (V, E)</tex>называется ''ЭйлеровымEulerian circuit'') {{---}} обход графа, если содержит все ребра <tex>G</tex>, причем каждое - только один разпосещающий эйлеров путь. <br/>

Эйлеровым циклом является '''Эйлеров цикл''' (англ. ''Eulerian cycle'') {{---}} замкнутый эйлеров путь, являющийся циклом.

==Эйлеров граф=={{Определение|id = euler_graph|definition=Граф <tex>G = называется '''эйлеровым''' (V, Eангл. ''Eulerian graph'')</tex> называется Эйлеровым, если он содержит Эйлеров эйлеров цикл. Графназывается '''полуэйлеровым''', содержащий Эйлеров если он содержит эйлеров путь, но не являющийся циклом, называют полуэйлеровымсодержит эйлеров цикл. <br/>

===Критерий Эйлеровости=эйлеровости=={{ОпределениеТеорема|definitionid =eulerTheoremНеориентированный |statement=Для того, чтобы граф назовем почти связным<tex>G = (V, если все его [[Отношение_связности,_компоненты_связности|E) </tex> был эйлеровым необходимо чтобы:1. Все вершины имели четную степень. 2. Все компоненты связности]], кроме, может быть может, одной, имеют размер не содержали ребер.|proof=1.<br/>Ориентированный граф назовем почти связнымДопустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два (помечаем уже пройденые ребра), если все его [[Отношение_связностиэта вершина не является стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла,_компоненты_связности|и на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение неверно. 2. Если в графе существует более одной компоненты слабой связности]], кромес ребрами, быть можетто очевидно, одной, имеют размер 1что нельзя пройти по их ребрам одним путем.

====[[Основные определения теории графовФайл:Euler_path_1.png|Неориентированный граф160px|thumb|left|Эйлерова пути нет.<br>Количество вершин нечетной степени больше двух.]][[Файл:Euler_path_2.png|230px|thumb|none|Две компоненты связности, одна имеет ребра.]]====

Неориентированный почти связный граф В графе <tex>G = (V, E)</tex> является Эйлеровым существует эйлеров цикл тогда и только тогда, когда не содержит вершин нечетной [[Основные определения теории графов|степени]].<br/>|proof='''Достаточность:'''<br/>Рассмотрим Эйлеров цикл <tex>p</tex> в <tex>G</tex>1.Каждое вхождение Все вершины в цикл(кроме первого и последнего вхождения начальной вершины) добавляет 2 к ее степениимеют четную степень.<br/>Для начальной вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени. В итогеВсе компоненты связности, кроме, может быть, одной, каждая вершина имеет четную степеньне содержат ребер.<br/>'''Необходимость:'''|proof=<br/>Необходимость мы доказали ранее. Докажем утверждение достаточность, используя индукцию по индукции.<br><br/>''База:''<br/> Лес из числу вершин <tex>Nn</tex> деревьев, каждое из 1 вершины.<br/><br/>''ПереходБаза индукции:''<br/>Рассмотри граф, в котором степени всех вершин четные.<br/>В нем найдется простой цикл, т.к. иначе граф является [[Дерево, эквивалентные определения|лесом]], и тогда в нем есть хотя бы два листа, что противоречит четности степеней всех вершин.Рассмотрим цикл <tex>cn = 0</tex> такой, что при удалении его ребер не образуется двух компонент связности размера больше 1.Такой всегда цикл существует, т.к. [[Граф_блоков-точек_сочленения|граф блоков и точек сочленения]] произвольного почти связного графа является [[Дерево, эквивалентные определения|деревом]], а т.к. все вершины <tex>G</tex> имеют четные степени, то не могут являться в нем листами. Значит, листами в дереве блоков и точек сочленения такого графа будут циклы, а в любом цикле есть подмножество, являющееся простым циклом.

Предположим что граф имеющий менее <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>u, следовательно мы получим замкнутый путь (цикл). Назовем этот цикл <tex>C_1</tex> со степенью больше 2. После удаления цикла Будем продолжать строить <tex>C_1</tex>cчерез <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 - c'</tex> имеет менее, чем <tex>n</tex>вершин, по предположению индукцииа у каждой вершины графа <tex>G'</tex> чётная степень, то у каждой компоненты связности <tex>G'</tex> существует эйлеров цикл. Пусть для рассматриваемой компоненты связноти это цикл <tex>eC_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>ua</tex>, затем обойти пройти <tex>C_2</tex> и вернуться в <tex>a</tex>. Если новый эйлеров цикл не является эйлеровым циклом для <tex>G</tex>, продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для <tex>eG</tex>. }}{{Теорема|about=следствие|statement=В графе <tex>G = (V, E) <br/tex>существует эйлеров путь тогда и только тогда, когда:1. Количество вершин с нечетной степенью меньше или равно двум.2. Все компоненты связности кроме, может быть одной, не содержат ребер.|proof=Переход доказанДобавим ребро, соединяющее вершины с нечетной степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.

Ориентированный почти связный граф В ориентированном графе <tex>G = (V, E) </tex> является Эйлеровым существует эйлеров цикл тогда и только тогда, когда входная : 1. Входная степень любой вершины равна ее выходной степени.<br/> 2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.

Аналогично неориентированному графуДоказательство аналогично случаю неориентированного графа.}} {{Теорема|about=cледствие|statement=В ориентированном графе <tex>G = (V, E)</tex> существует эйлеров путь если:1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа, для одной из которых <tex>\operatorname{deg}^+ - \operatorname{deg}^- = 1</tex>, а для другой <tex>\operatorname{deg}^+ - \operatorname{deg}^- = -1</tex>.2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.|proof=Соединим ориентированным ребром вершину с большей входящей степенью с вершиной с большей исходящей степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.

<br/>==См. также=='''Следствие'''<br/>Ориентированный почти связный граф <tex>G = (V, E)</tex> является полуэйлеровым тогда и только тогда, когда содержит ровно одну вершину, * [[Основные_определения_теории_графов|входная степеньАлгоритм построения Эйлерова цикла]] которой на единицу больше  == Источники информации== * Ф.Харари Теория графов. Глава 7. Обходы графов. Эйлеровы графы.* Уилсон Р. Введение в теорию графов. {{---}} М.: Мир, 1977* [[Основные_определения_теории_графов|выходной]], и ровно одну вершину, выходная степень которой на единицу больше входнойhttp://e-maxx.<brru/>algo/euler_path Нахождение эйлерова пути]

==Источники==[[Категория: Алгоритмы и структуры данных]]1. Ф.Харари. Теория [[Категория: Обходы графов. Москва, издательство "Едиториал УРСС". 2003 г.]][[Категория: Эйлеровы графы]]