1632
правки
Изменения
м
==Эйлеров обход==
==Эйлеров цикл==
==Эйлеров граф=={{Определение|id = euler_graph|definition=Граф называется '''эйлеровым'''(англ. ''Eulerian graph''), если он содержит эйлеров цикл. Граф называется '''полуэйлеровым''', если он содержит эйлеров путь, но не содержит эйлеров цикл.
{| |[[Файл:Euler_path_1.png|200px160px|thumb|left| Эйлерова пути нет. <br>Количество вершин нечетной степени больше двух.]] |[[Файл:Euler_path_2.png|300px230px|thumb|none| Две компоненты связности, одна имеет ребра.]] |}
'''Доказательство:'''|proof=
'''Следствие:'''{{Теорема|about=cледствие|statement=В ориентированном графе <tex>G = (V, E)</tex> существует эйлеров путь если: 1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа, для одной из которых <tex>\operatorname{deg}^+ - \operatorname{deg}^- = 1</tex>, а для другой <tex>\operatorname{deg}^+ - \operatorname{deg}^- = -1</tex>.
'''Доказательство:''' Соединим ориентированным ребром вершину с большей входящей степенью с вершиной с большей исходящей степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем. ==См. Такжетакже==
rollbackEdits.php mass rollback
==Эйлеров путьОсновные определения==
{{Определение|definition=
'''Эйлеровым путем''' (англ. ''Eulerian path'') в графе называется [[Основные определения теории графов|путь]], который проходит по каждому ребру, причем ровно один раз.
}}
{{Определение|definition=
'''Эйлеров обход''' (англ. ''Eulerian circuit'') {{---}} обход графа, посещающий эйлеров путь.
}}
{{Определение|definition=
'''Эйлеров цикл''' (англ. ''Eulerian cycle'') {{---}} замкнутый эйлеров путь.
}}
}}
==Критерий эйлеровости==
{{Теорема
|id = eulerTheorem
|statement=
Для того, чтобы граф <tex>G = (V, E) </tex> был эйлеровым необходимо чтобы:
1. Все вершины имели четную степень.
2. Все компоненты связности , кроме, может быть , одной, не содержали ребер.
|proof=
1. Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два (помечаем уже пройденые ребра), если эта вершина не является стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение неверно.
}}
{{Теорема
1. Все вершины имеют четную степень.
2. Все компоненты связности , кроме, может быть , одной, не содержат ребер.
|proof=
}}
{{Теорема'''Следствие:'''|about=следствие|statement=
В графе <tex>G = (V, E) </tex> существует эйлеров путь тогда и только тогда, когда:
1. Количество вершин с нечетной степенью меньше или равно двум.
2. Все компоненты связности кроме, может быть одной, не содержат ребер.
Добавим ребро, соединяющее вершины с нечетной степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.
}}
====[[Основные определения теории графов|Ориентированный граф]]====
}}
2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
|proof=Соединим ориентированным ребром вершину с большей входящей степенью с вершиной с большей исходящей степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.
}}
* [[Алгоритм построения Эйлерова цикла]]
==ЛитератураИсточники информации==
* Ф.Харари Теория графов. Глава 7. Обходы графов. Эйлеровы графы.
* Уилсон Р. Введение в теорию графов. {{---}} М.: Мир, 1977. ==Ссылки==
* [http://e-maxx.ru/algo/euler_path Нахождение эйлерова пути]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория: Эйлеровы графы]]
