Изменения

==Эйлеров обходОсновные определения==

'''Эйлеров обходЭйлеровым путем''' - обход графа, посещающий эйлеров (англ. ''Eulerian path'') в графе называется [[Основные определения теории графов|путь]], который проходит по каждому ребру, причем ровно один раз.

'''Эйлеровым путемЭйлеров обход''' в графе называется (англ. ''Eulerian circuit'') {{---}} обход графа, посещающий эйлеров путь, который проходит по каждому ребру, причем ровно один раз.

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

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

Рассмотрим эйлеров цикл <tex>p</tex> в <tex>G</tex>1.Каждое вхождение Все вершины в цикл(кроме первого и последнего вхождения начальной вершины) добавляет 2 к ее степениимеют четную степень.<br/>Для начальной вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени. В итогеВсе компоненты связности, кроме, может быть, одной, каждая вершина имеет четную степеньне содержат ребер. |proof=

'''Необходимость:'''мы доказали ранее. Докажем достаточность, используя индукцию по числу вершин <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. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.

Аналогично неориентированному графуДоказательство аналогично случаю неориентированного графа.

<br/>{{Теорема|about='''Следствие'''<br/>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/>

==Источникиинформации==1. Ф.Харари. Теория графов. Москва, издательство "Едиториал УРСС". 2003 г.