Пространство подграфов
Зафиксируем некоторое множество $$V$$
и рассмотрим множество $$\Gamma_{V}$$ всех графов с множеством
вершин $$V$$. Буквой $$O$$ будем
обозначать пустой граф из этого множества: $$O=(V,\varnothing)$$.
Для графов $$G_{1} =(V,E_{1})$$ и $$G_{2} =(V,E_{2} )$$
из $$\Gamma_{V}$$ определим их сумму по модулю $$2$$
(в дальнейшем в этом разделе
будем называть ее просто суммой) как граф $$G_{1} \oplus G_{2} =(V,E_{1}
\oplus E_{2} ),$$ где $$E_{1} \oplus E_{2}$$ обозначает
симметрическую
разность множеств $$E_{1}$$ и $$E_{2}$$. Иначе говоря, ребро
принадлежит графу $$G_{1} \oplus G_{2}$$ тогда и только тогда, когда
оно принадлежит в точности одному из графов $$G_{1}$$ и $$G_{2}$$. Пример показан на рис. 7.1.
(рис 7.1) Следующие свойства введенной операции очевидны или легко проверяются.
Коммутативность: $$G_{1} \oplus G_{2} =G_{2} \oplus G_{1}$$ для
любых $$G_{1}$$ и $$G_{2}$$.
Ассоциативность: $$G_{1} \oplus (G_{2} \oplus G_{3} )=(G_{1} \oplus
G_{2} )\oplus G_{3}$$ для любых $$G_{1},G_{2},G_{3}$$.
$$G\oplus O=G \text{ для любого } G$$.
$$G\oplus G=O \text{ для любого } G$$.
Отсюда следует, что множество $$\Gamma _{V}$$ относительно
операции $$\oplus$$ образует абелеву группу. Нейтральным элементом
("нулем") этой группы
служит граф $$O$$, а противоположным к каждому графу является сам
этот граф. Уравнение $$G\oplus X=H$$ с неизвестным $$X$$
и заданными графами $$G$$ и $$H$$ имеет единственное
решение $$X=G\oplus H$$.
Благодаря свойству ассоциативности мы можем образовывать
выражения вида $$G_{1} \oplus G_{2} \oplus \ldots \oplus G_{k}$$, не
используя скобок для указания порядка действий. Легко понять, что ребро
принадлежит графу $$G_{1} \oplus G_{2} \oplus \ldots \oplus G_{k}$$
тогда и только тогда, когда оно принадлежит нечетному количеству из графов $$G_{1},G_{2},\ldots,G_{k}$$.
Рассмотрим множество из двух элементов $$\{0, 1\}$$. Оно является
полем
относительно операций умножения и сложения по модулю 2. Определим операцию
умножения элементов этого поля на графы: $$0\cdot G=O$$, $$1\cdot
G=G$$ для
любого графа $$G$$. Множество $$\Gamma_{V}$$ с введенными
операциями
сложения графов и умножения на элементы поля является линейным векторным
пространством.
Зафиксируем некоторый граф $$G\in \Gamma_{V}$$
и рассмотрим множество
всех его остовных подграфов, которое будем обозначать $$S[G]$$. Это
множество состоит из $$2^{m(G)}$$ элементов, среди них сам
граф $$G$$
и граф $$O$$. Оно замкнуто относительно сложения графов и
умножения на
элементы поля, следовательно, является подпространством пространства $$\Gamma_{V}$$. Его называют пространством подграфов графа $$G$$.
Любой граф из $$S[G]$$ может быть выражен как сумма однореберных
подграфов. Всего у графа $$G$$ имеется $$m(G)$$
однореберных
подграфов и они, очевидно, линейно независимы.
Следовательно, однореберные
подграфы образуют базис пространства $$S[G]$$, а размерность этого
пространства равна $$m(G)$$.
В пространстве $$S[G]$$ можно очень естественным способом ввести
координаты. Занумеруем ребра графа $$G$$: $$EG=\{e_{1},e_{2},\ldots ,e_{m} \}$$.
Теперь остовному подграфу $$H$$ можно поставить
в соответствие характеристический
вектор $$\alpha (H)=(\alpha _{1} ,\alpha_{2},\ldots,\alpha_{m})$$
его множества ребер:
$$\alpha _{i} =\left\{\begin{aligned} 1, \text{если ребро }e_{i}\
\text{принадлежит } H, \\ 0, \text{если } e_{i}\ \text{не принадлежит } H.
\end{aligned}\right}$$
Получаем взаимно однозначное соответствие между множеством $$S[G]$$
и множеством всех двоичных векторов с $$m$$ координатами. Сумме
графов
соответствует векторная (покоординатная) сумма по модулю 2 их
характеристических векторов.
Квазициклы
В этом разделе слово "цикл" мы будем понимать несколько иначе,
чем до сих
пор. Именно, циклом будем называть граф, у которого одна компонента
связности является простым циклом, а остальные - изолированными
вершинами.
На рис. 7.1 показано, что в результате сложения двух циклов иногда
получается цикл. Это не всегда так (например, когда складываемые циклы не
имеют общих ребер), но все-таки графы, которые можно получить, складывая
циклы, обладают определенными особенностями. На этом основан
алгебраический подход к изучению устройства множества циклов графа.
Рассмотрим некоторый граф $$G\in \Gamma_{V}$$. Среди его
остовных
подграфов, возможно, имеется некоторое количество циклов. Обозначим
через $$C[G]$$ подпространство пространства подграфов, порождаемое
всеми этими
циклами. $$C[G]$$ называется пространством циклов графа $$G$$.
Оно содержит граф $$O$$ (если в $$G$$ нет циклов,
то $$O$$
является единственным элементом пространства циклов), а все
остальные его элементы - это всевозможные линейные комбинации циклов
графа $$G$$. Заметим, что коэффициентами в линейных комбинациях
являются
элементы множества $$\{0,1\}$$, поэтому речь идет на самом деле просто
о всевозможных суммах циклов.
Остовный подграф, у которого степени всех вершин четны, называется квазициклом. Оказывается,
множество $$C[G]$$ состоит в точности из всех
квазициклов графа $$G$$. Прежде чем доказать это, покажем сначала, что
множество всех квазициклов замкнуто относительно сложения.
Лемма 1. Сумма двух квазициклов есть квазицикл.
Доказательство. Пусть $$H_{1}$$ и $$H_{2}$$ - квазициклы.
Рассмотрим произвольную вершину $$a\in V$$, и пусть ее степени
в $$H_{1}$$ и $$H_{2}$$ равны соответственно $$d_{1}$$ и $$d_{2}$$.
Тогда степень вершины $$a$$ в графе $$H_{1} \oplus H_{2}$$
будет равна $$d=d_{1}+d_{2} -2d_{1,2}$$, где $$d_{1,2}$$
- число
вершин, с которыми $$a$$ смежна в обоих графах $$H_{1}$$ и $$H_{2}$$.
Отсюда видно, что число $$d$$ четно, если четны оба
числа $$d_{1}$$ и $$d_{2}$$.
Следующая лемма объясняет строение квазициклов.
Лемма 2. Любой квазицикл с непустым множеством ребер является
объединением простых циклов, не имеющих общих ребер.
Доказательство. В квазицикле $$H$$ в любой компоненте
связности, состоящей не менее чем из двух вершин, степени всех вершин не
меньше 2, следовательно, в нем есть цикл, а, значит, и простой цикл. Взяв
какой-нибудь простой цикл в $$H$$ и удалив его ребра
из $$H$$,
снова получим квазицикл. Если в этом новом квазицикле есть хотя бы
одно ребро, то в нем также имеется простой цикл, и т.д. В конце концов,
когда останется пустой граф, будет построено семейство простых циклов, не
имеющих общих ребер и в совокупности содержащих все ребра графа $$H$$.
Теорема 1. Граф принадлежит множеству $$C[G]$$ тогда и только тогда, когда он
является квазициклом графа $$G$$.
Доказательство. Всякий цикл является квазициклом. Так как элементы $$C[G]$$ - это суммы циклов, то, по лемме 1, все
они - квазициклы. Обратное
утверждение (каждый квазицикл принадлежит $$C[G]$$ )
следует из леммы 2,
так как объединение циклов, не имеющих общих ребер, совпадает
с их суммой.
Фундаментальные циклы
Компактное представление пространства дает его базис. Если выписать все
простые циклы графа $$G$$, то это в большинстве случаев не будет его
базисом, так как некоторые из этих циклов могут быть суммами других
(см. пример на рис. 7.1). Построить базис пространства $$C[G]$$, состоящий из простых циклов, можно следующим образом. Выберем в графе $$G$$
какой-нибудь каркас $$T$$. Пусть $$e_{1},\ldots e_{s}$$
- все ребра
графа $$G$$, не принадлежащие $$T$$. Если добавить к $$T$$
ребро $$e_{i}$$, то в полученном графе образуется единственный
(простой)
цикл $$Z_{i}$$. Таким образом, получаем семейство из $$s$$
циклов,
они называются фундаментальными циклами относительно
каркаса $$T$$.
Теорема 2. Множество всех фундаментальных циклов относительно
любого каркаса $$T$$ графа $$G$$ образует базис
пространства циклов этого графа.
Доказательство. Зафиксируем некоторый каркас $$T$$ и рассмотрим
фундаментальные циклы $$Z_{1},Z_{2},\ldots ,Z_{s}$$ относительно
этого
каркаса. В каждом из этих циклов имеется ребро $$e_{i}$$,
принадлежащее
данному циклу и не принадлежащее никакому из остальных. Поэтому при
сложении этого цикла с другими фундаментальными циклами данное
ребро не "уничтожится" - оно будет присутствовать в
суммарном графе.
Следовательно, сумма различных фундаментальных циклов никогда не будет
пустым графом, то есть фундаментальные циклы линейно независимы.
Покажем теперь, что любой квазицикл графа $$G$$ является суммой
фундаментальных циклов. Действительно, пусть $$H$$ - такой
квазицикл.
Пусть $$e_{i_{1}},e_{i_{2}},\ldots e_{i_{t} }$$ - все
ребра $$H$$,
не принадлежащие $$T$$. Рассмотрим граф $$F=H\oplus Z_{i_{1}}
\oplus Z_{i_{2}} \oplus \ldots \oplus Z_{i_{t} }$$. Каждое из ребер $$e_{i_{j} }$$, $$j=1,\ldots t$$, входит ровно в два
слагаемых этой
суммы - в $$H$$ и в $$Z_{i_{j} }$$. Следовательно,
при сложении все
эти ребра уничтожатся. Все остальные ребра, присутствующие
в графах-слагаемых, принадлежат $$T$$. Значит, $$F$$
- подграф
графа $$T$$. Так как все слагаемые являются квазициклами,
значит, $$F$$ -
тоже квазицикл. Но в $$T$$ нет циклов, поэтому имеется
единственная возможность: $$F=O$$, откуда получаем $$H=Z_{i_{1}} \oplus Z_{i_{2}} \oplus \ldots \oplus Z_{i_{t}}$$.
Из этой теоремы следует, что размерность пространства циклов графа равна
числу ребер, не входящих в его каркас. Так как каркас содержит $$n-k$$
ребер, где $$k$$ - число компонент связности графа, то эта
размерность
равна $$\nu (G)=m-n+k$$. Это число называют цикломатическим числом
графа.
Построение базы циклов
Базис пространства циклов графа коротко называют базой циклов.
На основании теоремы 2 можно предложить достаточно простой способ построения
базы циклов графа. Сначала находится какой-нибудь каркас, затем для
каждого ребра, не принадлежащего каркасу, отыскивается тот единственный
цикл, который это ребро образует с ребрами каркаса. Таким образом, любой
алгоритм построения каркаса может быть использован для нахождения базы
циклов.
Поиск в глубину особенно удобен благодаря основному свойству DFS-дерева
(теорема 1 из лекции 5) - каждое обратное ребро относительно этого дерева
является продольным. Это означает, что из двух вершин такого ребра одна
является предком другой в DFS-дереве. Каждое такое ребро в процессе поиска
в глубину встретится дважды - один раз, когда активной вершиной будет
предок, другой раз, когда ею будет потомок. В этом последнем случае
искомый фундаментальный цикл состоит из рассматриваемого обратного ребра
и участка пути в DFS-дереве, соединяющего эти две вершины. Но этот путь так
или иначе запоминается в процессе обхода в глубину, так как он необходим
для последующего возвращения. Если, например, для хранения открытых вершин
используется стек, то вершины этого пути находятся в верхней части стека.
В любом случае этот путь легко доступен и цикл находится без труда.
Запишем процедуру построения фундаментальных циклов на базе алгоритма
поиска в глубину с построением DFS-дерева. Переменная $$k$$ -
счетчик
циклов, $$C(k)$$ - последовательность (список) вершин,
составляющих цикл
с номером $$k$$.
Алгоритм 1. Построение базы циклов.
пометить все вершины как новые
$$k:=1$$
for $$x\in V$$ do if $$x$$
новая then $$CycleBase(x)$$
Procedure $$CycleBase(a)$$
открыть вершину $$a$$
$$F(a)\, :=a$$
$$x\, :=a$$
while $$x$$ открытая do
if имеется неисследованное
ребро $$(x,y)$$
then пометить ребро $$(x,y)$$
как исследованное
if вершина $$y$$ новая
then открыть
вершину $$y$$
$$F(y):=x$$
$$x:=y$$
else $$NewCycle$$
else закрыть вершину $$x$$
$$x:=F(x)$$
Procedure $$NewCycle$$
$$k:=k+1$$
Создать список $$C(k)$$ из одного элемента $$x$$
$$z:=x$$
repeat $$z:=F(z)$$
добавить $$z$$ к списку $$C(k)$$
until $$z=y$$
Хотя сам поиск в глубину выполняется за линейное от числа вершин и ребер
время, решающее влияние на трудоемкость этого алгоритма оказывает
необходимость запоминать встречающиеся циклы. Подсчитаем суммарную длину
этих циклов для полного графа с $$n$$ вершинами. DFS-дерево в этом
случае является простым путем, относительно него будет $$n-2$$
цикла
длины $$3$$, $$n-3$$ цикла длины $$4\ldots 1$$ цикл
длины $$n$$. Сумма
длин всех фундаментальных циклов будет равна
$$\sum_{i=1}^{n-2}i(n+1-i)=\frac{n^{3} + 3n^{2} -16n+12}{6}.$$
Таким образом, на некоторых графах число операций этого алгоритма будет
величиной порядка $$n^{3}$$.
Рационализация
Приведенный алгоритм нетрудно модифицировать так, что он будет строить
базу циклов с суммарной длиной, ограниченной сверху величиной
порядка $$n^{2}$$ (и такой же будет оценка трудоемкости алгоритма).
Рассмотрим в графе произвольную вершину $$x$$
и пусть $$y_{1},y_{2}\ldots y_{k}$$ - все ее предки в DFS-дереве,
соединенные с $$x$$ обратными ребрами.
Положим также $$y_{k+1} =x$$. Обозначим через $$P_{i}$$ для $$i=1,\ldots,k$$
путь в DFS-дереве, соединяющий $$y_{i}$$ и $$y_{i+1}$$. Описанный выше алгоритм выдает
циклы вида $$C_{i} =xP_{i} P_{i+1} \ldots P_{k} x$$, $$i=1,\ldots,k$$. Рассмотрим
циклы $$C'_{i} =xP_{i}x$$, $$i=1,\ldots,k$$. Так
как $$C_{i}
=C'_{i} \oplus C'_{i+1} \oplus \ldots \oplus C'_{k}$$,
то совокупность всех таких циклов также образует базу
циклов графа. Назовем эту систему
циклов сокращенной.
Алгоритм легко модифицировать так, чтобы вместо циклов $$C_{i}$$ выдавались циклы $$C'_{i}$$ - нужно
только после обнаружения
обратного ребра, ведущего от предка $$x$$ к потомку $$y$$
(строка 11), выписать вершины, содержащиеся в стеке, начиная
с $$y$$ и заканчивая следующей вершиной,
смежной с $$x$$. Для эффективной
проверки этой смежности удобно использовать матрицу смежности.
Оценим суммарную длину $$S$$ циклов сокращенной системы.
Предположим,
что граф имеет $$n$$ вершин и $$m$$ ребер. Каждое обратное
ребро
принадлежит не более чем двум циклам сокращенной системы. Значит,
суммарный вклад обратных ребер в $$S$$ не
превосходит $$2m$$.
Для каждого цикла из сокращенной системы назовем верхушкой этого цикла
вершину цикла с наибольшим глубинным номером (это та вершина $$x$$,
при исследовании окрестности которой был найден данный цикл). Очевидно,
для каждого прямого ребра в сокращенной системе имеется не более одного
цикла с данной верхушкой. Значит, число циклов, в которые входит данное
прямое ребро, не превосходит числа вершин, лежащих в дереве выше него
(т.е. являющихся потомками вершин этого ребра). Тем более это число не
превосходит числа всех вершин графа. Так как имеется не более
чем $$n-1$$
прямое ребро, то для суммарного вклада всех прямых ребер в $$S$$
получаем верхнюю оценку $$n^{2}$$. Таким образом, $$S < 2m+n^{2}
=O(n^{2})$$,
т.е. на порядок меньше максимальной суммарной длины системы
фундаментальных циклов.
