Определения, формы представления графов. Матричное представление графов. Матрица инциденций неориентированного графа, страница 6

При рассмотрении связного неориентированого графа G(Х, А) без петель с n вершинами и m ребрами величину n(G)=m-n+1 называют цикломатическим числом графа [1,2,4].  Принимая во внимание, что дерево с n вершинами имеет n-1 ребро, можно сказать, что цикломатическое число равно числу ребер, которые необходимо удалить из данного графа, чтобы получить дерево.

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

n(G) = m – n + р.

Упражнение

Граф G(Х, А) задан матрицей смежности А₂   из упражнения  5.1.

а) Построить его геометрическое изображение;

б) Определить цикломатическое число;

в) Указать независимые циклы.

7.1. Хроматическое число

Неориентированный граф  G(Х, А) без петель называется r–хроматическим, если его вершины могу быть раскрашены в r цветов (красок) так, что не найдется двух смежных вершин одного цвета. Наименьшее число r, в которое таким образом  могут быть раскрашены вершины графа, называется хроматическим числом графа G [1,2,4]. Обозначим его К(G).

В отличие от цикломатического числа определение хроматического числа осуществляется с помощью сравнительно сложных алгоритмов, поэтому дадим здесь лишь оценку хроматического числа через число вершин n cвязного графа G и через степени его вершин d_i(х):

1 £ К(G) £ n;

k(G) £ d_max (х) = max d(х_i);

х_i Î X.

Например, для графа на рис. 7.1 длина цикла (x_1, х₆, х₂, х₅, х₁) равна четырем, длина цикла (х₂, х_5, х₄, х₉, х₈, х₆, х₂) – шести.

Если K(G)=2, то граф G называется бихроматическим или двудольным, т.к. множество вершин Х в нем можно разбить на два непересекающихся подмножества Х₁ и Х₂, в каждом из которых все вершины несмежны и окрашены в один цвет. Пример двудольного графа приведен на рис. 7.1. Необходимое и достаточное условие бихроматичности графа состоит в том, чтобы все простые циклы в нем имели четную длину[1].

Заметим, что дерево всегда является двудольным графом.

На практике для связных графов оценить величину К(G)  можно с помощью различных приближенных алгоритмов. Например, с помощью следующей процедуры [2]: выбираем вершину с максимальной степенью (если таких несколько, то любую из них) и раскрашиваем ее в цвет 1. Затем, просматривая все неокрашенные вершины, в цвет 1 раскрашиваем всякую величину, не смежную с уже окрашенными в этот цвет вершинами.

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

Аналогично действуем с цветами 3, 4 и т.д., пока не будут окрашены все вершины.

Число использованных цветов будет приближенным значением хроматического числа графа. В качестве примера найдем оценку К(G) для графа на рис.7.2.

В цвет 1 окрашиваем вершины: х₈, х₁, х₅;

В цвет 2 : х₁₀,  х₂,  х₄;

В цвет 3: х₇, х₉, х₃, х₆.

Таким образом, оценка хроматического числа для графа на рис. 7.2 равна 3.

7.3.    Число внутренней устойчивости (независимости)

Если в неориентированном графе G (Х, А) имеется некоторое подмножество S_i Ì X несмежных между собой вершин, т.е. (" х_i Î S_i) [Г(х_i) n S_i = Æ], то такое подмножество называется внутренне устойчивым или независимым множеством .[2,4]

Например, для графа на рис. 7.2 множества вершин s₁={x₂, x₄}, S₂{х₁, х₅, х₈}, S₃{х₇, х₉, х₃, х₆} - внутренне устойчивые или независимые множества.

Независимое множество называется непополнимым или максимальным, если его нельзя дополнить ни одной вершиной х_i Î Х без потери свойств независимости. Так, множества S₁ и S₂ являются непополнимыми, а множество S₁ таковым не является, т.к. при добавлении к нему вершины х₈ свойство независимости вершин сохраняется.

Если имеется семейство S всех независимых множеств, то подмножество с максимальной мощностью называется наибольшим независимым (внутренне устойчивым) множеством, а величина равная мощности этого множества -  числом независимости или числом внутренней устойчивости a(G):

a(G) = max½Si½,  Si Î S.

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