Изменения

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

[[Основные определения теории графов|Путь]] <tex>p</tex> <tex>u_0 \rightarrow u_0u_1 \rightarrow u_1 \rightarrow u_1u_2 \rightarrow '''Эйлеровым путем''' (англ...\rightarrow u</tex>_{<tex>k-1</tex>} <tex>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> является Эйлеровым существует эйлеров цикл тогда и только тогда, когда : 1. Все вершины имеют четную степень. 2. Все компоненты связности, кроме, может быть, одной, не содержит вершин нечетной [[Основные определения теории графовсодержат ребер. |степени]]proof= Необходимость мы доказали ранее.Докажем достаточность, используя индукцию по числу вершин <tex>n<br/tex>.|proofБаза индукции: <tex>n =0</tex> цикл существует.'''Достаточность:'''Предположим что граф имеющий менее <tex>n<br/tex>вершин содержит эйлеров цикл. Рассмотрим Эйлеров цикл связный граф <tex>pG = (V, E)</tex> в с <tex>Gn > 0</tex>вершинами, степени которых четны.Каждое вхождение вершины в цикл(кроме первого Пусть <tex>v_1</tex> и последнего вхождения начальной <tex>v_2</tex> {{---}} вершины) добавляет 2 к ее степениграфа.Поскольку граф связный, то существует путь из <tex>v_1</tex> в <tex>v_2<br/tex>Для начальной вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени. В итогеСтепень <tex>v_2</tex> {{---}} чётная, значит существует неиспользованное ребро, каждая вершина имеет четную степеньпо которому можно продолжить путь из <tex>v_2</tex>.Так как граф конечный, то путь, в конце концов, должен вернуться в <tex>v_1<br/tex>, следовательно мы получим замкнутый путь (цикл). Назовем этот цикл <tex>'''Необходимость:'''C_1<br/tex>Докажем утверждение по индукции.Будем продолжать строить <brtex>C_1<br/tex> через <tex>''База:''v_1<br/tex> Лес таким же образом, до тех пор, пока мы в очередной раз не сможем выйти из вершины <tex>Nv_1</tex> деревьев, каждое из 1 вершиныто есть <tex>C_1</tex> будет покрывать все ребра, инцидентные <tex>v_1</tex>.Если <tex>C_1<br/tex> является эйлеровым циклом для <tex>G<br/tex>''Переход:', тогда доказательство закончено. Если нет, то пусть <tex>G'<br/tex> {{---}} подграф графа <tex>G</tex>Рассмотри граф, в котором степени полученный удалением всех вершин четныерёбер, принадлежащих <tex>C_1</tex>.Поскольку <tex>C_1<br/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>cG'</tex> такойчётная степень, что при удалении его ребер не образуется двух компонент то у каждой компоненты связности размера больше 1.Такой всегда <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>.

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

Ориентированный почти связный граф В ориентированном графе <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 г.]][[Категория: Эйлеровы графы]]