Эйлеровость графов

Эйлеров путь

Определение:

Эйлеровым путем в графе называется путь, который проходит по каждому ребру, причем ровно один раз.

Эйлеров обход

Определение:

Эйлеров обход - обход графа, посещающий эйлеров путь.

Эйлеров цикл

Определение:

Эйлеров цикл - замкнутый эйлеров путь.

Эйлеров граф

Определение:

Граф называется эйлеровым, если он содержит эйлеров цикл. Граф называется полуэйлеровым, если он содержит эйлеров путь, но не содержит эйлеров цикл.

Критерий эйлеровости

Необходимое условия:

1. Количество вершин нечетной степени не превосходит двух.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.

Доказательство:

1. Допустим в графе количество вершин нечетной степени больше двух. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два(помечаем уже пройденые ребра), если эта вершина не является стартовой или конечной. Следовательно вершин с нечетной степенью не может быть больше двух. Наше предположение неверно.

2. Если в графе существует более одной компоненты связности с ребрами, то очевидно, что нельзя пройти по их ребрам одним путем.

Теорема:

Для того, чтобы граф был эйлеровым необходимо: 1. Количество вершин нечетной степени не превосходило двух. 2. Все компоненты связности кроме, может быть одной, не содержали ребер.

Доказательство:

[math]\triangleright[/math]

1. Допустим в графе количество вершин нечетной степени больше двух. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два(помечаем уже пройденые ребра), если эта вершина не является стартовой или конечной. Следовательно вершин с нечетной степенью не может быть больше двух. Наше предположение неверно. 2. Если в графе существует более одной компоненты связности с ребрами, то очевидно, что нельзя пройти по их ребрам одним путем.

[math]\triangleleft[/math]

Эйлерова пути нет. Количество вершин нечетной степени больше двух.

Две компоненты связности, одна имеет ребра.

Теорема:

В графе [math]G = (V, E) [/math] существует эйлеров цикл тогда и только тогда, когда: 1. Все вершины имеют четную степень. 2. Все компоненты связности кроме, может быть одной, не содержат ребер.

Доказательство:

[math]\triangleright[/math]

Докажем эту теорему, используя индукцию по числу вершин [math]n[/math]. Необходимость мы доказали ранее. База индукции: [math]n = 0[/math] цикл существует. Предположим что граф имеющий менее [math]n[/math] вершин содержит эйлеров цикл. Рассмотрим связный граф [math]G = (V, E)[/math] с [math]n \gt 0[/math] вершинами, степени которых четны. Допустим, что [math]v_1[/math] и [math]v_2[/math] - вершины графа. Поскольку граф связный, то существует путь из [math]v_1[/math] в [math]v_2[/math]. Поскольку степень [math]v_2[/math] - чётная, существует неиспользованное ребро, по которому можно продолжить путь. Поскольку граф конечный, то путь, в конце концов, должен вернуться в [math]v_1[/math], и эйлеров цикл можно считать построенным. Если [math]C_1[/math] является эйлеровым циклом для [math]G[/math], тогда доказательство закончено. Если нет, то пусть [math]G'[/math] - подграф графа [math]G[/math], полученный удалением всех рёбер, принадлежащих [math]C_1[/math]. Поскольку [math]C_1[/math] содержит чётное число рёбер, инцидентных каждой вершине, то каждая вершина подграфа [math]G'[/math] имеет чётную степень. Заметим что [math]G'[/math] может состоять из нескольких компонент связности. Рассмотрим какую - либо компоненту связности [math]G'[/math]. Поскольку рассматриваемая компонента связности [math]G'[/math] имеет менее, чем [math]n[/math] вершин, а у каждой вершины графа [math]G'[/math] чётная степень, то у каждой компоненты связности [math]G'[/math] существует эйлеров цикл. Пусть для рассматриваемой компоненты связноти это цикл [math]C_2[/math]. У [math]C_1[/math] и [math]C_2[/math] имеется общая вершина [math]a[/math], так как [math]G[/math] cвязен. Теперь можно обойти эйлеров цикл, начиная его в вершине [math]a[/math], обойти [math]C_1[/math] , вернуться в [math]a[/math], затем пройти [math]C_2[/math] и вернуться в [math]a[/math]. Если новый эйлеров цикл не является эйлеровым циклом для [math]G[/math], продолжаем использовать этот процесс, расширяя наш эйлеров цикл, пока, в конце концов, не получим эйлеров цикл для [math]G[/math].

[math]\triangleleft[/math]

Следствие:

В графе [math]G = (V, E) [/math] существует эйлеров путь тогда и только тогда, когда:

1. Количество вершин с нечетной степенью меньше или равно двум.

2. Все компоненты связности кроме, может быть одной, не содержат ребер.

Доказательство:

Добавим ребро, соединяющее вершины с нечетной степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.

Ориентированный граф

Теорема:

В ориентированном графе [math]G = (V, E) [/math] существует эйлеров цикл тогда и только тогда, когда: 1. Входная степень любой вершины равна ее выходной степени. 2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.

Доказательство:

[math]\triangleright[/math]

Доказательство аналогично случаю неориентированного графа.

[math]\triangleleft[/math]

Следствие:

В ориентированном графе [math]G = (V, E)[/math] существует эйлеров путь если:

1. Входная степень любой вершины равна ее выходной степени, кроме двух вершин графа, для одной из которых [math]deg^+ - deg^- = 1[/math], а для другой [math]deg^+ - deg^- = -1[/math].

2. Все компоненты слабой связности кроме, может быть одной, не содержат ребер.

Доказательство:

Соединим ориентированным ребром вершину с большей входящей степенью с вершиной с большей исходящей степенью. Теперь можно найти эйлеров цикл, после чего удалить добавленное ребро. Очевидно найденный цикл станет путем.

Источники

• Ф.Харари Теория графов. Глава 7. Обходы графов. Эйлеровы графы.

Полезные ссылки

• Нахождение эйлерова пути
• Алгоритм построения Эйлерова цикла