6.12. Циклы, фундаментальные множества циклов

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

Полезность фундаментального множества циклов вытекает из того факта, что это множество полностью определяет циклическую структуру графа: каждый цикл в графе может быть представлен комбинацией циклов из фундаментального множества. Пусть фундаментальное множество циклов, где каждый цикл С, является подмножеством ребер Тогда любой цикл графа можно записать в виде где символ обозначает операцию симметрической разности,

Например, на рис. 6.35 показан граф и фундаментальное множество циклов, получающихся из выделенного жирной линией остовного дерева графа. Цикл графа есть или цикл есть Отметим, что в общем случае не каждая сумма циклов будет являться циклом графа.

Рис. 6.35. Граф, его остовное дерево и фундаментальное множество циклов

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

Программная реализация поиска фундаментального множества циклов представлена в алгоритме 6.16.

Алгоритм 6.15. Фундаментальные циклы графа

(см. скан)

(см. скан)

Алгоритм 6.16. Программа поиска фундаментальных циклов

графа

(см. скан)

(см. скан)

(см. скан)

(см. скан)

Рассмотрим пример расчета по программе алгоритма 6.16 фундаментального множества циклов для графа, представленного на рис. 6.35. Исходные данные структуры смежности графа задаются в текстовом файле

Результаты расчетов сохраняются в текстовом файле со следующей структурой:

Каждая строка в выходном файле — это найденный цикл, который представляется последовательностью вершин. Начальный номер в строке — номер цикла по порядку.