17.1. Цикломатическое и хроматическое числа графа

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

Наименьшее число ребер, которое необходимо удалить из графа G, чтобы он стал ациклическим (деревом), называется цикломатическим числом графа. Для графа G = (X, U), |X| = n, |U| = m цикломатическое число

(G) = m – n + k, (17.1)

где k — число компонентов связности графа, (k = 1, 2, …). Величину (G) = n – k называют коцикломатическим числом. Тогда (G) = m – (G).

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

(G) = m – n + 1. (17.2)

Например, для графа G (рис. 17.38) (G) = 9 – 6 + 1 = 4, то есть после удаления четырех ребер он становится деревом. В примере это могут быть ребра (x₁, x₃), (x₁, x₅), (x₄, x₅), (x₄, x₆). Тогда получаем дерево T, выделенное жирным шрифтом.

Заметим, что цикломатическое число графа не зависит от ориентации его ребер и формула его определения справедлива для мультиграфов. Из определения (G) следует, что оно может быть только положительным или равным нулю. Граф (мультиграф) не имеет циклов тогда и только тогда, когда (G) = 0. Очевидно, что граф (мультиграф) имеет единственный цикл тогда и только тогда, когда (G) = 1.

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

Матрица R_c = ||r_c(i, j)||_(G)×m, состоящая из (G) строк и m столбцов, называется матрицей фундаментальных циклов, если

Для графа G (рис. 17.38) матрица R_c запишется следующим образом:

		u1	u2	u3	u4	u5	u6	u7	u8	u9
Rc =	c1	1	0	1	0	1	0	0	0	0	.
	c2	1	1	0	1	0	1	0	0	0
	c3	0	0	0	1	1	0	0	1	1
	c4	0	0	0	0	0	0	1	1	1

u₁ = (x₁, x₂), u₂ = (x₁, x₃), u₃ = (x₁, x₅), u₄ = (x₂, x₄), u₅ = (x₂, x₅), u₆ = (x₃, x₄), u₇ = (x₄, x₅), u₈ = (x₄, x₆), u₉ = (x₅, x₆).

Раскраской вершин графа называется разбиение множества вершин X на l непересекающихся классов (подмножеств):

(17.3)

таких, что внутри каждого подмножества X_i не должно содержаться смежных вершин. Если каждому подмножеству X_i поставить в соответствие определенный цвет, то вершины этого подмножества можно окрасить в один цвет, вершины другого подмножества X_j – в другой цвет, и т.д. до раскраски всех подмножеств. В этом случае граф называется l–аскрашиваемым. Наименьшее число подмножеств, на которое разбивается граф при раскраске, называется хроматическим числом (G).

Очевидно, что полный граф K_n можно раскрасить только n цветами, следовательно, (K_n) = n. Для связного графа G = (X, U) с (n - 1)  m  n(n – 1)/2 верхняя оценка хроматического числа

(17.4)

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

(G)  1+max (x_i), x_i  X, i  I = {1, 2, …, n}. (17.5)

Если известно число вершин в наибольшем полном подграфе K_i графа G, то

(G) = n / n_i,

где n_i – число вершин в подграфе K_i. Известны еще такие оценки:

, (17.6)

где – хроматическое число графа .

Хроматическое число обычно определяют аналитически с помощью методов линейного программирования. Рассмотрим один из возможных методов определения (G), равного q.

Пусть справедливы следующие утверждения:

и

Тогда можно составить следующую систему линейных соотношений:

j = 1, 2, …, n,

l = 1, 2, …, m, (17.7)

p = 1, 2, …, q.

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

Каждому способу раскраски вершин графа q цветами (при обязательном условии разноцветности смежных вершин) соответствует система целых чисел (j, p), удовлетворяющая условиям (17.3), и, наоборот, каждому целочисленному решению системы (17.3) соответствует один из способов раскраски. Наименьшее q, для которого система (17.7) имеет целочисленное решение, будет искомым хроматическим числом графа.

Опишем последовательный метод раскраски графа G = (X, U). Сначала составляется упорядоченный в порядке не возрастания степеней вершин список. Первая вершина окрашивается в цвет 1 и удаляется из списка. Просматривая список, в цвет 1 раскрашиваются и удаляются из него все вершины, не смежные с первой выбранной и между собой. Далее снова выбирается первая вершина из списка, она окрашивается в цвет 2 и удаляется. Процесс продолжается, пока не будут окрашены все вершины.

Например, пусть задан граф G, показанный на рис. 17.1.

Рис. 17.1. Граф G

Построим список смежности

xi	x3	x2	x4	x5	x7	x1	x6
(xi)	5	4	3	3	3	2	2

Вершины x₃, x₄ окрашиваем в цвет 1 и удаляем из списка. Получаем новый список

xi	x2	x5	x7	x1	x6
(xi)	4	3	3	2	2

Вершины x₂, x₆ окрашиваем в цвет 2 и удаляем из списка:

xi	x5	x7	x1
(xi)	3	3	2

Вершины x₅, x₇, x₁ окрашиваем в цвет 3. На этом процесс окончен, так как раскрашены все вершины графа.

Отметим, что такого типа последовательные методы могут давать плохие результаты раскраски при быстром получении результата. Существует много модификаций последовательных алгоритмов, связанных с переупорядочиванием списков после удаления вершин, анализа вершин с одинаковой локальной степенью и выбора из них вершин, через которые проходит большее число маршрутов, и т.п. Временная сложность таких алгоритмов составляет величину O(n) – O(n²).

Важное практическое применение имеет частный вид n-раскрашиваемых графов – двудольные (бихроматические) графы. Обозначается двудольный граф G(n₁, n₂) = (X₁, X₂, U). Причем X₁  X₂ = X, X₁  X₂ = , а ребра соединяют только подмножества X₁ и X₂ между собой. На рис. 17.2 показан пример двудольного графа G = (X₁, X₂, U), |X₁| = 3 = n₁, |X₂| = 2 = n₂, X₁ = {x₁, x₂, x₃}, X₂ = {x₄, x₅}.

Рис. 17.2. Двудольный граф

Граф K(n₁, n₂) называется полным двудольным, если любая вершина x_i  X₁ смежна с каждой вершиной x_j  X₂ и наоборот (i = 1, 2, …, n₁; j = n₁ + 1, n₁ + 2, …, n₁ + n₂).

Например, при добавлении к графу G(n₁, n₂) (рис. 3.2) ребра (x₃, x₄) он становится полным двудольным графом. Очевидно, что в графе G = (X₁, X₂, U) подмножество X₁ можно раскрасить одним цветом, а подмножество X₂ – другим. Число ребер m графа K(n₁, n₂) определяется выражением m = n₁ × n₂.

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

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