Алгоритмтм Флёри.

1. Начинаем с любой вершины. Проходим вдоль любого ребра до другой вершины. Запомина-ем это ребро как начало цикла и удаляем его из графа.

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

3. Выполняем шаг 2 до тех пор, пока не удалим все рёбра из графа.

Пример 30. Применим алгоритм Флёри к графу, показанному на рис.30 a. Прежде всего проверяем, что граф связен и степени всех вершин чётны. По теореме Эйлера из этого следует, что эйлеров цикл в таком графе должен быть.

Рис.30

Начинаем процесс с вершины 3. Из 3 можно двигаться либо в 2, либо в 5. Пойдём по на-правлению к 5, удалив ребро {3, 5} (на рисунке 30 b указаны номера удаляемых рёбер в порядке их удаления). Таким образом, началом искомого цикла является ребро {3, 5}. Далее можно дви-гаться в вершины 4, 6 или 7. Поскольку ни одно из рёбер {5, 4}, {5, 6} и {5, 7} в графе после удаления ребра {3, 5} не является перешейком, то можно выбрать в качестве 2-го ребра цикла любое из этих трёх рёбер. Выбираем ребро {5, 7}. На рис.30 b это ребро имеет номер 2, а начало искомого цикла выглядит так: 3→5→7.

Далее, из вершины 7можно перейти в вершины 1, 4 или 6. Однако ребро {7, 1} является перешейком в графе, полученном удалением рёбер {3, 5} и {5, 7} (см. рис.30 b). Так как есть другие возможности ({7, 4} и {7, 6}), в соответствии с алгоритмом Флёри выберем одну из них. Выбрав {7, 6 }, продлеваем строящийся цикл этим самым ребром {7,6} и получаем 3→5→7→6; удаляемые рёбра и модифицированный граф показаны на рис.30 b. Заметим, что выбор пере-шейка {7, 1} в графе, показанном на рис.30 b, и его последующее удаление привели бы к невоз-можности когда-либо пройти по рёбрам {7, 4} и {7, 6}. Это поясняет условие на шаге 2 алго-ритма Флёри.

Граф, оставшийся после удаления первых трёх рёбер искомого цикла – {3, 5}, {5, 7} и {7,6} – показан на рис.30 с. Из очередной вершины 6 в графе рис.30 с выходит только одно ребро {6,5}, которое является перешейком в этом графе. В соответствии с алгоритмом Флёри, мы должны двигаться далее по этому ребру {6,5}, несмотря на то, что {6,5} является перешейком, так как других возможностей нет. Далее все последующие рёбра определяются также совер-шенно однозначно (см. рис.30 с). В результате получаем эйлеров цикл 3→5→7→6→5→4→7→

1→2→3. В него по одному разу входят все 9 рёбер рассматриваемого графа. Полная последова-тельность удаляемых по порядку рёбер представлена на рис.30 d.

Задание 15. В неориентированных графах, показанных на рис.31, найти эйлеров цикл, пользуясь алгоритмом Флёри. Решение должно быть представлено, как в примере 30. Это озна-чает, что должны быть подробно показаны все шаги и должны быть отмечены все встречаемые перешейки, вплоть до ситуации, когдадальнейшие рёбра определяются совершенно однознач-но ■

Дата добавления: 2015-10-16