Эйлеровость графов — различия между версиями
(→Критерий эйлеровости) |
(→Ориентированный граф) |
||
| Строка 46: | Строка 46: | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
| − | Ориентированный почти связный граф <tex>G = (V, E) </tex> является эйлеровым тогда и только тогда, когда входная степень любой вершины равна ее выходной степени. | + | Ориентированный почти связный граф <tex>G = (V, E) </tex> является эйлеровым тогда и только тогда, когда входная степень любой вершины равна ее выходной степени. |
|proof= | |proof= | ||
| − | |||
}} | }} | ||
| − | |||
| − | |||
| − | |||
| − | |||
==Источники== | ==Источники== | ||
Версия 07:04, 30 ноября 2011
Содержание
Эйлеров обход
| Определение: |
| Эйлеров обход - обход графа, посещающий эйлеров путь. |
Эйлеров путь
| Определение: |
| Эйлеровым путем в графе называется путь, который проходит по каждому ребру, причем ровно один раз. |
Эйлеров цикл
| Определение: |
| Эйлеров цикл - эйлеров путь, который является циклом. |
Эйлеров граф
| Определение: |
| Граф называется эйлеровым, если он содержит эйлеров цикл. Граф, содержащий эйлеров путь, не являющийся циклом, называют полуэйлеровым. |
Критерий эйлеровости
Необходимое условия:
1. Количество вершин нечетной степени не превосходит двух.
2. Все компоненты связности кроме, может быть одной, не имеют ребер.
| Теорема: |
В графе существует эйлеров цикл тогда и только тогда, когда:
1. Все вершины имеют четную степень. 2. Все компоненты связности кроме, может быть одной, не имеют ребер. |
| Доказательство: |
|
База индукции: цикл существует. При доказано. |
Ориентированный граф
| Теорема: |
Ориентированный почти связный граф является эйлеровым тогда и только тогда, когда входная степень любой вершины равна ее выходной степени. |
Источники
1. Ф.Харари. Теория графов. Москва, издательство "Едиториал УРСС". 2003 г.
