Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


Элементы цикломатики в теории графов

Элементы цикломатики в теории графов


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


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


Примечание. Отметим, что не любой базис может быть вычислен посредством поиска в глубину (см. граф на рис. 5.23).


Графы и множество их ребер, формирующие цепь

Пусть c — некоторая цепь графа G. Через E(c) обозначим множество ребер этой цепи. Для любой цепи с множество ее ребер E(c) определяется однозначно. Обратно, если фиксировано какое-то (конечное) множество ребер \{e_1,\ldots,e_n\} графа G, то можно доказать следующий факт: если указанное выше множество ребер формирует цепь, т.е. существует такая цепь (последовательность вершин графа) v_0,v_1,\ldots,v_n, что \{v_0,v_1\}= e_{i_1},\ldots, \{v_{n-1},v_n\}= e_{i_n}, где 1 \leqslant i_1,\ldots,i_n \leqslant n, то эта цепь при условии, что она не является циклом, определяется с точностью до порядка расположения ребер в последовательности (от v_0 к v_n или наоборот). Если цепь является циклом, то она определяется с точностью до порядка расположения ребер в последовательности и до выбора начальной вершины v_0. Так, на рис. 5.41 множество ребер \bigl\{\{v_1, v_2\},\{ v_2, v_3\},\{ v_3, v_5\},\{ v_5, v_6\}\bigr\} формирует цепь v_1, v_2, v_3, v_5, v_6, а также цепь v_6, v_5, v_3, v_2, v_1 ("инверсия" предыдущей цепи). Множество ребер \bigl\{\{v_1, v_2\},\{v_2, v_3\},\{v_3, v_1\}\bigr\} формирует цикл v_1, v_2, v_3, v_1 a вместе с ним циклы:


\begin{array}{lll}v_2,~ v_3,~ v_1,~ v_2;&\qquad v_3,~ v_1,~ v_2,~ v_3;&\qquad v_1,~ v_3,~ v_2,~ v_1;\\[2pt] v_3,~ v_2,~ v_1,~ v_3;&\qquad v_2,~ v_1,~ v_3,~ v_2;&\qquad {} \end{array}

Множество же ребер \bigl\{\{v_1,v_2\}, \{v_2,v_3\}, \{v_3,v_5\}, \{v_4,v_6\}\bigr\} не формирует никакой цепи.


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


Для двух произвольных цепей a,b графа G их сумму определим (с учетом сделанного выше замечания) так:


a\oplus b=E(a)\,\triangle\,E(b),

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

Сумма цепей, вообще говоря, не является цепью, т.е. соответствующее множество ребер в общем случае не формирует цепь. На рис. 5.41 сумма цепей v_1, v_3, v_4, v_6 и v_2, v_3, v_4, v_5, v_6 не есть цепь. Алгебра, системой образующих которой служит множество всех конечных цепей данного графа G, называют алгеброй цепей неориентированного графа G. Эта алгебра является абелевой группой в силу известных свойств операции симметрической разности множеств.


Любая абелева группа G=(M,\oplus,\bold{0}) может быть рассмотрена как линейное пространство над полем \mathbb{Z}_2 (полем вычетов по модулю 2). Действительно, определим умножение элемента g группы на элементы поля \mathbb{Z}_2\colon\, 0\cdot g=\bold{0} и 1\cdot g=g. Выполнение аксиом линейного пространства в этом случае можно легко проверить. Обратим внимание, что в любой линейной комбинации \textstyle{\sum\limits_{k=1}^{n}(\lambda_k\cdot e_k)} элементов e_1,\ldots, e_k такого линейного пространства каждый коэффициент \lambda_k равен либо 0, либо 1. Тогда понятно, что нетривиальная линейная комбинация элементов e_1,\ldots, e_k, т.е. линейная комбинация, не все коэффициенты которой равны 0, есть не что иное, как сумма элементов непустого подмножества множества \{e_1,\ldots, e_k\}.


Применив указанное построение к алгебре цепей неориентированного графа, получим линейное пространство цепей данного графа. Его называют пространством цепей графа. Заметим, что в этом пространстве каждый элемент противоположен себе самому, так как для каждого элемента a этого пространства a\oplus a=\varnothing (в силу известных свойств операции симметрической разности).


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


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


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



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


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


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


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


Пусть C_1 и C_2 — два цикла графа G. Если они не имеют ни общих вершин, ни общих ребер, то доказываемое утверждение тривиально. Предположим, что ребра


e_1=\{a_1,b_1\},\quad e_2=\{a_2,b_2\},\quad \ldots\quad e_n=\{a_n,b_n\}

есть все ребра, общие для циклов C_1 и C_2 (рис. 5.43). В каждом из рассматриваемых циклов для каждого i=\overline{1,n-1} существуют цепи, соединяющие вершины b_i и a_{i+1}. Обозначим их W_i^1 для первого и W_i^2 для второго цикла. Также существуют цепи, в первом цикле — W_0^1 и во втором — W_0^1, соединяющие вершины a_1 и b_n. Все эти цепи таковы, что не содержат ни одного из ребер e_i,~i= \overline{1,n}. Поскольку ребра e_i,~i= \overline{1,n} — все ребра, общие для циклов C_1 и C_2, то для каждого i= \overline{0,n-1} цепи W_i^1 и W_i^2 не имеют общих ребер и имеют две общие вершины (см. рис. 5.43). Это значит, что каждая сумма W_i^1\oplus W_i^2,~i=\overline{0,n-1}, есть цикл (в пространстве цепей графа G). Обозначим его \varkappa_i.


Цепи графа, не имеющие общих ребер и имеющие две общие вершины

Докажем, что циклы \varkappa_i попарно не пересекаются (т.е. не имеют попарно ни общих вершин, ни общих ребер). Действительно, цепи W_i^1 и W_j^1 при i\ne j не могут иметь ни общих вершин, ни общих ребер, так как вершины a_1,b_1, a_2,b_2,\ldots,a_n,b_n — это, по построению, все вершины, общие для циклов C_1 и C_2. В то же время (для фиксированного s\in\{1;2\}) никакие две цепи W_i^s и W_j^s при i\ne j не могут иметь общих вершин и ребер, так как тогда циклы C_1 или C_2 не были бы простыми цепями.


Итак, циклы \varkappa_i попарно не пересекаются. Тогда


C_1\oplus C_2= \varkappa_0\oplus \varkappa_1\oplus \ldots\oplus \varkappa_{n-1},

причем в том и только в том случае, когда множество ребер \{e_1,\ldots,e_n\} формирует цепь, написанная выше сумма есть цикл.


Аналогично рассматривается случай, когда циклы C_1 и C_2, не имея общих ребер, имеют общие вершины: a_1,a_2,\ldots,a_n (рис. 5.44). Тогда, как можно видеть на рис. 5.44, сумма C_1\oplus C_2 будет замкнутой цепью (которая в общем случае не будет циклом).


Граф с циклами и замкнутой цепью

Пусть C — произвольный цикл графа, а f_1,\ldots,f_m — все его обратные ребра, и пусть F_1,\ldots,F_m — фундаментальные циклы, содержащие ребра f_1,\ldots,f_m соответственно.


Рассмотрим суммы (в пространстве циклов):


\begin{aligned}&C\oplus F_1=C_1,\\ &C_1\oplus F_2=C\oplus F_1\oplus F_2=C_2,\\ &\cdots\cdots\cdots\cdots\cdots\\ &C_{m-2}\oplus F_{m-1}= C\oplus F_1\oplus \ldots\oplus F_{m-1}=C_{m-1}. \end{aligned}

Как было доказано выше, каждая из этих сумм есть либо замкнутая цепь, либо множество попарно не пересекающихся циклов, причем сумма C_i,~1\leqslant i\leqslant n-1, содержит обратные ребра f_{i+1},\ldots,f_m, и только их, так как при сложении C с F_1 исчезает общее для них ребро f_1, при сложении C_1 с F_2 — общее для них ребро f_2 и т.д. Следовательно, последняя из этих сумм содержит единственное обратное ребро f_m. Значит, сумма C_{m-1} есть цикл. В самом деле, если бы она была непустым множеством попарно не пересекающихся циклов, то содержала бы по крайней мере два таких цикла. Поскольку в C_{m-1} только одно обратное ребро, то по крайней мере один из этих циклов проходил бы только по древесным ребрам, что невозможно.


Аналогично, предполагая, что C_{m-1} есть замкнутая цепь, не являющаяся циклом, получим (с учетом следствия 5.1), что такая цепь представима в виде суммы по крайней мере двух циклов, не имеющих общих ребер. Тогда один из этих циклов содержит только древесные ребра, что невозможно.



Итак, сумма C_{m-1} есть цикл, содержащий только одно обратное ребро. В силу взаимно однозначного соответствия между множеством обратных ребер и множеством фундаментальных циклов цикл C_{m-1} совпадает с фундаментальным циклом F_m:


C_{m-1}=F_m, или C\oplus F_1\oplus F_2\oplus \ldots\oplus F_{m-1}=F_m,.

откуда (поскольку каждый элемент пространства циклов противоположен сам себе)

C=F_1\oplus F_2\oplus \ldots\oplus F_m\,.

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




Циклический и коциклический ранги графа


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


Выведем формулу, связывающую циклический ранг \nu, число ребер m, число вершин n и число компонент связности к произвольного неориентированного графа G.


Обозначим через \mu коциклический ранг графа G. Тогда, поскольку в неориентированном дереве число ребер на единицу меньше числа вершин, получим


\nu=m-\mu= m-\bigl((n_1-1)+\ldots+(n_k-1)\bigr)=m-n+k,

где n_i — число вершин в i-й компоненте связности графа G.


Итак, имеем \nu=m-n+k.


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


Циклический ранг неориентированного графа показывает "степень цикличности" этого графа: чем больше циклический ранг, тем больше в графе циклов. Лес, в частности дерево, имеет нулевой циклический ранг (нульмерное пространство циклов).




Пример 5.16. Рассмотрим неориентированные графы, изображенные на рис. 5.41. Предположим, что в списках смежности вершины упорядочены по возрастанию номеров. На рис. 5.41 показаны результаты поиска в глубину из двух разных вершин: v_1 в графе G_1 и v_4 в графе G_2. Древесные ребра в графах выделены. По результатам поиска циклический ранг равен 4, а коциклический ранг — 5. В графе G_1 фундаментальными являются циклы


\begin{array}{ll}C_1\colon~v_1 \shortmid\!\!\!-\!\!\!\shortmid v_5 \shortmid\!\!\!-\!\!\!\shortmid v_4 \shortmid\!\!\!-\!\!\!\shortmid v_6,&\qquad C_3\colon~v_4 \shortmid\!\!\!-\!\!\!\shortmid v_3 \shortmid\!\!\!-\!\!\!\shortmid v_2 \shortmid\!\!\!-\!\!\!\shortmid v_4,\\[2pt] C_2\colon~v_5 \shortmid\!\!\!-\!\!\!\shortmid v_3 \shortmid\!\!\!-\!\!\!\shortmid v_4 \shortmid\!\!\!-\!\!\!\shortmid v_5,&\qquad C_4\colon~v_3 \shortmid\!\!\!-\!\!\!\shortmid v_1 \shortmid\!\!\!-\!\!\!\shortmid v_2 \shortmid\!\!\!-\!\!\!\shortmid v_3. \end{array}

Записывая циклы (которые, по определению, есть последовательности вершин), мы .ради наглядности пишем между вершинами значок \shortmid\!\!\!-\!\!\!\shortmid непосредственной достижимости.


Циклы пронумерованы в порядке обнаружения. Для графа G_2 фундаментальными будут циклы


\begin{aligned}&D_1\colon~ v_3\shortmid\!\!\!-\!\!\!\shortmid v_2\shortmid\!\!\!-\!\!\!\shortmid v_1\shortmid\!\!\!-\!\!\!\shortmid v_3,\\ &D_2\colon~ v_3\shortmid\!\!\!-\!\!\!\shortmid v_4\shortmid\!\!\!-\!\!\!\shortmid v_2\shortmid\!\!\!-\!\!\!\shortmid v_1\shortmid\!\!\!-\!\!\!\shortmid v_3,\\ &D_3\colon~ v_5\shortmid\!\!\!-\!\!\!\shortmid v_4\shortmid\!\!\!-\!\!\!\shortmid v_2\shortmid\!\!\!-\!\!\!\shortmid v_1\shortmid\!\!\!-\!\!\!\shortmid v_3\shortmid\!\!\!-\!\!\!\shortmid v_5,\\ &D_4\colon~ v_6\shortmid\!\!\!-\!\!\!\shortmid v_4\shortmid\!\!\!-\!\!\!\shortmid v_2\shortmid\!\!\!-\!\!\!\shortmid v_1 \shortmid\!\!\!-\!\!\!\shortmid v_3 \shortmid\!\!\!-\!\!\!\shortmid v_5\shortmid\!\!\!-\!\!\!\shortmid v_6.\end{aligned}

Разложение одного и того же цикла C~ v_2\shortmid\!\!\!-\!\!\!\shortmid v_3\shortmid\!\!\!-\!\!\!\shortmid v_5\shortmid\!\!\!-\!\!\!\shortmid v_6\shortmid\!\!\!-\!\!\!\shortmid v_4\shortmid\!\!\!-\!\!\!\shortmid v_2 по двум указанным базисам будет следующим (рис. 5.45):


C=C_\oplus C_2\oplus C_3,\qquad C=D_1\oplus D_4.

Разложение одного и того же цикла графа по двум указанным базисам



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


Таким образом, анализ циклов может быть использован для доказательства неизоморфности графов.


Пример 5.17. Рассмотрим графы, представленные на рис. 5.46. Заметим, что у этих графов одинаковое количество вершин и ребер, а также одинаковые степени всех вершин. Поэтому гипотеза об их изоморфности представляется правдоподобной. Однако для доказательства изоморфизма графов необходимо явно указать биекцию множества вершин одного графа на множество вершин второго, при которой сохраняется отношение смежности. Поиск такой биекции весьма трудоемок, так как может потребовать полного перебора всех возможных вариантов. Для доказательства неизоморфности достаточно показать принципиальную невозможность установления требуемой биекции. Используем для этого анализ циклов.


Графы с одинаковым количеством вершин и ребер, а также одинаковыми степенями всех вершин

Проведем поиск в глубину в каждом из графов. Если количество обратных ребер окажется различным, неизоморфность графов будет доказана. Для определенности в каждом из графов начнем поиск с вершины v_1 и будем считать, что списки смежности каждой вершины упорядочены по возрастанию номеров вершин. На рис. 5.46 в графах выделены древесные ребра, полученные при поиске в глубину. В каждом из графов оказалось по шесть обратных ребер, и, следовательно, вывод о неизоморфности сделать нельзя.


Различие можно увидеть в "тонких" структурах циклов. Заметим, что в графе G_1 имеются четыре цикла длины 3:


\begin{array}{ll}v_1 \shortmid\!\!\!-\!\!\!\shortmid v_2\shortmid\!\!\!-\!\!\!\shortmid v_4\shortmid\!\!\!-\!\!\!\shortmid v_1,&\qquad v_1\shortmid\!\!\!-\!\!\!\shortmid v_3\shortmid\!\!\!-\!\!\!\shortmid v_4\shortmid\!\!\!-\!\!\!\shortmid v_1,\\[2pt] v_7 \shortmid\!\!\!-\!\!\!\shortmid v_8\shortmid\!\!\!-\!\!\!\shortmid v_9\shortmid\!\!\!-\!\!\!\shortmid v_7,&\qquad v_8\shortmid\!\!\!-\!\!\!\shortmid v_9\shortmid\!\!\!-\!\!\!\shortmid v_{10}\shortmid\!\!\!-\!\!\!\shortmid v_8. \end{array}

В графе G_2 таких циклов также четыре:


\begin{array}{ll}v_1 \shortmid\!\!\!-\!\!\!\shortmid v_2\shortmid\!\!\!-\!\!\!\shortmid v_4\shortmid\!\!\!-\!\!\!\shortmid v_1,&\qquad v_1\shortmid\!\!\!-\!\!\!\shortmid v_2\shortmid\!\!\!-\!\!\!\shortmid v_3\shortmid\!\!\!-\!\!\!\shortmid v_1,\\[2pt] v_7 \shortmid\!\!\!-\!\!\!\shortmid v_8\shortmid\!\!\!-\!\!\!\shortmid v_9\shortmid\!\!\!-\!\!\!\shortmid v_7,&\qquad v_8\shortmid\!\!\!-\!\!\!\shortmid v_9\shortmid\!\!\!-\!\!\!\shortmid v_{10}\shortmid\!\!\!-\!\!\!\shortmid v_8. \end{array}

Однако количество циклов длины 4 в графах различно. В графе G_1 таких циклов шесть:


\begin{array}{ll}v_1 \shortmid\!\!\!-\!\!\!\shortmid v_2\shortmid\!\!\!-\!\!\!\shortmid v_4\shortmid\!\!\!-\!\!\!\shortmid v_3\shortmid\!\!\!-\!\!\!\shortmid v_1,&\qquad v_1\shortmid\!\!\!-\!\!\!\shortmid v_2\shortmid\!\!\!-\!\!\!\shortmid v_5\shortmid\!\!\!-\!\!\!\shortmid v_3\shortmid\!\!\!-\!\!\!\shortmid v_1,\\[2pt] v_2 \shortmid\!\!\!-\!\!\!\shortmid v_4\shortmid\!\!\!-\!\!\!\shortmid v_3\shortmid\!\!\!-\!\!\!\shortmid v_5\shortmid\!\!\!-\!\!\!\shortmid v_2,&\qquad v_9\shortmid\!\!\!-\!\!\!\shortmid v_7\shortmid\!\!\!-\!\!\!\shortmid v_8\shortmid\!\!\!-\!\!\!\shortmid v_{10}\shortmid\!\!\!-\!\!\!\shortmid v_9,\\[2pt] v_9 \shortmid\!\!\!-\!\!\!\shortmid v_7\shortmid\!\!\!-\!\!\!\shortmid v_6\shortmid\!\!\!-\!\!\!\shortmid v_{10}\shortmid\!\!\!-\!\!\!\shortmid v_9,&\qquad v_7\shortmid\!\!\!-\!\!\!\shortmid v_8\shortmid\!\!\!-\!\!\!\shortmid v_{10}\shortmid\!\!\!-\!\!\!\shortmid v_6\shortmid\!\!\!-\!\!\!\shortmid v_7.\end{array}

а в графе G_2 — всего два: v_1\shortmid\!\!\!-\!\!\!\shortmid v_3\shortmid\!\!\!-\!\!\!\shortmid v_2\shortmid\!\!\!-\!\!\!\shortmid v_4\shortmid\!\!\!-\!\!\!\shortmid v_1,~ v_8\shortmid\!\!\!-\!\!\!\shortmid v_{10}\shortmid\!\!\!-\!\!\!\shortmid v_9\shortmid\!\!\!-\!\!\!\shortmid v_7\shortmid\!\!\!-\!\!\!\shortmid v_8. Следовательно, графы неизоморфны.




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


Заметим, что в общем случае все циклы графа можно получить, рассматривая различные линейные комбинации над \mathbb{Z}_2 фундаментальных циклов. При этом следует учесть, что результатом сложения может быть множество ребер, образующих несколько непересекающихся циклов.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved