Изменения

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

[[Основные определения теории графов|Путь]] <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>P</tex> содержит все ) в графе называется [[Основные определения теории графов|ребрапуть]] <tex>G</tex>, который проходит по каждому ребру, причем каждое - только ровно один раз. <br/>

[[Основные определения теории графов|Цикл]] <tex>C</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>C</tex> содержит все ребра <tex>G</tex>, причем каждое - только один разпосещающий эйлеров путь. <br/>

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

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

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

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

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

Докажем утверждение по База индукции: <tex>n = 0</tex> цикл существует.

''База:'' <br>Лес из Предположим что граф имеющий менее <tex>Nn</tex> деревьев, каждое из 1 вершинывершин содержит эйлеров цикл.

''Переход:''Рассмотрим связный граф <tex>G = (V, E)</tex> с <brtex>Рассмотри граф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>cC_1</tex>. Будем продолжать строить <tex>C_1</tex> такойчерез <tex>v_1</tex> таким же образом, до тех пор, что при удалении его ребер пока мы в очередной раз не образуется двух компонент связности размера больше 1сможем выйти из вершины <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>GC_1</tex> имеют четные степенисодержит чётное число рёбер, инцидентных каждой вершине, то не могут являться в нем листамикаждая вершина подграфа <tex>G'</tex> имеет чётную степень. ЗначитА так как <tex>C_1</tex> покрывает все ребра, листами в дереве блоков и точек сочленения такого графа будут циклыинцидентные <tex>v_1</tex>, а в любом цикле есть подмножество, являющееся простым цикломто граф <tex>G'</tex> будет состоять из нескольких компонент связности.

Рассмотрим вершину какую-либо компоненту связности <tex>uG'</tex> со степенью больше 2. После удаления цикла Поскольку рассматриваемая компонента связности <tex>G'</tex> имеет менее, чем <tex>cn</tex> из графа степени всех вершин останутся четными,при этом количество ребер в графе уменьшится. Для а у каждой вершины графа <tex>G - c'</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>cC_1</tex>, начиная с вершины вернуться в <tex>ua</tex>, затем обойти пройти <tex>C_2</tex> и вернуться в <tex>a</tex>. Если новый эйлеров цикл не является эйлеровым циклом для <tex>G</tex>, продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для <tex>eG</tex>.

'''Следствие'''{{Теорема|about=следствиеНеориентированный почти связный граф |statement=В графе <tex>G = (V, E)</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 г.]][[Категория: Эйлеровы графы]]