Page 67 - 4386

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

району.

Розв'язок.

Розташуємо ребра даного графа в порядку зростання їх ваг:

(a, b), (с, d), (d, e), (с, е), (a, с), (b, e), (b, d), (b, с), (a, d) та (a, e).

Сформуємо дві множини №1 та №2, які на початок роботи

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

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

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

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

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

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

(d, e) 10 Зелений a, b с, d, e
(с, е) 20 Жовтий a, b с, d, e

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

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

множину, то алгоритм завершує свою роботу. Таким чином,

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

п’яти міст складає 73 умовні одиниці (рис. 6.6).

Рисунок 6.6

66