Цикломатическая матрица и матрица разрезов

Свойства базисных циклов и разрежающих множеств

Базисные циклы и разрезающие множества

Пусть T- остов графа G, а g_i^* – хорда кодерева T*. Так как Т – ацикличный граф, то граф Т È g_i^* содержит точно один цикл C_i. Цикл C_i состоит из хорды g_i^* и тех ветвей остова Т, которые образуют единственную простую цепь между концевыми вершинами хорды g_i^*. Цикл C_i, возникающий в графе Т È g_i^*, называется базисным циклом относительно хорды g_i^* остова Т. Множество всех таких циклов, число которых равно цикломатическому числу µ(G) графа G, называют базисным множеством циклов графа G относительно остова Т.

Пусть G(X) – связный граф и X = {X₁, X₂} – некоторое раз­биение множества его вершин: X = X₁ È X₂ и X₁ÇX₂ =Æ. Множество ребер графа G, одна концевая вершина каждого из которых принадлежит X₁, а другая – X₂, называется разрежающим множеством или разрезом графа. Удаление разрежающего множества – разрез графа, разде­ляет граф на две компоненты и делает его несвязным.

Пусть T – остов связного графа G, а g_j – ветвь этого остова. Удаление ветви из остова разбивает остов на 2 компоненты T₁ и T₂. Пусть X₁ и X₂ множества вершин, соответственно, компонент T₁ и T₂, а G₁ и G₂ – подграфы графа G, порожденные множествами вершин X₁ и X₂. Очевидно, что T₁ – остов подграфа G₁, а T₂ – остов подграфа G₂. Следовательно, подграфы G₁ и G₂ связны, а разрез, разделяющий X₁ и X₂, является разрежающим множеством графа G.

Разрежающее множество S_j, составленное из ребер, связывающих вершины компонент T₁ и T₂ остова называется базисным разрежающим множеством графа G. При этом, компоненты T₁ и T₂ остова образованы удалением ветви g_j остова T.

1.Базисный цикл C_i относительно хорды g_i^* кодерева T* связного графа G включает точно те ветви остова T, которым соответствуют базисные разрежающие множества, включающие эту хорду.

2. Базисное разрежающее множество S_j относительно ветви g_j остова T связного графа G включает точно те хорды кодерева T*, которым соответствуют базисные циклы, включающие эту ветвь.

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

1. Количество базисных циклов графа G равно цикломатическому числу графа - числу ребер в кодереве.

2. Количество базисных разрежающих множеств равно величине ранга графа - числу ребер в остове.

Построим цикломатическую матрицу C = (c_ik) и матри­цу разрезов S = (s_jk) графа, элементы которых:

1, если g_k Î C_i ; 1, если g_k Î S_j ;

c_ik = s_jk =

0, если g_k ÏC_i . 0, если g_k ÏS_j.

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

Суперпозиция осуществляется с помощью операции сложения по модулю 2 двоичной алгебры, обозначаемой символом Å. Вектор-строка с_i = (c_i1, c_i2, …, c_im), описы­вающая цикл C_i графа, вычисляется как покомпо­нентная сумма по модулю 2 векторов, соответствующих базисным циклам. Аналогично, вектор-строка s_j = (s_j1, s_j2, …, s_jm) описывает разрез S_j графа и вычисляется как сумма по модулю 2 векторов, соответствующих базисным разрезающим множествам.

Рассмотрим пример построения этих матриц для графа, приведенного на рис. 3.30. Сначала вычислим ранг и цикломатическое число этого. Ранг графа – число ребер в остове (рис. 3.31) – равен 4. Цикломатическое число графа – число ребер в кодереве (рис. 3.32) – равно 3. Следовательно, имеем 3 базисных цикла и 4 базисных разрезающих множества. Далее запишем эти базисные циклы и разрезающие множества.

Базисные циклы:

Базисные разрезающие множества: