Пространство циклов графа

Понятие фундаментального цикла вводится следующим образом. Пусть в связном графе G= <V, E> произвольно фиксировано максимальное остовное дерево Т(V, E_T). Рёбра графа G, не принадлежащие дереву Т, называются хордами, а множество хорд T* = E\E_T, называется кодеревом графа G, соответствующим дереву Т. Таким образом, каждый максимальный остов однозначно определяет разбиение рёбер графа на подмножества древесных рёбер и хорд.

Алгоритмы поиска в глубину и в ширину строят остовные деревья, причём изменение порядка вершин в списках смежности (и выбор начальной вершины) приводит к построению алгоритмами разных остовных деревьев. Однако, не все деревья удаётся построить с помощью поиска в глубину – см. пример.

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

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

Пусть граф G = <V, E> имеет n вершин и m рёбер. Если n=m+1, то граф – дерево. Если же n £ m, то в графе есть цикл. После удаления ребра из цикла граф остаётся связным. Если это не дерево, можно снова найти цикл и удалить из него ребро. Продолжая процедуру, приходим в конце концов к некоторому остовному дереву. Количество удалённых рёбер, таким образом, будет в точности равно циклическому рангу графа: C(G) = m – n + 1. Ранг дерева равен 0, графа с одним циклом – 1 и т.д. Изменение порядка удаления рёбер из данного графа приводит, вообще говоря, к разным остовным деревьям, но циклический ранг, очевидно, от этого не зависит.

Во многих задачах требуется перечислить все остовные деревья и выбрать из них оптимальное. В силу установленной однозначной связи остов Þ множество хорд «множество фундаментальных циклов эту задачу можно решать разными способами.

Алгебраический подход. Каждый цикл а = (v(i₁), …, v(i_k)) в графе однозначно задаёт множество рёбер С(а) Ì Е. Обратно, если некоторое множество рёбер С образует цикл, то по нему можно восстановить последовательность вершин цикла (v(i₁), …, v(i_k)) – с точностью до выбора начальной вершины и направления обхода. Таким образом, можно отождествить множество циклов графа и семейство подмножеств множества рёбер. Пользуясь этим соответствием, введём на множестве циклов графа структуру векторного пространства.

Определим операцию сложения для циклов:

a + b F C(a) D C(b); 0 F Æ.

Результат операции, вообще говоря, будет не циклом, а дизъюнктивным (несвязным) объединением циклов. Если к операции сложения добавить умножение на число из поля Галуа Z₂:

0 a F 0, 1 a F a;

то полученное линейное пространство будет называться пространством циклов.

Линейность пространства позволяет ввести понятия линейной комбинации и линейной независимости и воспользоваться результатами теории векторных пространств. Именно: а) пространство циклов характеризуется определённой размерностью r; б) любой цикл может быть представлен в виде суммы по r базисным векторам. Нетрудно понять, что базисом является любая система фундаментальных циклов, r есть циклическое число графа, а выбор разных остовов есть переход к другому базису в пространстве циклов. Следствием также является утверждение о равенстве числа удалённых хорд циклическому рангу графа C(G) = r.

Пример. Граф с 6-ю вершинами имеет 4 фундаментальных цикла, определяемых остовом. Симметрическая разность Z₁DZ₄ даёт те же 2 цикла, симметрическая разность Z₁DZ₂DZ₃DZ₄ – внешнюю границу графа. Симметрическая разность даёт Z₁DZ₃DZ₄ эйлеров цикл данного графа.

Замечание. Четыре естественных треугольника являются базисом пространства циклов, но не являются фундаментальной системой ни для какого остова.

В последующем алгоритме для построения остова используется задание графа списком рёбер. Остов графа G получается в результате «разрастания» леса, являющегося подграфом G.

Алгоритм построения остова для произвольного графа G.

1. Выбрать произвольное ребро, не являющееся петлёй. Пометить его меткой a и объявить (под)деревом это ребро вместе с концевыми вершинами.

2. Выбрать следующее ребро, не являющееся петлёй:

а) если оба конца выбранного ребра принадлежат одному дереву, пометить его меткой b и перейти к шагу 3;

б) если один из концов ребра принадлежит построенному ранее (под)дереву В, а другой конец свободен (не принадлежит ни одному дереву), пометить его меткой a, включить его вместе с концами в дерево В и перейти на метку 3;

в) если концы выбранного ребра принадлежат построенным ранее деревьям В и С, пометить выбранное ребро меткой a, включить его и дерево С в дерево В и перейти к шагу 3;

г) если оба конца ребра свободны, пометить его меткой a, объявить это ребро вместе с вершинами новым деревом в лесу и перейти на 3;

если непомеченных рёбер нет, закончить алгоритм.

3. Если все вершины графа G вошли в одно дерево, закончить алгоритм. Если нет, перейти к шагу 2.

Под словом «выбрать» подразумевается некоторая процедура перечисления рёбер – это может быть случайный выбор, выбор в соответствии с некоторыми приоритетами – например, весом, цветом или стоимостью – так что необходимо использовать некоторую вспомогательную процедуру упорядочивания (сортировки) рёбер.

Замечание. Этот алгоритм, в принципе, может перебрать все остовы.