Инструменты пользователя

Инструменты сайта


examination:diskretka:question15

Вопрос №15. Эйлеровы графы. Критерий эйлеровости конечного неориентированного графа.

Эйлеров цикл – цикл в графе, содержащий все ребра этого графа; граф, имеющий эйлеров цикл, называется эйлеровым.

Не любой граф эйлеров.

Теорема Эйлера: критерий эйлеровости конечного графа Конечный неорграф эйлеров, если он связен и степени всех его вершин четны (локальная степень, то есть петлю считаем за 2).

Замечание: наличие петель в графе на эйлеровость не влияет; поэтому при проверке на эйлеровость петли можно не учитывать.

Доказательство теоремы: Необходимость очевидна. Связность ясна. Рассмотрим честность степеней вершин. Эта вершина непременно попадает в какой-нибудь эйлеров цикл в заданном графе, следовательно, входя в эту вершину по одному из ребер цикла, мы должны выйти по другому ребру. Так как каждое из ребер графа входит в эйлеров цикл, это значит, что все ребра (без петель), инцидентные данной вершине, разбиваются на пары соседних в эйлеровом цикле. Следовательно, указанное количество ребер должно быть четным числом. Достаточность: пусть граф Г связен, а степени всех его вершин четны, построим эйлеров цикл: начальную вершину возьмем произвольно. Каждый раз, когда мы добавляем к эйлеровому маршруту новое ребро и переходим в новую вершину , отличную от начальной, число свободных ребер уменьшается на 1. Так как до этого указанное число ребер было четным, то после этого оно становится нечетным и заведомо не равным нулю. Следовательно, в вершине эйлеров цикл кончиться не может. С другой стороны, при любом выходе из начальной вершины и возврате к ней число свободных ребер уменьшается на 2 и в конце концов указанная величина станет равной нулю. Процесс таким образом завершится в начальной вершине. Мы построили цикл, начинающийся и заканчивающийся в начальной вершине. Нет оснований считать его эйлеровым. Дальнейшая деятельность – расширение цикла путем последовательного присоединения оставшихся ребер графа с тем, чтобы в итоге получить эйлеров цикл.

examination/diskretka/question15.txt · Последние изменения: 2014/01/15 12:14 (внешнее изменение)