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