Алгоритм получения дерева из графа

1. Выбирается любая вершина. Счетчик i принимаем равным 1 (i=1).

2. Если i = k, то дерево построено.

3. Если i ¹ k, то выбирается любая незадействованная вершина и ребро, соединяющее данную вершину с любой из выбранных.

4. Счетчик увеличивается на единицу.(i= i+1).

5. Переход на пункт 2.

ПРИМЕР

Преобразовать граф, представленный на рис. 3.12 в дерево:

Рис. 3.12

1. Найдем цикломатическое число , т.е. необходимо изъять 4 ребра.

2. Выбираем вершину 5.

3. Присоединяем вершину 3.

4.

5. Присоединяем вершину 4.

6.

7. Присоединяем вершину 1.

8.

9. Присоединяем вершину 2.

10.

11. Все вершины охвачены. Дерево построено

Рис. 3.13