Цикломатическое число соответствует тому наименьшему количеству ребер в
графе, которые нужно исключить из графа, чтобы получить дерево.
Хроматическое число. Пусть задан граф без петель: G(X,Г). Разобьем множество
его вершин на К непересекающихся подмножеств так, чтобы любые две смежные
вершины x
i
,x
j
X принадлежали разным подмножествам ,т.е. чтобы ребра графа
G(X,Г) соединяли вершины из разных подмножеств: x
i
X [x
i
Xs Гx
i
Xs]. Отметим
все вершины X индексами 1,2,...,K (т.е. раскрасим вершины K цветами), причем
вершины внутри каждого подмножества X помечают одним индексом (раскрашивают
одним цветом). Подмножества формируют таким образом, чтобы концы любого ребра
графа имели различные индексы. Наименьшее возможное число подмножеств,
получаемое в результате такого разбиения вершин графа G(X,Г), называют
хроматическим числом графа, К(G), а граф G(X,Г) называют К-хроматическим.
Особое значение имеет бихроматический граф или двудольный граф, для которого
К(G)=2. Согласно теореме Кенига обыкновенный граф является бихроматическим
тогда и только тогда, когда он не содержит циклов нечетной длины. Если граф - дерево,
т.е. в нем нет циклов, то он является бихроматическим графом.
Определение хроматического числа осуществляется с помощью сравнительно
сложных алгоритмов. Для простых связных графов оценить число К(G) можно
следующим образом. Сначала выбираем вершину с минимальной степенью и пометим
(раскрасим) ее, затем произведем раскраску вершин, смежных с данной и т.д.
Например, для графа, изображенного на рис.16, выбираем вершину x
3
, для которой
(x
3
)=1, и пометим ее красным цветом. Вершину x
2
можно раскрасить в синий цвет, а
вершины x
1
и x
5
- в красный (они не смежны с x
3
). Вершины x
6
и x
8
можно раскрасить в
синий цвет.
Оставшиеся вершины x
4
и x
7
раскрасим в зеленый цвет. Всего использовано 3
цвета. Значит К(G)=3.
Рис. 16. Определение хроматического числа графа
2.5. Плоские графы
Граф называется плоским (планарным), если он может быть изображен на
плоскости так, что все его ребра пересекаются только в вершинах графа. Планарность
является внутренним свойством графа и не обязательно проявляется при произвольном
его изображении.
Максимальное число некратных ребер у плоского графа r
max
=3(n-2). Если число
таких некратных ребер графа rn+2, то такой граф заведомо плоский. Таким образом,
можно записать условия для предварительного исследования планарности графа:
r>3(n-2) - граф заведомо не плоский,
rn+2 - граф заведомо плоский.