Изменения

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

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

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

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

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

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

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

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

2. Все компоненты связности , кроме, может быть , одной, не содержат ребер.

Восстановить Предположим что граф имеющий менее <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>, обходим следовательно мы получим замкнутый путь (цикл). Назовем этот цикл<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'</tex> имеет менее, чем <tex>n</tex> вершин, а у каждой вершины графа <tex>G'Следствие:''</tex> чётная степень, то у каждой компоненты связности <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>.

 '''Доказательство:'''|proof=

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

==Полезные ссылкиИсточники информации==

* Ф.Харари Теория графов. глава Глава 7. Обходы графов. Эйлеровы графы.* Уилсон Р. Введение в теорию графов. {{---}} М.: Мир, 1977