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

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

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

По этой ссылке вы найдёте полный курс лекций по математике:

Решение задач по математике

Начать цикл с произвольной вершины и. Присвоить произвольному ребру tiv, инцидентному и, номер 1. Удалить из графа ребро uv, перейти в вершину v. Пусть после к шагов мы находимся в вершине w. Выбрать произвольное ребро wt, причем мост выбирается только в том случае, если нет другой возможности. Ребру wt присвоить номер k+ 1. Удалить из графа ребро wt, перейти в вершину t. Число шагов в описанном алгоритме совпадает с числом ребер в графе.

По окончании работы алгоритма ребра исходного графа будут пронумерованы в порядке их следования в эйлеровом цикле. Докажем корректность предложенного алгоритма. Теорема 6. Применение алгоритма Флери к произвольному эйлерову графу всегда при водит к построению эйлерова цикла. Алгоритм Флери построения эйлерова цикла Пусть G — эйлеров граф. Тогда степень каждой его вершины четна. В силу этого алгоритм может закончить свою работу лишь в начальной вершине и, построив при этом некоторый цикл С.

Нужно доказать, что цикл С включает в себя все ребра графа G. Если это не так, то после удаления ребер С граф распадается на компоненты связности, хотя бы одна из которых (назовем ее В) содержит ребра. Обозначим через А семейство всех ребер цикла С, инцидентных вершинам В.

Пусть а — наибольший номер ребра (полученный в результате работы алгоритма Флери) из А, тогда к моменту удаления данного ребра из графа оно было мостом; однако это противоречит правилу выбора очередного ребра: поскольку в компоненте В степень каждой вершины четна (это легко видеть), то в ней существует цикл, идя по которому (напомним, любое ребро цикла — не мост) можно было избежать преждевременного удаления моста.

Возможно вам будут полезны данные страницы:

Проведение проецирующей плоскости через прямую линию
Практические приемы расчета на сдвиг и смятие. Расчет болтовых соединений
Химические расчеты
Примеры решения

Корректность алгоритма Флери доказана. В заключение параграфа отметим, что для случайным образом построенного графа вероятность его эйлеровости (при большом числе вершин) мала. Теорема 7 (Р. Рейд, 1962 г.). Пусть Р(п) — множество всех простых помеченных графов с п вершинами, Р9(п) — множество всех простых помеченных эйлеровых графов с п вершинами.

Тогда Алгоритм Флери построения

эйлерова цикла Пусть Р0(п) — множество всех простых помеченных графов с п вершинами, степень каждой из которых четна. Связные графы из Ро{п) составляют, как известно, Ре{п); поэтому . Каждый граф из Р(п) определяется некоторым подмножеством ребер полного графа Кп, содержащего Сп ребер; в силу этого Нетрудно подсчитать и мощность Ро(п).

Установим взаимно однозначное соответствие между Р(п - 1) и Ро(п): если все вершины нечетной степени произвольного графа из Р(п - 1) (число их по следствию из леммы о рукопожатиях четно) соединить с п-й вершиной, то получим граф из Ро{п). Таким образом, Дальнейшее просто