% А-В не порождает цикла
смеж( А, В, Граф) :-
принадлежит ( А-В, Граф);
принадлежит ( В-А, Граф).
вершина( А, Граф) :- % А содержится в графе, если
смеж( А, _, Граф). % А смежна какой-нибудь вершине
Pис. 9. 22. Построение остовного дерева: алгоритмический подход.
Предполагается, что Граф - связный граф.
связный граф; Дер1 и Дер - два подмножества G, являющиеся деревьями. Дер - остовное дерево графа G, полученное добавлением некоторого (может быть пустого) множества ребер из G к Дер1. Можно сказать, что 'Дер1 расширено до Дер'.
Интересно, что можно написать программу построения остовного дерева совершенно другим, полностью декларативным способом, просто формулируя на Прологе некоторые математические определения. Допустим, что как графы, так и деревья задаются списками своих ребер, как в программе рис. 9.22. Нам понадобятся следующие определения:
(1) Т является остовным деревом графа G, если
Т - это подмножество графа G и
Т - дерево и
Т 'накрывает' G, т.е. каждая вершина из G содержится также в Т.
(2) Множество ребер Т есть дерево, если
Т - связный граф и
Т не содержит циклов.
Эти определения можно сформулировать на Прологе (с использованием нашей программы путь из предыдущего раздела) так, как показано на рис. 9.23. Следует, однако, заметить, что эта программа в таком ее виде не представляет практического интереса из-за своей неэффективности.
% Построение остовного дерева
% Графы и деревья представлены списками ребер.
остдерево( Граф, Дер) :-
подмнож( Граф, Дер),
дерево( Дер),
накрывает( Дер, Граф).
дерево( Дер) :-
связи( Дер),
not имеетцикл( Дер).
связи( Дер) :-
not ( вершина( А, Дер), вершина( В, Дер),
not путь( А, А, Дер, _ ) ).
имеетцикл( Дер) :-
смеж( А, В, Дер),
путь( А, В, Дер, [А, X, Y | _ ). % Длина пути > 1
накрывает( Дер, Граф) :-
not ( вершина( А, Граф), not вершина( А, Дер) ).
