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

Решение многих технических задач методами теории графов сводится к определению тех или иных характеристик графов, поэто­му полезно знакомство со следующими характеристиками.

Цикломатическое число.Пусть 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).