2.5. Характеристики графов.

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

Цикломатическое число. Пусть G - неориентированный граф, имеющий n вершин, m рёбер и r компонент связности. Цикломатическим числом графа G называют число (G)=m-n+r.

Это число имеет интересный физический смысл. Оно равно наибольшему числу независимых циклов в графе. При расчёте электрических цепей цикломатическим числом можно пользоваться для определения числа независимых контуров.

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

Если (G)=2, то граф называют называют бихроматическим. Необходимым и достаточным условием того, чтобы граф был бихроматическим, является отсутствие в нём циклов нечётной длины. Хроматическое число играет важную при решении задачи наиболее экономического использования ячеек памяти при программировании. Однако его определение, за исключением случая бихроматического графа, представляет собой довольно трудную задачу, требующую нередко применения электронных вычислительных машин.

Пусть G – связный неориентированный граф, V и V – любые две его вершины. Тогда существует связывающая их простая цепь. М (L1,L2,…,Lq). Если количество ребер q этой цепи не минимальное из возможных , то существует цепь M( L1,L2,…,Lq), связывающая U и U и имеющая меньшее число ребер. Т.о. существует связывающая U иU цепь М с минимальным количеством ребер р. Минимальная длина простой цепи с началом U и концом U называется расстояние d (U U) между этими вершинами.

Расстояние d(U’ U”) удовлетворяет аксиомам метрики.

1) d(U’ U”) >0 при цепи d(U’ U”) = 0 если U’= U”

2) d(U’ U”) = d (U’ U”)

3) Справедливо неравенство треугольника d(U’ U”)+d(U’ U”) >d(U’ U”).

Диаметр графа

d(G) = max d (U’ U”); U’, U”  G (2.6)

Пусть V – произвольная вершина графа G. Максимальным удалением в графе G от вершины U называется величина (U) = max d(U U’) U’ G

Вершина U называется центром графа, если максимальное удаление от нее принимает минимальное значение

P (G) = min p (U’), U’  G (2.7)

Максимальное удаление р (G) от центра называется радиусом графа.

Центр не обязательно должен быть единственным.

Например в полном неориентированном графе, в котором любые две различные вершины U’ U” V соединены ребром, радиус равен 1 и любая вершина U V является центром.

Связный граф- все его вершины связаны между собой.

Множество внутренней устойчивости.

Множество SX графа G=(X,Г) называют внутренне устойчивым, если никакие две вершины из S не смежны, т.е. для любого XS имеет место ГхS=.

Множество внутренней устойчивости, содержащее наибольшее число элементов, называют наибольшим внутренне устойчивым множеством, а число элементов этого множества - числом внутренней устойчивости графа G. Наибольшее внутреннее устойчивое множество играет важную роль в теории связи.

Множество внешней устойчивости.

Множество ТХ графа G=(X,Г) называют внешне устойчивым, если любая вершина, не принадлежащая Т, соединена дугами с вершинами из Т, т.е. для любого хТ имеет место ГхТ=.

Множество внешней устойчивости, содержащее наименьшее число элементов, называют наименьшим внешне устойчивым множеством, а число элементов этого множества - числом внешней устойчивости графа G.