Изменения

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

'''Эйлеровым путем''' (англ. ''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| Две компоненты связности, одна имеет ребра.]]

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

Восстановить эйлеров цикл исходного графа можно следующим образом: идём по первому циклу, обнаруженному жадным обходомНеобходимость мы доказали ранее. Каждый разДокажем достаточность, когда вершина этого цикла лежит также и на другом цикле в одной из компонент связности, обходим этот цикл. Очевидно, полученный путь будет являться циклом и обходит все рёбра графаиспользуя индукцию по числу вершин <tex>n</tex>.}}

В графе Предположим что граф имеющий менее <tex>G = (V, E) n</tex> существует вершин содержит эйлеров путь тогда и только тогда, когда:цикл.

1. Количество вершин Рассмотрим связный граф <tex>G = (V, E)</tex> с нечетной степенью меньше или равно двум<tex>n > 0</tex> вершинами, степени которых четны.

2Пусть <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>.

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

В ориентированном графе <tex>G = (V, E)</tex> существует эйлеров путь если для двух вершин данного графа выполнено:=См. также==

1. <tex>|deg^+u - deg^-u| = 1</tex>. 2. Все компоненты слабой связности кроме, может быть одной, не имеют ребер. '''Доказательство''' Соединим ориентированным ребром вершину с большей входящей степенью с вершиной с большей исходящей степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем. ==* [[Алгоритм построения эйлерова Эйлерова цикла, эйлерова пути== Запускаем алгоритм от вершины <tex>v</tex>.Алгоритм будет корректно работать, когда в графе существует эйлеров цикл, то есть степени всех вершин четны.  FindEulerPath(v) перебираем все рёбра, выходящие из вершины v. каждое такое ребро удаляем из графа. вызываем FindEulerPath из второго конца этого ребра. добавляем вершину v в ответ. Сложность алгоритма <tex>O(E)</tex> В случае не существования эйлерова цикла, соединим вершины с нечетной степенью ребром, найдем эйлеров цикл, а затем удалим добавленное ребро из ответа.]]

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

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