Цикломатическое число. Пусть задан граф без петель. Цикломатическим числом графа называют величину V(G)=r-n+P, где n - число вершин графа, r - число его ребер, P - число компонент связности. Так как n-P=R(G) - ранг графа, то V(G) = r-R(G).
Цикломатическое число соответствует тому наименьшему количеству ребер в графе, которые нужно исключить из графа, чтобы получить дерево.
Хроматическое число. Пусть задан граф без петель: G(X,Г). Разобьем множество его вершин на К непересекающихся подмножеств так, чтобы любые две смежные вершины xi,xjÎX принадлежали разным подмножествам,т.е. чтобы ребра графа G(X,Г) соединяли вершины из разных подмножеств: "xiÎX [xiÎXs ®ГxiÏXs]. Отметим все вершины X индексами 1,2,..., K (т.е. раскрасим вершины Kцветами), причем вершины внутри каждого подмножества X помечают одним индексом (раскрашивают одним цветом). Подмножества формируют таким образом, чтобы концы любого ребра графа имели различные индексы. Наименьшее возможное число подмножеств, получаемое в результате такого разбиения вершин графа G(X,Г), называют хроматическим числом графа, К(G), а граф G(X,Г) называют К-хроматическим.
Особое значение имеет бихроматический граф или двудольный граф, для которого К(G)= 2. Согласно теореме Кенига обыкновенный граф является бихроматическим тогда и только тогда, когда он не содержит циклов нечетной длины. Если граф - дерево, т.е. в нем нет циклов, то он является бихроматическим графом.
Определение хроматического числа осуществляется с помощью сравнительно сложных алгоритмов. Для простых связных графов оценить число К(G) можно следующим образом. Сначала выбираем вершину с минимальной степенью и пометим (раскрасим) ее, затем произведем раскраску вершин, смежных с данной и т.д. Например, для графа, изображенного на рис.16, выбираем вершину x3, для которой r(x3)= 1, и пометим ее красным цветом. Вершину x2 можно раскрасить в синий цвет, а вершины x1 и x5 - в красный (они не смежны с x3). Вершины x6 и x8 можно раскрасить в синий цвет.
Оставшиеся вершины x4 и x7 раскрасим в зеленый цвет. Всего использовано 3 цвета. Значит К(G) =3.
Рис. 16. Определение хроматического числа графа
Плоские графы
Граф называется плоским (планарным), если он может быть изображен на плоскости так, что все его ребра пересекаются только в вершинах графа. Планарность является внутренним свойством графа и не обязательно проявляется при произвольном его изображении.
Максимальное число некратных ребер у плоского графа rmax =3(n -2). Если число таких некратных ребер графа r £ n +2, то такой граф заведомо плоский. Таким образом, можно записать условия для предварительного исследования планарности графа:
r >3(n -2) - граф заведомо не плоский,
r £ n +2 - граф заведомо плоский.
Если число некратных ребер графа находится в интервале n +2< r £3(n -2), то для выяснения его планарности требуются специальные исследования.
Согласно теореме Понтрягина-Куратовского граф является плоским тогда и только тогда, когда он не содержит подграфа, изоморфного с точностью до вершин степени два одному из графов Понтрягина-Куратовского. Графы Понтрягина-Куратовского первого и второго типов приведены на рис. 17. Эти графы заведомо не плоские и имеют минимум одно пересечение ребер.
Рис. 17. Графы Понтрягина-Куратовского
Литература
1. Деньдобренько В.Н., Малика А.С. Автоматизация конструирования РЭА.-М.: Высшая школа, 1980.-361 с.;ил.
2. Коршунов Ю.А. Математические основы кибернетики: Учеб. пособие для вузов, - М.:Энергоатомиздат,1987. -496 с.;ил.
3. Сигорский В.П. Математический аппарат инженера. - К.: Техника, 1975.- 766с.;ил.
