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



         

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


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

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

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

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

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

    line();

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

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

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

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

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

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

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

                    связи( Дер),

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

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

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

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

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

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



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