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

Циклы – очень важная часть структуры графа, с ними приходится иметь дело при решении многих задач. В графе может быть очень много циклов (см. задачу 5.15), поэтому полезно иметь средства для компактного описания множества всех циклов данного графа и манипулирования ими. Одно из наиболее удобных средств такого рода предоставляет аппарат линейной алгебры.

Далее будем рассматривать графы с фиксированным множеством вершин V. Буквой O будем обозначать пустой граф: .

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

Следующие свойства введенной операции очевидны или легко проверяются.

1) Коммутативность: для любых и .

2) Ассоциативность: для любых .

3) для любого G.

4) для любого G.

Отсюда следует, что множество всех графов с множеством вершин V образует абелеву группу относительно операции сложения по модулю 2. Нейтральным элементом («нулем») этой группы служит граф O, а противоположным к каждому графу является сам этот граф. Уравнение с неизвестным X и заданными графами G и H имеет единственное решение . Благодаря свойству ассоциативности мы можем образовывать выражения вида , не используя скобок для указания порядка действий. Легко понять, что ребро принадлежит графу тогда и только тогда, когда оно принадлежит нечетному количеству из графов .

Рассмотрим множество из двух элементов {0,1}. Оно является полем относительно операций умножения и сложения по модулю 2. Определим операцию умножения элементов этого поля на графы: , для любого графа G. Множество всех графов с множеством вершин V при введенных операциях сложения графов и умножения на элементы поля является линейным векторным пространством (т. е. подчиняется аксиоматике таких пространств).

Зафиксируем некоторый граф и рассмотрим множество всех его остовных подграфов. Это множество состоит из элементов, среди них сам граф G и граф . Оно замкнуто относительно сложения графов и умножения на элементы поля, следовательно, является подпространством пространства всех графов. Его называют пространством подграфов графа G.

В пространстве подграфов можно естественным способом ввести координаты. Занумеруем ребра графа G: . Теперь остовному подграфу можно поставить в соответствие характеристический вектор его множества ребер:

Получаем взаимно однозначное соответствие между множеством подграфов и множеством -мерных двоичных векторов. Сумме графов соответствует векторная (покоординатная) сумма по модулю 2 их характеристических векторов.

Далее в этом разделе слово «цикл» будем понимать несколько иначе, чем до сих пор.Именно, циклом графа G будемназывать его остовный подграф, у которого одна компонента связности является простым циклом, а остальные – изолированными вершинами. Остовный подграф, у которого степени всех вершин четны, называется квазициклом. Таким образом, любой цикл является квазициклом и граф О – квазицикл.

Теорема о квазициклах. Множество всех квазициклов данного графа замкнуто относительно сложения по модулю 2.

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

Компактное представление линейного векторного пространства дает его базис. Базис пространства циклов называют просто базисом циклов. Построить базис циклов можно следующим образом. Выберем в графе G какой-нибудь каркас T. Пусть – все ребра графа G, не принадлежащие T. Если добавить к T ребро , то в полученном графе образуется единственный цикл . Таким образом, получаем семейство из s циклов, они называются фундаментальными циклами относительно каркаса T.

Теорема о фундаментальных циклах. Множество всех фундаментальных циклов относительно любого каркаса T графа G образует базис пространства циклов этого графа.

Из этой теоремы следует, что размерность пространства циклов графа равна числу ребер, не входящих в его каркас. Так как каркас содержит ребер, где k – число компонент связности графа, то эта размерность равна . Это число называют цикломатическим числом графа.

Каркас графа можно построить многими способам. Для построения базиса циклов графа особенно удобен поиск в глубину благодаря основному свойству DFS-дерева – каждое обратное ребро относительно этого дерева является продольным. Это означает, что из двух вершин такого ребра одна является предком другой в DFS-дереве. Каждое такое ребро в процессе поиска в глубину встретится дважды ­– один раз, когда активной вершиной будет предок, другой раз, когда ею будет потомок. В этом последнем случае искомый фундаментальный цикл состоит из рассматриваемого обратного ребра и участка пути в DFS-дереве, соединяющего эти две вершины. Но этот путь так или иначе запоминается в процессе обхода в глубину, так как он необходим для последующего возвращения. Если, например, для хранения открытых вершин используется стек, то вершины этого пути находятся в верхней части стека. В любом случае этот путь легко доступен и цикл находится без труда.

Хотя сам поиск в глубину выполняется за линейное от числа вершин и ребер время, решающее влияние на трудоемкость алгоритма оказывает необходимость запоминать встречающиеся циклы. Подсчитаем суммарную длину фундаментальных циклов, полученных с помощью поиска в глубину для полного графа с n вершинами. DFS-дерево в этом случае является простым путем, относительно него будет цикла длины 3, цикла длины 4, …, 1 цикл длины n. Сумма длин всех фундаментальных циклов будет равна

.

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

С пространством циклов тесно связано пространство разрезов графа. Пусть , . Разрез графа G, определяемый множеством А, – это остовный подграф, ребрами которого являются все ребра графа, соединяющие вершины из А с вершинами из .

Теорема о разрезах. Множество всех разрезов данного графа замкнуто относительно сложения по модулю 2.

Разрез, определяемый одноэлементным множеством А, называется элементарным. Базис пространства разрезов связного графа можно получить, если взять все его элементарные разрезы, кроме одного (любого). Для несвязного графа это нужно проделать для каждой компоненты связности. Таким образом, размерность пространства разрезов графа с k компонентами равна .

Пусть и – характеристические векторы двух остовных подграфов графа G. Будем говорить, что эти подграфы ортогональны, если . Это равносильно тому, что подграфы имеют четное число общих ребер.

Теорема о циклах и разрезах. Любой цикл данного графа ортогонален любому его разрезу.

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

Рис. 8

матрицу инцидентности и удалим из нее одну (любую) строчку (в случае несвязного графа удаляется по одной строке из каждой компоненте связности):

Строки этой матрицы – характеристические векторы элементарных разрезов, образующих базис разрезов. Так как пространство циклов является ортогональным дополнением пространства разрезов, то остается найти фундаментальную систему решений системы линейных однородных уравнений с этой матрицей (над полем из двух элементов). Для этого с помощью операций над строками преобразуем матрицу так, чтобы в первых столбцах образовалась единичная подматрица:

Удаляем первые четыре столбца, оставшуюся матрицу транспонируем и приписываем кт ней справа единичную подматрицу:

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

Задачи

5.1. Сколько существует абстрактных эйлеровых графов с 5 вершинами?

5.2. Граф нужно превратить в эйлеров, изменяя (удаляя и добавляя) ребра. Каково

наименьшее число изменений, если разрешается а) только удалять ребра; б) только

добавлять ребра; в) и удалять, и добавлять?

5.3. Проследите работу алгоритма построения эйлерова цикла на графе . Вершины

одной доли имеют номера 1-4, другой – номера 5-8, старт в вершине1. Всякий раз,

когда имеется несколько непройденных ребер, по которым можно продолжить

движение, выбирается то из них, которое ведет в вершину с наименьшим номером.

5.4. Алгоритм построения эйлерова цикла применяется к графу . Каков будет ответ

(содержимое стека С в конце работы алгоритма)?

5. 5. Что нужно изменить в алгоритме построения эйлерова цикла, чтобы получился

алгоритм построения эйлерова пути в графе с двумя вершинами нечетной степени?

5.6. С помощью графа де Брейна найдите последовательность де Брейна 1) порядка 4 для

двухбуквенного алфавита; 2) порядка 2 для четрехбуквенного алфавита.

5.7. Сколько существует абстрактных графов с 5 вершинами, имеющих гамильтонов

цикл?

5.8. В каких из следующих графов имеется гамильтонов цикл?

1) ; 2) ; 3) ; 4) ; 5) .

5.9. При каких p и q в графе имеется а) гамильтонов цикл? Б) гамильтонов путь?

5.10. При каких n существует гамильтонов цикл в графе а) ; б) ?

5.11. Постройте дерево путей для графа, изображенного на рисунке а) с корнем в

вершине 1; б) с корнем в вершине 2.

5.12. Сколько листьев будет в дереве путей для графа ?

5.13. Найдите гамильтонов путь в графе .

5.26. Найдите гамильтонов путь в турнире, заданном матрицей смежности:

5.15. Сколько в полном графе имеется подграфов, изоморфных а) ; б) ;

в) , ?

5.16. Операция сложения графов по модулю 2 может быть распространена на графы с

разными множествами вершин следующим образом: если ,

, то . Можно ли с помощью этой операции, а

также удаления и добавления изолированных вершин и переименования вершин

получить а) из ; б) из ; в) из ; г) из ?

5.17. Связный граф имеет 10 вершин, 4 из них имеют степень 6, остальные – степень 3.

Чему равно цикломатическое число этого графа?

5.18. Постройте фундаментальные циклы для графа относительно каркаса,

полученного с помощью а) поиска в глубину; б) поиска в ширину. Выразите границу

внешней грани как сумму базисных циклов.

5.19. Какова будет суммарная длина фундаментальных циклов, построенных с помощью

поиска в ширину для графа а) ; б) ?

a

5.20. Сколько различных разрезов имеется а) у связного графа с n вершинами;

б) у графа с k компонентами и n вершинами?

5.21. Найдите базис циклов по матрице инцидентности для графа, показанного на

рисунке.

5.22*. Модифицируйте алгоритм построения эйлерова цикла так, чтобы не требовалась

предварительная проверка четности степеней. Существование вершины нечетной

степени должно обнаруживаться по ходу работы алгоритма.

5.23*. Докажите, что при любом в графе существует гамильтонов цикл.

5.24*. Разработайте алгоритм построения дерева путей и поиска гамильтонова цикла.

5.25*. Докажите, что в любом сильно связном турнире имеется гамильтонов цикл.

5.26.* Разработайте алгоритм построения базиса циклов на основе поиска в ширину.