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

Граф называется связным, если между любыми двумя его вершинами существует путь. Остовное дерево графа 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. Провести анализ ошибок и полученных результатов, составить отчет о проделанной работе.

Контрольные задания

1. Определить, является ли связным заданный граф.

2. Найти все вершины графа, к которым существует путь заданной длины от выделенной вершины графа.

3. Найти все вершины графа, достижимые из заданной.

4. Подсчитать количество компонент связности заданного графа.

5. Найти диаметр графа, т.е. максимум расстояний между всевозможными парами его вершин.

6. Найти такую нумерацию вершин орграфа, при которой всякая дуга ведет от вершины с меньшим номером к вершине с большим номером.

7. Дан взвешенный граф. Построить остовное дерево минимальной стоимости.

8. Определить является ли граф гамильтоновым. Найти гамильтонов цикл, т. е. цикл, проходящий через все вершины графа.

9. Задана система односторонних дорог. Найти путь, соединяющий города A и B и не проходящий через заданное множество городов.

10. В заданном графе указать все его четырехвершинные полные подграфы.

11. Известно, что заданный граф - не дерево. Проверить, можно ли удалить из него одну вершину ( вместе с инцидентными ей ребрами), чтобы в результате получилось дерево.