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




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


                вершина( А, Дер).                             % А содержится в Дер
                не вершина( В, Дер).                        % А-В не порождает цикла

        смеж( А, В, Граф) :-
                принадлежит ( А-В, Граф);
                принадлежит ( В-А, Граф).

        вершина( А, Граф) :-                                 % А содержится в графе, если
                смеж( А, _, Граф).                              % А смежна какой-нибудь вершине

line();

Pис. 9. 22.  Построение остовного дерева: алгоритмический подход.
Предполагается, что Граф - связный граф.

связный граф; Дер1 и Дер - два подмножества G, являющиеся деревьями. Дер - остовное дерево графа G, полученное добавлением некоторого (может быть пустого) множества ребер из G к Дер1. Можно сказать, что "Дер1 расширено до Дер".

Интересно, что можно написать программу построения остовного дерева совершенно другим, полностью декларативным способом, просто формулируя на Прологе некоторые математические определения.


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