Page 61 - 4386

належать окремій зв'язній компоненті, об’єднуються в множину.

Деяке ребро утворює цикл із ребрами, уже включеними в дерево,

якщо обидві його кінцеві вершини належать одній і тій же

зв'язній компоненті (одній і тій же множині).

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

закінчується, коли кількість ребер, зафарбованих у зелений колір,

стає рівна числу, на одиницю меншу числа вершин розглянутого

графа або, що те ж саме, коли всі вершини графа виявляються в

одній множині. Зазначені умови завершення алгоритму дійсно

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

число ребер, на одиницю менше числа вершин. Причому, ці

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

кістякове дерево. Якщо ж граф такого дерева не містить, тобто є

незв'язним, алгоритм закінчується після зафарбування всіх ребер

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

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

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

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

є не зафарбованими і жодна з множин не сформована.

Крок 1. Вибрати будь-яке ребро, що не є петлею.

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

включивши в неї кінцеві вершини зафарбованого ребра.

Крок 2. Вибрати будь-яке незафарбоване ребро, яке не є

петлею. Якщо в графі такого ребра не знайдеться, закінчити

процедуру – вхідний граф не містить кістякового дерева. Після

зазначеного вибору можливі чотири різні випадки:

а) обидві кінцеві вершини обраного ребра належать одній і

тій же множині;

60