Page 65 - 4386

то алгоритм побудував би кістякове дерево (рис. 6.4 б), що

складається з ребер (е, с), (а, с), (с, d) та (b, с).

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

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

Розглянемо задачу пошуку кістякового дерева з мінімально

або максимально можливою вагою, яка називається відповідно

задачею про мінімальне або максимальне кістякове дерево.

Очевидно, якщо граф містить деяке кістякове дерево, то в ньому

можна виділити як мінімальне, так і максимальне кістякове

дерево. Такі кістякові дерева можуть бути легко побудовані за

допомогою розглянутого вище алгоритму при виборі певного

порядку перегляду ребер.

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

дерева

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

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

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

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

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

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

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

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

району.

Розв'язок.

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

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

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

64