Ациклічний граф (граф, що не містить циклів) назив. деревом. Кістяковим деревом графа назив. такий його суграф (підграф, в якому обов’язково мають бути задіяні всі вершини), який є деревом.
Для довільного графа G = (V, Е) з n вершинами та m ребрами наступні твердження є рівносильні: 1)граф G – дерево. 2) G – зв’язний граф та m = n-1; 3) 2) G – ациклічний граф; m = n-1.
Щоб отримати кістякове дерево графа, необхідно послідовно вилучати ребра, що входять до складу хоча б одного циклу в графі. Граф скінчений, і тому на деякому етапі буде отриманий ациклічний граф, який і є кістяковим деревом.
Цикломатичне число графа.
Нехай граф G має k компонент зв’язності. Це число – цикломатичне число графа.
Цикломатичне число характеризує к-ть ребер, які необхідно вилучити з графа, щоб отримати його кістяковий ліс. цикломатичне число є додатнім. цикломатичне число дерева = 0.
Кістякове дерево зв’язного графа.
див. пит. 67
Алгоритм Крускала
1) вибрати в графі G ребро мінімальної ваги. Присвоїти і=2.
2)якщо і= n, то закінччуємо роботу алгоритму. В іншому випадку:
3)побудувати граф G', додаючи до отриманого на попередньому етапі графа ребро мін. довжини, обране серед множини ребер, кожне з яких інцидентне якій-небудь вершині графа G, але яке не міститься в графі G'. і=і+1, і переходимо до кроку 2.
