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



         

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


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

                            % А содержится в Дер

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

                       % А-В не порождает цикла

        смеж( А, В, Граф) :-

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

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

        вершина( А, Граф) :-

                                % А содержится в графе, если

                смеж( А, _, Граф).

                             % А смежна какой-нибудь вершине

line();

Pис. 9. 22.  Построение остовного дерева: алгоритмический подход.

Предполагается, что Граф - связный граф.

связный граф; Дер1 и Дер - два подмножества G, являющиеся деревьями. Дер

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

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


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