Ранг та цикломатичне число графа

Розглянемо граф на вершинах і ребрах, який має компонент зв’язності.

Означення 2.3.2. Рангом графа називають число, яке дорівнює різниці між кількістю його вершин і компонент зв’язності:

Означення 2.3.3. Цикломатичним числом графа називають число, яке дорівнює різниці між кількістю його ребер і вершин плюс кількість компонент компонент зв’язності:

Зауважимо, що існує зв’язок між рангом і цикломатичним числом графа:

Ранг і цикломатичне число – найважливіші характеристики графа.

Теорема 2.3.2. Нехай граф, одержаний з графа додаванням нового ребра між вершинами та . Тоді:

1) якщо чи вони можуть бути з’єднані ланцюгом в , то

та ;

2) якщо чи вони не можуть бутиз’єднані ланцюгом в , то

та .

Доведення.

Якщо виконується умова 1), то додавання нового ребра кількості компонент зв’язності графа не змінює. Очевидно, що .

Тому

Випадок 1) доведено.

Якщо ж виконується умова 2), то додане ребро – перешийок між компонентами зв’язності графа , тому воно зменшує їх кількіть на 1.

У цьому випадку .

Тоді

Випадок 2) доведено. Теорему доведено¾.

Наслідок. .

Доведення.

Якщо граф – вироджений, тобто має лише вершини, а ребра – відсутні, то і . За теоремою 2.3.2 додавання нового ребра збільшує або , або . Отже, числа та можуть лише зростати.

Наслідок доведено¾.

Підсумовуючи вище сказане, бачимо, що цикломатичне число графа вказує на кількість у ньому циклів.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Компоненти зв’язності	\|	Дерева і ліси

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.003 сек.