Page 64 - 4386

алгоритму є порожніми. Результати виконання кожного кроку

алгоритму наведено в табл. 6.1.

Рисунок 6.3

Таблиця 6.1 – Результати виконання алгоритму побудови

кістякового дерева

Ребро Колір Множина № 1 Множина № 2

(a, b) Зелений a, b ∅

(d, e) Зелений a, b d, e

(a, d) Зелений a, b, d, e ∅

(b, e) Жовтий a, b, d, e ∅

(е, с) Зелений a, b, с, d, e ∅

Алгоритм закінчується переглядом ребра (е, с), оскільки

після цього вершини розглянутого графа попадають в одну

множину. Отже, чотири зелені ребра (а, b), (d, е), (a, d) та (е, с)

утворюють для даного графа кістякове дерево (рис. 6.4 а).

а б

Рисунок 6.4

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

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

графа. Зокрема, якби ребра проглядались у зворотному порядку,

63