Page 63 - 4386

Якщо алгоритм не закінчується побудовою кістякового

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

дерева. Це зумовлене наступною причиною. По закінченню

роботи алгоритму будуть сформовані принаймні дві множини,

для яких не найдеться жодного ребра, що з'єднує деякі вершини з

різних множин. Дійсно, якщо б таке ребро знайшлося, то воно в

процесі роботи алгоритму було б зафарбоване в зелений колір, а

відповідні множини злилися б в одну множину. Таким чином,

алгоритм робить саме те, для чого він призначений – будує для

графа кістякове дерево (за умови що граф містить таке дерево).

Описаний алгоритм має таку властивість – кожне ребро

проглядається не більше одного разу. Якщо в ході алгоритму

деяке ребро зафарбовується, то це ребро надалі не може бути

переглянуте заново. Алгоритми такого типу, у яких кожний з

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

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

і назавжди, називаються поїдаючими алгоритмами. Перевага

поїдаючих алгоритмів полягає в тому, що, по-перше, у процесі їх

роботи не доводиться витрачати час на повторний перегляд

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

визначити максимальну кількість необхідних операцій. Зокрема,

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

кроків не повинне перевищити числа ребер у відповідному графі.

Приклад 6.1. Побудувати кістякове дерево для графа,

зображеного на рис. 6.3.

Розв'язок.

Будемо переглядати ребра графа в такому довільно

обраному порядку: (a, b), (d, e), (a, d), (b, e), (е, с), (а, с), (с, d) та

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

62