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