Page 66 - 4386

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

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

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

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

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

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

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

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

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

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

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

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

п’яти міст складає 300 умовних одиниць (рис. 6.5).

Рисунок 6.5

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

Даний алгоритм являє собою алгоритм побудови

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

зростання їх ваг (перше ребро – з мінімальною вагою, останнє

ребро – з максимальною). Якщо два чи більше ребер мають

однакові ваги, то вони впорядковуються довільним чином.

Приклад 6.3. Побудувати мінімальне кістякове дерево для

графа, зображеного на рис. 6.1 б. Даний граф представляє мережу

65