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

Граф называется связным, если между любыми двумя его вершинами существует путь. Остовное дерево графа G = (V,E) - это связный граф T = (V,E1) без циклов,в котором E1 - подмножество E.

Определим процедуру

osttree(e,T),

где T - остовное дерево графа G (G - связный граф), e - произвольно выбранное ребро графа G.

Остовное дерево можно строить так: 1) начать с произвольного ребра графа G; 2) добавлять новые ребра, постоянно следя за тем, чтобы не образовывались циклы; 3) продолжать этот процесс до тех пор, пока не обнаружится, что нельзя присоединить ни одного ребра, поскольку любое новое ребро порождает цикл. Отсутствие цикла обеспечивается так: ребро присоединяется к дереву лишь в том случае, когда одна из его вершин уже содержится в строящемся дереве, а другая пока еще не включена в него.

Основное отношение, используемое в программе,

expand(Tree1,Tree).

Здесь Tree остовное дерево, полученное добавлением множества ребер из G к дереву Tree1.

Пример 3. Построение остовного дерева.

arca(a,b). arca(b,c). arca(c,d). arca(b,d).

member(X,[X|_]).

member(X,[_|Tail]):-member(X,Tail).

osttree(arca(A,B),Tree):- expand([arca(A,B)],Tree).

expand(Tree1,Tree):- ap_arca(Tree1,Tree2), expand(Tree2,Tree).

expand(Tree,Tree):-not(ap_arca(Tree,_)).

ap_arca(Tree,[arca(A,B)|Tree]):- arca(A,B), node(A,Tree), not(node(B,Tree));

arca(A,B),node(B,Tree), not(node(A,Tree)).