Эйлеровость графов
Содержание
Эйлеров путь
| Определение: |
| Эйлеровым путем в графе называется путь, который проходит по каждому ребру, причем ровно один раз. |
Эйлеров обход
| Определение: |
| Эйлеров обход - обход графа, посещающий эйлеров путь. |
Эйлеров цикл
| Определение: |
| Эйлеров цикл - замкнутый эйлеров путь. |
Эйлеров граф
| Определение: |
| Граф называется эйлеровым, если он содержит эйлеров цикл. Граф называется полуэйлеровым, если он содержит эйлеров путь, но не содержит эйлеров цикл. |
Критерий эйлеровости
Необходимое условия:
1. Количество вершин нечетной степени не превосходит двух.
2. Все компоненты связности кроме, может быть одной, не содержат ребер.
Доказательство:
1. Допустим в графе количество вершин нечетной степени больше двух. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два(помечаем уже пройденые ребра), если эта вершина не является стартовой или конечной. Следовательно вершин с нечетной степенью не может быть больше двух. Наше предположение неверно.
2. Если в графе существует более одной компоненты связности с ребрами, то очевидно, что нельзя пройти по их ребрам одним путем.
| Теорема: |
В графе существует эйлеров цикл тогда и только тогда, когда:
1. Все вершины имеют четную степень. 2. Все компоненты связности кроме, может быть одной, не содержат ребер. |
| Доказательство: |
|
База индукции: цикл существует. При доказано. Рассмотрим граф в котором количество вершин с четной степенью больше нуля. Рассмотрим произвольную вершину . Из нее выходит ребро. Пойдем по нему и будем действовать далее также. Таким образом можно дойти до и найти цикл. Выкинем ребра цикла из графа. Первое условие сохранится. Второе может не выполниться, найдём эйлеров цикл в каждой получившейся компоненте связности. Восстановить эйлеров цикл исходного графа можно следующим образом: идём по первому циклу, обнаруженному жадным обходом. Каждый раз, когда вершина этого цикла лежит также и на другом цикле в одной из компонент связности, обходим этот цикл. Очевидно, полученный путь будет являться циклом и обходит все рёбра графа. |
Следствие:
В графе существует эйлеров путь тогда и только тогда, когда:
1. Количество вершин с нечетной степенью меньше или равно двум.
2. Все компоненты связности кроме, может быть одной, не содержат ребер.
Доказательство:
Добавим ребро, соединяющее вершины с нечетной степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.
Ориентированный граф
| Теорема: |
В ориентированном графе существует эйлеров цикл тогда и только тогда, когда:
1. Входная степень любой вершины равна ее выходной степени. 2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер. |
| Доказательство: |
| Доказательство аналогично случаю неориентированного графа. |
Следствие:
В ориентированном графе существует эйлеров путь если:
1. Для двух вершин данного графа выполнено .
2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.
Доказательство:
Соединим ориентированным ребром вершину с большей входящей степенью с вершиной с большей исходящей степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.
Полезные ссылки
- Ф.Харари Теория графов. глава 7. Обходы графов. Эйлеровы графы.
- Нахождение эйлерова пути
- Алгоритм построения Эйлерова цикла
