Программирование на языке ПРОЛОГ для искуственного интеллекта




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


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

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

  • Т - это подмножество графа G и
  • Т - дерево и
  • Т "накрывает" G, т.е. каждая вершина из G содержится также в Т.

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

  • Т - связный граф и
  • Т не содержит циклов.

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

line();

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

        остдерево( Граф, Дер) :-
                подмнож( Граф, Дер),
                дерево( Дер),
                накрывает( Дер, Граф).

        дерево( Дер) :-
                связи( Дер),
                not имеетцикл( Дер).

        связи( Дер) :-
                not ( вершина( А, Дер), вершина( В, Дер),
                            not путь( А, А, Дер, _ ) ).

        имеетцикл( Дер) :-
                смеж( А, В, Дер),



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