Материал: Diskretnaya_matematika

3.6.2. Характеристические числа графов

Решение многих технических задач методами теории графов сводится к определению тех или иных характеристик графов, поэто­му полезно знакомство со следующими характеристиками.

Цикломатическое число. Пусть G(X) – неориен­тирован­ный граф, имеющий n вершин, m ребер и k компонент связности. Цикломатическим числом графа G называется число µ(G) = m - n + k.

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

Хроматическое число. Пусть р – натуральное число. Граф G(X) называется р-хроматическим, если его вершины можно рас­красить различными цветами так, чтобы никакие две смежные вер­шины не были раскрашены одинаково. Наименьшее число р, прикотором граф является р‑хроматическим, называется хроматическим числом графа и обозначается γ(G).

Если γ(G) = 2, то граф называется бихроматическим. Необходимым и достаточным условием того, чтобы граф был бихроматическим, является отсутствие в нем циклов нечетной длины.

Хроматическое число играет важную роль при решении задачи наиболее экономичного использования ячеек памяти при програм­мировании. Однако его определение, за исключением γ(G) = 2, пред­ставляет собой довольно трудную задачу, требующую применения ЭВМ.

Множество внутренней устойчивости. Множество S  X графа G(X) называется внутренне устойчивым, если никакие две вершины из S не являются смежными, то есть для любого х  S имеет место:

G(x)  S = .

Множество внутренней устойчивости, содержащее наибольшее число элементов, называется наибольшим внутренне устойчивым множеством, а число элементов этого множества называется чис­лом внутренней устойчивости графа G. Наибольшее внутренне устойчивое множество играет важную роль в теории связи.

Множество внешней устойчивости. Множество Т  X графа G(X) называется внешне устойчивым, если любая вершина, не при­надлежащая Т, соединена дугами с вершинами из Т, то есть для лю­бого х  Т имеет место: G(x)  Т  .

Множество внешней устойчивости, содержащее наименьшее число элементов, называется наименьшимвнешне устойчивым множеством, а число элементов этого множества называетсячис­лом внешней устойчивостиграфаG(X).

3.7. Циклы и разрезы графа

3.7.1. Остов и кодерево

ОстовомT графаGназывается называется подграф графа в виде дерева, содержащий все его вершины. Остов определяет каркас графа.Кодеревом T^* остова Т называется подграф графаG, содержащий все вершины и только те ребра, которые не входят в остов Т. Ребра остова называют ветвями, а ребра кодерева - хордами.

Из определений остова и кодерева следует:

1. Объединение остова T и кодерева T^* есть граф G:

Т T^* = G.

2. Кодерево есть дополнение остова T до графа G:

T^*=G\ Т =Т.

Рассмотрим пример графа, изображенного на рис. 3.30.

Рис. 3.30. Граф

Выберем остов графа в виде связного дерева (рис. 3.31).

Рис. 3.31. Остов графа

Кодерево для данного остова имеет вид несвязного графа (рис. 3.32), но он может быть и связным.

Рис. 3.32. Кодерево графа

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

Пусть 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*, которым соответствуют базисные циклы, включающие эту ветвь.

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

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

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 базисных разрезающих множества. Далее запишем эти базисные циклы и разрезающие множества.

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

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