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

Рассмотрим некоторые характеристические числа графа, не зависящие от изоморфных преобразований. Такие числа называют инвариантами графа, т.е. у изоморфных графов они равны.

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

Пусть связный граф G(X, U) имеет n=|X| вершин и r=|U|ребер. Тогда, дерево, построенное на этом графе, имеет |W| = n-1 ребро. По определению цикломатическое число

u (G) = r - (n -1) = r – n +1.

Для несвязного графа с p компонентами связности, цикломатическое число

u (G) = r – n + p.

Цикломатическое число всегда неотрицательно.

Основное свойство цикломатического числа формулируется в виде теоремы:

Цикломатическое число графа равно максимальному числу независимых циклов.

Знание цикломатического числа оказывается полезным при анализе топологии электронных схем, а также для решения целого класса задач конструкторского проектирования ЭВМ.

Хроматическое число.Пусть, задан граф G(X,U) без петель. Разобьем множество его вершин на k непересекающихся подмножеств X₁, X₂, ..., X_k,

Æ] так, чтобы любые две смежные вершины x_i и x_jÎX принадлежали разным подмножествам, т.е. чтобы ребра графа G(X,U) соединяли вершины из разных подмножеств ("X_sÌX [ГX_sÇX_s=Æ], где ГX_s множество вершин, смежных вершинам множества X_s).

Задача раскраски вершин графа формулируется следующим образом. Необходимо раскрасить вершины графа таким образом, чтобы смежные вершины были окрашены в разные цвета. Минимальное число красок, в которые можно раскрасить граф называется хроматическим числом графа и обозначается c(G), а граф G(X, U) называют c-хроматическим.

Особое значение имеет частный вид c-хроматического графа – бихроматический граф, для которого множество вершин X можно разбить на два непересекающихся подмножества Х₁ и Х₂ так, чтобы ребра соединяли вершины разных подмножеств (Х=Х₁ÈХ₂, Х₁ÇХ₂=Æ, "х_iÎX₁ [Гx_iÇX₁=Æ], "х_jÎX₂ [Гx_jÇX₂=Æ].

Такие графы называют бихроматическими, двудольными графами или графами Кенига и обозначают G(X_1, Х₂, U).

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

Если граф G(X, U) - дерево, т.е. в нем отсутствуют циклы, то он является бихроматическим графом и может быть представлен в виде двудольного графа (рис. 3.16).

Рисунок 3.16. Пример представления дерева в виде двудольного графа

Граф Кенига G(X_1, Х₂, U) называют полным, если каждая вершина х_iÎX₁ смежна с каждой вершиной х_jÎX₂ и наоборот. Полный двудольный граф обозначают K_nm, где n=|X₁| и m=|X₂|. Полный бихроматический граф K₃₃ приведен на рис. 3.17.

х2

х3

х1

х4

х5

х6

Х1

Х2

Рис. 3.17. Полный бихроматический граф K₃₃

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

Число планарности.Граф G(X, U) называют плоским тогда и только тогда, когда он геометрически реализованна плоскости так, что все его ребра пересекаются только в вершинах Х графа. Граф G(X,U) называют планарным, если он может быть геометрически реализован на плоскости без пересечения ребер. Т.е., плоскостность это свойство его геометрической реализации на плоскости, а планарность – свойство графа быть реализованным на плоскости. На рис. 3.18 показаны полный планарный граф К₄ и его плоская реализация.

х2

х1

х4

х3

х2

х1

х4

х3

а

бб

Рисунок 3.18. Полный планарный граф К₄ (а) и его плоская реализация (б)

На рис. 3.19. приведены непланарные графы Понтрягина-Куратовского (полный граф К₅ (а) и полный двудольный граф К₃₃ (б)).

а б

Рисунок 3.19. Непланарные графы К₅ (а) и К₃₃ (б)

Граф К₅ – непланарный граф с минимальным числом вершин, а граф К₃₃ – непланарный граф с минимальным числом ребер.

Минимальное число ребер, которое нужно удалить из графа, чтобы он стал планарным, называется числом планарности и обозначается Q(G). Для полного графа К_n с n ≥4 Q(G) = (n - 3)(n - 4)/2.

Число планарности графа К₄ равно0, графа К₅ Q(G) = (5 - 3)(5 - 4)/2=1 (рис. 3.20).

Рисунок 3.20. Ребро, удаление которого делает граф К₅ планарным

Минимальное число плоских суграфов, на которые разбивается граф G(X,U) называется толщиной графа t(G).

Число внутренней устойчивости. Множество вершин Х_s графа G(X,U) называется внутренне устойчивым (независимым), если никакие две вершины из этого множества не смежны, X_sÌX [ГX_sÇX_s=Æ]. Внутренне устойчивое множество называется максимальным, если оно не является собственным подмножеством некоторого другого независимого множества. Максимальное по мощности независимое множество называется наибольшим. Число вершин в наибольшем независимом множестве графа G(X,U) называется числом внутренней устойчивости этого графа и обозначается a(G), a(G)=max|X_s|.

Для графа G(X,U), изображенного на рис. 3.21, множества вершин {x₃, x₆}, {x₄, x₆}, {x₁, x₃, x₇}, {x₁, x₄, x₅} являются максимальными, но не наибольшими. Множество {x₂, x₅, x₇, x₈} является наибольшим, a(G)=4.

х7

х1

х4

х3

х6

х5

х8

х2

Рисунок 3.21. Граф G(X,U)

Заметим, что при раскраске графа, множество вершин, окрашенных в один цвет – внутренне устойчивое.

Число внешней устойчивости.Множество вершин Х_s графа G (X,U) называется внешне устойчивым (доминирующим), если каждая вершина из X\X_s смежна с некоторой вершиной из X_s. Иначе говоря, каждая вершина графа x_jÎX_s или x_jÎГX_s, т.е.находится на расстоянии не более 1 от внешне устойчивого множества, ГX_sÈX_s=Х.

Внешне устойчивое множество X_s называется минимальным, если при удалении из него любой вершины получается множество, не являющееся внешне устойчивым.

Внешне устойчивое множество, состоящее из минимального числа вершин, называется наименьшим.

Число вершин в наименьшем независимом множестве графа G (X,U) называется числом внешней устойчивости этого графа и обозначается b(G), b(G) = min|X_s|.

Для графа G (X,U), изображенного на рис. 3.21, множества вершин {x₁, x₃, x₇}, {x₁, x₄, x₅, x₇} являются минимальными, но не наименьшими. Множества {x₃, x₆} и {x₄, x₆} является наименьшими, b(G)=2.

Подмножество вершин графа, являющееся как внутренне устойчивым, так и внешне устойчивым, называется ядром.