|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Характеристические числа графов
Рассмотрим некоторые характеристические числа графа, не зависящие от изоморфных преобразований. Такие числа называют инвариантами графа, т.е. у изоморфных графов они равны. Цикломатическое число. Цикломатическое число графа указывает то число ребер, которое нужно удалить из данного графа, чтобы получить дерево (для связного графа) или лес (для несвязного графа), т.е. добиться отсутствия у графа циклов. Пусть связный граф 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 непересекающихся подмножеств X1, X2, ..., Xk, Задача раскраски вершин графа формулируется следующим образом. Необходимо раскрасить вершины графа таким образом, чтобы смежные вершины были окрашены в разные цвета. Минимальное число красок, в которые можно раскрасить граф называется хроматическим числом графа и обозначается c(G), а граф G(X, U) называют c-хроматическим. Особое значение имеет частный вид c-хроматического графа – бихроматический граф, для которого множество вершин X можно разбить на два непересекающихся подмножества Х1 и Х2 так, чтобы ребра соединяли вершины разных подмножеств (Х=Х1È Х2, Х1Ç Х2=Æ, " хiÎ X1 [ГxiÇ X1=Æ ], " хjÎ X2 [ГxjÇ X2=Æ ]. Такие графы называют бихроматическими, двудольными графами или графами Кенига и обозначают G(X1, Х2, U). Критерий бихроматичности произвольного графа формулируется теоремой Кенига, согласно которой граф G(X, U) является бихроматическим тогда и только тогда, когда он не содержит циклов нечетной длины. Если граф G(X, U) - дерево, т.е. в нем отсутствуют циклы, то он является бихроматическим графом и может быть представлен в виде двудольного графа (рис. 3.16).
Рисунок 3.16. Пример представления дерева в виде двудольного графа Граф Кенига G(X1, Х2, U) называют полным, если каждая вершина хiÎ X1 смежна с каждой вершиной хjÎ X2 и наоборот. Полный двудольный граф обозначают Knm, где n=|X1| и m=|X2|. Полный бихроматический граф K33 приведен на рис. 3.17.
Рис. 3.17. Полный бихроматический граф K33 В отличие от цикломатического числа определение хроматического числа осуществляется с помощью сравнительно сложных алгоритмов, в основу большинства которых положены методы целочисленного линейного программирования. Число планарности. Граф G(X, U) называют плоским тогда и только тогда, когда он геометрически реализован на плоскости так, что все его ребра пересекаются только в вершинах Х графа. Граф G(X, U) называют планарным, если он может быть геометрически реализован на плоскости без пересечения ребер. Т.е., плоскостность это свойство его геометрической реализации на плоскости, а планарность – свойство графа быть реализованным на плоскости. На рис. 3.18 показаны полный планарный граф К4 и его плоская реализация.
Рисунок 3.18. Полный планарный граф К4 (а) и его плоская реализация (б) На рис. 3.19. приведены непланарные графы Понтрягина-Куратовского (полный граф К5 (а) и полный двудольный граф К33 (б)).
а б Рисунок 3.19. Непланарные графы К5 (а) и К33 (б) Граф К5 – непланарный граф с минимальным числом вершин, а граф К33 – непланарный граф с минимальным числом ребер. Минимальное число ребер, которое нужно удалить из графа, чтобы он стал планарным, называется числом планарности и обозначается Q(G). Для полного графа Кn с n ≥ 4 Q(G) = (n - 3)(n - 4)/2. Число планарности графа К4 равно0, графа К5 Q(G) = (5 - 3)(5 - 4)/2=1 (рис. 3.20).
Рисунок 3.20. Ребро, удаление которого делает граф К5 планарным Минимальное число плоских суграфов, на которые разбивается граф G(X, U) называется толщиной графа t(G). Число внутренней устойчивости. Множество вершин Хs графа G(X, U) называется внутренне устойчивым (независимым), если никакие две вершины из этого множества не смежны, XsÌ X [ГXsÇ Xs=Æ ]. Внутренне устойчивое множество называется максимальным, если оно не является собственным подмножеством некоторого другого независимого множества. Максимальное по мощности независимое множество называется наибольшим. Число вершин в наибольшем независимом множестве графа G(X, U) называется числом внутренней устойчивости этого графа и обозначается a(G), a(G)=max|Xs|. Для графа G(X, U), изображенного на рис. 3.21, множества вершин {x3, x6}, {x4, x6}, {x1, x3, x7}, {x1, x4, x5} являются максимальными, но не наибольшими. Множество {x2, x5, x7, x8} является наибольшим, a(G)=4.
Рисунок 3.21. Граф G(X, U) Заметим, что при раскраске графа, множество вершин, окрашенных в один цвет – внутренне устойчивое. Число внешней устойчивости. Множество вершин Хs графа G (X, U) называется внешне устойчивым (доминирующим), если каждая вершина из X\Xs смежна с некоторой вершиной из Xs. Иначе говоря, каждая вершина графа xjÎ Xs или xjÎ ГXs, т.е.находится на расстоянии не более 1 от внешне устойчивого множества, ГXsÈ Xs=Х. Внешне устойчивое множество Xs называется минимальным, если при удалении из него любой вершины получается множество, не являющееся внешне устойчивым. Внешне устойчивое множество, состоящее из минимального числа вершин, называется наименьшим. Число вершин в наименьшем независимом множестве графа G (X, U) называется числом внешней устойчивости этого графа и обозначается b(G), b(G) = min|Xs|. Для графа G (X, U), изображенного на рис. 3.21, множества вершин {x1, x3, x7}, {x1, x4, x5, x7} являются минимальными, но не наименьшими. Множества {x3, x6} и {x4, x6} является наименьшими, b(G)=2. Подмножество вершин графа, являющееся как внутренне устойчивым, так и внешне устойчивым, называется ядром . Плотность графа. Максимальный полный подграф графа G (X, U) называется кликой графа G; другими словами, клика графа G есть подмножество его вершин, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством. Число вершин клики графа называется плотностью графа и обозначается f(G). Для графа G(X, U), изображенного на рис. 3.22 клику образуют вершины (2, 3, 6, 7). Плотность этого графа f(G)=4.
Рисунок 3.22. Граф G(X, U) с кликой (2, 3, 6, 7) Число Хадвигера. Операцией сжатия графа (стягивание графа) называется замена двух смежных вершин хi и хj одной хs с удалением ребра uij. Числом Хадвигера h(G) графа G(X, U) называется такое наибольшее число h, что граф G стягиваем к полному графу Kh. На рис. 3.23, а изображен граф Петерсена. В результате стягивания графа (замена вершин x1 и x6 на y1; x2 и x7 на y2 и т.д.) получим полный граф К5 (рис.3.23, б). Число Хадвигера графа Петерсена h(G)=5.
Рисунок 3.23. Граф Петерсена (а) и полный граф К5 (б) Популярное:
|
Последнее изменение этой страницы: 2017-03-10; Просмотров: 810; Нарушение авторского права страницы
Æ ] так, чтобы любые две смежные вершины xi и xjÎ X принадлежали разным подмножествам, т.е. чтобы ребра графа G(X, U) соединяли вершины из разных подмножеств (" XsÌ X [ГXsÇ Xs=Æ ], где ГXs множество вершин, смежных вершинам множества Xs).
