2014-02-09
3112
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
