17
правок
Изменения
м
'''Доказательство:'''|proof=
'''Следствие:'''{{Теорема|about=cледствие|statement=В ориентированном графе <tex>G = (V, E)</tex> существует эйлеров путь если: 1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа, для одной из которых <tex>\operatorname{deg}^+ - \operatorname{deg}^- = 1</tex>, а для другой <tex>\operatorname{deg}^+ - \operatorname{deg}^- = -1</tex>.
'''Доказательство:''' |proof=Соединим ориентированным ребром вершину с большей входящей степенью с вершиной с большей исходящей степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.}}
Нет описания правки
}}
{{Теорема'''Следствие:'''|about=следствие|statement=
В графе <tex>G = (V, E) </tex> существует эйлеров путь тогда и только тогда, когда:
1. Количество вершин с нечетной степенью меньше или равно двум.
2. Все компоненты связности кроме, может быть одной, не содержат ребер.
Добавим ребро, соединяющее вершины с нечетной степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.
}}
====[[Основные определения теории графов|Ориентированный граф]]====
}}
2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
==См. также==
* [[Алгоритм построения Эйлерова цикла]]
==ЛитератураИсточники информации==
* Ф.Харари Теория графов. Глава 7. Обходы графов. Эйлеровы графы.
* Уилсон Р. Введение в теорию графов. {{---}} М.: Мир, 1977. ==Ссылки==
* [http://e-maxx.ru/algo/euler_path Нахождение эйлерова пути]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
