Page 57 - 4386

Щоб одержати кістякове дерево зв’язного графа G=(V, E),

можна послідовно вилучати з нього ребра, що входять до складу

хоча б одного циклу, і кожного разу одержувати зв’язний граф.

Оскільки граф G скінченний, то на деякому кроці залишиться

ациклічний зв’язний граф, який буде кістяковим деревом графа.

При цьому кількість ребер, що залишаться в кістяковому дереві

графа, дорівнює |V|-1. Отже, вилучено |E|-|V|+1 ребер. Слід

зауважити, що ребро зв’язного графа, інцидентне кінцевій

вершині, входить в усі зв’язні суграфи графа, оскільки вилучення

такого ребра робить відповідну вершину ізольованою.

З наведеного вище випливає, що зв’язний неорієнтований

граф завжди має кістякове дерево.

Для побудови кістякового лісу для незв’язного графа

необхідно побудувати кістякове дерево для кожної компоненти

зв’язності. Ця операція потребує вилучення |E|-|V|+k ребер, де k –

кількість компонент зв’язності графа.

5.5 Цикломатичне число графа

Нехай граф G=(V, E) має k компонент зв’язності. Кількість

ребер ν(G)=|E|-|V|+k, що необхідно вилучити з графа для

одержання його кістякового лісу, називається цикломатичним

числом графа G. У довільному графі G воно дорівнює сумі

цикломатичних чисел його зв’язних компонент.

Отже, справджуються такі твердження.

1. Для довільного графа G виконується ν(G)≥0;

2. Граф G є лісом тоді і тільки тоді, коли ν(G)=0;

3. Граф G має рівно один простий цикл тоді і тільки тоді,

коли ν(G)=1;

4. Кількість циклів у графі G не менша ніж ν(G).

56