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

Цикломатическое число. Пусть задан граф без петель. Цикломатическим числом графа называют величину V(G)=r-n+P, где n - число вершин графа, r - число его ребер, P - число компонент связности. Так как n-P=R(G) - ранг графа, то V(G) = r-R(G).

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

Хроматическое число. Пусть задан граф без петель: 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₃, для которой r(x₃)= 1, и пометим ее красным цветом. Вершину x₂ можно раскрасить в синий цвет, а вершины x₁ и x₅ - в красный (они не смежны с x₃). Вершины x₆ и x₈ можно раскрасить в синий цвет.

Оставшиеся вершины x₄ и x₇ раскрасим в зеленый цвет. Всего использовано 3 цвета. Значит К(G) =3.

 

Рис. 16. Определение хроматического числа графа

Плоские графы

 

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

Максимальное число некратных ребер у плоского графа r_max =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с.;ил.