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

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

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

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

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

Если y(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”).

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