32. Степени вершин. Эйлеровы графы, циклы, цепи. Алгоритм построения эйлерова цикла.

Степенью или валентностью вершины a неорграфа G называется число ребер, инцидентных вершине a (петли считаются дважды). Вершина степени 0 называется изолированной, степени 1 – концевой или висячей.

Лемма о рукопожатиях: Сумма степеней всех вершин графа является четным числом и равна удвоенному числу ребер.

Критерий «эйлировости» графа: Связный неориентированный мультиграф тогда и только тогда является эйлеровым, когда степень каждой из его вершин – четное число.

Алгоритм построения эйлерова цикла:

1. Выбрать произвольно некоторую вершину a.

2. Выбрать произвольно некоторое ребро u, инцидентное a, и присвоить ему номер 1 (назовем это ребро пройденным).

3. Каждое пройденное ребро вычеркнуть и присвоить ему номер, на единицу больший предыдущего вычеркнутого ребра.

4. Находясь в вершине x, не выбирать ребро, соединяющее x с a, если есть возможность иного выбора.

5. Находясь в вершине x, не выбирать ребро, которое является перешейком (т.е. ребром, при вычеркивании которого граф распадается на две компоненты связности).

6. После того как в графе будут занумерованы все ребра, образуется эйлеров цикл.

Теорема: Если связный граф содержит k вершин нечетной степени, то минимальное число покрывающих его реберно непересекающихся цепей равно k/2.

Доказательство: Набор реберно непересекающихся цепей покрывает граф G, если каждое его ребро входит в одну из этих цепей.

Пусть связный граф G содержит k вершин нечетной степени. По лемме о рукопожатиях число k четно. Рассмотрим граф G’, полученной добавлением к G новой вершины a и ребер, соединяющих a со всеми вершинами нечетной степени графа G. Граф G’ будет содержать эйлеров цикл. Если удалить из этого цикла все ребра, инцидентные вершине a, то получится не более k/2 цепей, покрывающих G. С другой стороны, граф, являющийся объединением r реберно непересекающихся цепей имеет не более 2r верши нечетной степени. Поэтому граф G нельзя покрыть цепями, число которых меньше k/2.