Граф называется связным, если между любыми двумя его вершинами существует путь. Остовное дерево графа 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)).
node(A,Tree):- member(arca(A,_),Tree); member(arca(_,A),Tree).
Содержание работы
1. Выполнить рассмотренные примеры.
2. Составить программу, которая решает задачу соответствующего варианта.
3. Подобрать тестовые данные, проверяющие работу программы.
4. Провести анализ ошибок и полученных результатов, составить отчет о проделанной работе.