Page 62 - 4386

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

множині, а інша кінцева вершина не належить ні одній із уже

сформованих множин;

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

сформованих множин;

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

множинам.

Якщо має місце випадок а, то зафарбувати обране ребро в

жовтий колір (воно не включається в дерево) і повернутися до

початку кроку 2. Якщо має місце випадок б, то зафарбувати

обране ребро в зелений колір (воно включається в дерево) і

включити його кінцеву вершину, що не належала раніше жодній

множині, у ту множину, якій належить інша кінцева вершина

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

розглянуте ребро в зелений колір і сформувати нову множину з

його кінцевих вершин. Нарешті, якщо має місце випадок г, то

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

яким належать його кінцеві вершини, злити в оду нову множину.

По завершенню кроку 2 перейти до кроку 3.

Крок 3. Якщо всі вершини графа увійшли в одну множину,

закінчити процедуру, тому що при цій умові зелені ребра

утворюють кістякове дерево. А якщо ні, то повернутися до

початку кроку 2.

Необхідно відзначити, що описаний алгоритм складається з

багаторазового повторення кроку 2, причому при кожному

виконанні даного кроку деяке ребро зафарбовується в певний

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

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

алгоритм повинен закінчитися через скінченне число кроків.

61