Циклы и разрезы графа
Характеристические числа графов
Решение многих технических задач методами теории графов сводится к определению тех или иных характеристик графов, поэтому полезно знакомство со следующими характеристиками.
Цикломатическое число. Пусть G(X) – неориентированный граф, имеющий n вершин, m ребер и k компонент связности. Цикломатическим числом графа G называется число µ(G) = m - n + k.
Это число имеет интересный физический смысл: оно равно наибольшему числу базисных (независимых) циклов в графе. При расчете электрических цепей цикломатическим числом можно пользоваться для определения числа независимых контуров.
Хроматическое число. Пусть р – натуральное число. Граф G(X) называется р-хроматическим, если его вершины можно раскрасить различными цветами так, чтобы никакие две смежные вершины не были раскрашены одинаково. Наименьшее число р, при котором граф является р‑хроматическим, называется хроматическим числом графа и обозначается γ(G).
Если γ(G) = 2, то граф называется бихроматическим. Необходимым и достаточным условием того, чтобы граф был бихроматическим, является отсутствие в нем циклов нечетной длины.
Хроматическое число играет важную роль при решении задачи наиболее экономичного использования ячеек памяти при программировании. Однако его определение, за исключением γ(G) = 2, представляет собой довольно трудную задачу, требующую применения ЭВМ.
Множество внутренней устойчивости. Множество S Ì X графа G(X) называется внутренне устойчивым, если никакие две вершины из S не являются смежными, то есть для любого х Î S имеет место:
G(x) Ç S = Æ.
Множество внутренней устойчивости, содержащее наибольшее число элементов, называется наибольшим внутренне устойчивым множеством, а число элементов этого множества называется числом внутренней устойчивости графа G. Наибольшее внутренне устойчивое множество играет важную роль в теории связи.
Множество внешней устойчивости. Множество Т Ì X графа G(X) называется внешне устойчивым, если любая вершина, не принадлежащая Т, соединена дугами с вершинами из Т, то есть для любого х Ï Т имеет место: G(x) Ç Т ¹ Æ.
Множество внешней устойчивости, содержащее наименьшее число элементов, называется наименьшим внешне устойчивым множеством, а число элементов этого множества называется числом внешней устойчивости графа G(X).
Остовом T графа G называется называется подграф графа в виде дерева, содержащий все его вершины. Остов определяет каркас графа. Кодеревом T* остова Т называется подграф графа G, содержащий все вершины и только те ребра, которые не входят в остов Т. Ребра остова называют ветвями, а ребра кодерева - хордами.
Из определений остова и кодерева следует:
1. Объединение остова T и кодерева T* есть граф G:
Т ÈT* = G.
2. Кодерево есть дополнение остова T до графа G:
T* = G \ Т =`Т.
Рассмотрим пример графа, изображенного на рис. 3.30.
Рис. 3.30. Граф
Выберем остов графа в виде связного дерева (рис. 3.31).
Рис. 3.31. Остов графа
Кодерево для данного остова имеет вид несвязного графа (рис. 3.32), но он может быть и связным.
Рис. 3.32. Кодерево графа