Построение остовного дерева - часть 4

Допустим, что как графы, так и деревья задаются списками своих ребер, как в программе рис. 9.22. Нам понадобятся следующие определения:

(1)        Т является остовным деревом графа G, если

Т - это подмножество графа G и

Т - дерево и

Т "накрывает" G, т.е. каждая вершина из G содержится также в Т.

(2)        Множество ребер Т есть дерево, если

Т - связный граф и

Т не содержит циклов.

Эти определения можно сформулировать на Прологе (с использованием нашей программы путь

из предыдущего раздела) так, как показано на рис. 9.23. Следует, однако, заметить, что эта программа в таком ее виде не представляет практического интереса из-за своей неэффективности.

line();

%  Построение остовного дерева

%  Графы и деревья представлены списками ребер.

        остдерево( Граф, Дер) :-

                подмнож( Граф, Дер),

                дерево( Дер),

                накрывает( Дер, Граф).

        дерево( Дер) :-

                связи( Дер),

                not имеетцикл( Дер).

        связи( Дер) :-

                not ( вершина( А, Дер), вершина( В, Дер),

                            not путь( А, А, Дер, _ ) ).

        имеетцикл( Дер) :-

                смеж( А, В, Дер),

Содержание  Назад  Вперед

---

---

---