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

Материал из Викиконспекты
Версия от 08:00, 25 декабря 2011; 192.168.0.2 (обсуждение) (Критерий эйлеровости)
Перейти к: навигация, поиск

Эйлеров путь

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


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

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


Эйлеров цикл

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


Эйлеров граф

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


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

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

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. Обходы графов. Эйлеровы графы.

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