Изменения

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

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

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

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

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

===Критерий эйлеровости=={{Теорема|id =eulerTheoremНеобходимое условия|statement=Для того, чтобы граф <tex>G = (V, E) </tex> был эйлеровым необходимо чтобы:1. Все вершины имели четную степень.

2. Все компоненты связности, кроме, может быть, одной, не содержали ребер.|proof=1. Количество Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два (помечаем уже пройденые ребра), если эта вершина не является стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степени степенью быть не превосходит двухможет. Наше предположение неверно.

2. Все Если в графе существует более одной компоненты связности кромес ребрами, может быть однойто очевидно, не имеют реберчто нельзя пройти по их ребрам одним путем.}}

[[Файл:not_eulerEuler_path_1.png|200px160px|thumb|centerleft| Эйлерова пути нет. <br>Количество вершин нечетной степени больше двух.]][[Файл:not_euler2Euler_path_2.png|200px230px|thumb|centernone| Эйлерова пути нет. Количество вершин нечетной степени больше двухДве компоненты связности, одна имеет ребра.]]

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

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

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

''Базаиндукции:'' <br>Лес из <tex>Nn = 0</tex> деревьев, каждое из 1 вершиныцикл существует.

''Переход:''Предположим что граф имеющий менее <tex>n<br/tex>Рассмотри граф, в котором степени всех вершин четныесодержит эйлеров цикл.

В нем найдется простой цикл, т.к. иначе Рассмотрим связный граф является [[Дерево, эквивалентные определения|лесом]], и тогда в нем есть хотя бы два листа, что противоречит четности степеней всех вершин.Рассмотрим цикл <tex>cG = (V, E)</tex> такой, что при удалении его ребер не образуется двух компонент связности размера больше 1.Такой всегда существует, т.к. [[Граф_блоков-точек_сочленения|граф блоков и точек сочленения]] произвольного почти связного графа является [[Дерево, эквивалентные определения|деревом]], а т.к. все вершины с <tex>Gn > 0</tex> имеют четные вершинами, степени, то не могут являться в нем листами. Значит, листами в дереве блоков и точек сочленения такого графа будут циклы, а в любом цикле есть подмножество, являющееся простым цикломкоторых четны.

Рассмотрим вершину Пусть <tex>v_1</tex> и <tex>v_2</tex> {{---}} вершины графа. Поскольку граф связный, то существует путь из <tex>v_1</tex> в <tex>uv_2</tex> со степенью больше 2. После удаления цикла Степень <tex>cv_2</tex> {{---}} чётная, значит существует неиспользованное ребро, по которому можно продолжить путь из <tex>v_2</tex>. Так как граф конечный, то путь, в конце концов, должен вернуться в <tex>v_1</tex>, следовательно мы получим замкнутый путь (цикл). Назовем этот цикл <tex>C_1</tex>. Будем продолжать строить <tex>C_1</tex> через <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>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 г.