Характеристики графів

Вирішення багатьох технічних завдань методами теорії графів зводиться до визначення тих або інших характеристик графів, хоча технічні додатки теорії графів розглядати в цьому посбнику неможливо, знайомство з найважливішими характеристиками графів може виявитися корисним при вивченні інших дисциплін.

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

Це число має цікавий фізичний зміст. Воно дорівнює найбільшому числу незалежних циклів у графі. При розрахунку електричних ланцюгів цикломатичним числом можна користуватися для визначення числа незалежних контурів.

Хроматичне число. Нехай р - натуральне число. Граф G називають р-хроматичним, якщо його вершини можна пофарбувати р різноманітними кольорами так, щоб ніякі дві суміжні вершини не були пофарбовані однаково. Найменше число р, при якому граф є р-хроматичним, називають хроматичним числом графа і позначають Y(G).

Якщо Y(G)=2, то граф називають біхроматичним. Необхідною і достатньою умовою того, щоб граф був біхроматичним, є відсутність у ньому циклів непарної довжини. Хроматичне число грає важливу роль при вирішенні завдань найбільш економного використання пам'яті при програмуванні. Проте його визначення, за винятком випадку біхроматичного графа, являє собою досить важке завдання, що потребує нерідко застосування електронних обчислювальних машин.

Нехай G - зв'язаний неорієнтований граф, V і U - будь-які дві його вершини. Тоді існує їхній простий ланцюг М (L1, L2, ... , Lq), що їх зв'язує.. Якщо кількість ребер q цього ланцюга не мінімальне з можливих , то існує ланцюг M( L1, L2, ... , Lq) , що зв'язує V і U і має менше число ребер. Таким чином, існує ланцюг М, що зв'язує V і U з мінімальною кількістю ребер р. Мінімальна довжина простого ланцюга з початком V і кінцем U називається відстань d (V, 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.

Нехай V - довільна вершина графа G. Максимальним віддаленням у графі G від вершини U називається величина (U) = max d(U, U'), U'Î G.

Вершина U називається центром графа, якщо максимальне віддалення від неї набуває мінімальне значення

P (G) = min p (U'), U' Î G.

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

Центр не обов'язково повинний бути єдиним.

Наприклад, у повному неорієнтованому графі, в якому будь-які дві різноманітні вершини U', U", або V з'єднані ребром, радіус дорівнює 1 і будь-яка вершина U і V є центром.

У зв'язному графі всі вершини пов'язані між собою.

Множина внутрішньої усталеності. Множину SÍX графа G=(X, Г) називають внутрішньо стійкою, якщо ніякі дві вершини з S не суміжні, тобто для будь-якого XÎS має місце ГхÇS=Æ.

Множину внутрішньої усталеності, що містить найбільше число елементів, називають найбільшою внутрішньо стійкою множиною, а число елементів цієї множини - числом внутрішньої усталеності графа G. Найбільша внутрішньо стійка множина відіграє важливу роль у теорії зв'язку.

Множина зовнішньої усталеності. Множину ТÌХ графа G=(X, Г) називають зовнішньо стійкою, якщо будь-яка вершина, що не належить Т, сполучена дугами з вершинами з множини Т, тобто для довільного хÏТ має місце Г_х ÇТ=Æ.

Множину зовнішньої усталеності, що містить найменше число елементів, називають найменшою зовнішньо стійкою множиною, а число елементів цієї множини - числом зовнішньої усталеності графа G.