Алгоритм построения всех каркасов

Основные понятия
Пусть задан граф в стандартной форме G = {V, E}, где V – множество вершин графа, Е – множество рёбер, состоящее из пар вида (х, у), где х, у принадлежат V.
Каркас (остовное дерево) графа G – это подграф S⊂G, содержащий все вершины и не содержащий циклов. Остовное дерево степени n содержит (n – 1) ребро.
Один из способов построения:
- удаляем из графа G все рёбра;
- добавляем (n – 1) ребро по правилу: очередное ребро добавляется, если оно инцидентно изолированной вершине.
Подробный алгоритм
Обозначим граф G = {VG, EG}, а искомый каркас S = {VS, ES}. Перенумеруем вершины в произвольном порядке. Будем считать, что вершины обозначены натуральными числами от 1 до n. То же выполним для рёбер – перенумеруем натуральными числами от 1 до m.
Построение каркаса графа степени n состоит в том, чтобы выбрать (n – 1) ребро по некоторому правилу.
1. Алгоритм выбора k элементов из списка.
Пусть имеется список (упорядоченное множество) элементов L1. Требуется составить все возможные списки L2, содержащие ровно k различных элементов из списка L1.
Используем метод ветвей и границ. Сначала построим все возможные списки, в котором первым элементом будет первый элемент списка L1, затем – где первым элементом будет второй элемент L1 и т.д.
Реализация на Прологе:
combin(L1, L2, L2, N):-
length(L2, N), !.
combin([H|T], L2, L3, N):-conc(L2, [H], L4),
combin(T, L4, L3, N).
combin([H|T], L2, L3, N):-combin(T, L2, L3, N).
Правило combin(L1, L2, L2, N) имеет 4 аргумента: L1 – исходный список, L2 – промежуточный результат, L3 – требуемый результат, N – нужное количество элементов. Если длина L2 равна N, то список построен, и он является результатом (первый предикат). Иначе добавляем в список L2 первый элемент списка L1 (Н) и продолжаем построение для остатка списка Т (второй предикат). Иначе продолжаем построение для остатка списка (третий предикат).
Длина списка определяется предикатом length.
length([], 0).
length([_|T], N):-length(T, N1),
N is N1 + 1.
Добавление элемента в список – предикатом conc.
conc([], L, L).
conc([H|T], L, [H|T1]):-conc(T, L, T1).
Пусть известны множество (список) рёбер ЕG исходного графа G и его степень N. Тогда построение всех возможный множеств (списков) длины (N – 1) можно задать следующим целевым предикатом:
?- combin(Еg, [], Еs, N - 1),
write(Еs),
nl, fail.
Результат выполнения для исходного множества ЕG = [1, 2, 3, 4]: сначала выведено исходное множество, затем – полученные трёхэлементные наборы.
Compiling the file:
C:\Users\User\Downloads\Pr_karkas
0 errors, 0 warnings.
[1,2,3,4]
[1,2,3]
[1,2,4]
[1,3,4]
[2,3,4]
No.
2. Выбор подходящих наборов.
В алгоритме построения каркаса графа требуется выбрать (n – 1) ребро так, чтобы им были инцидентны все вершины графа. В исходном алгоритме ребро проверялось перед добавлением в каркас. Рассмотрим вариант построения каркаса, когда сначала выбирается (n – 1) ребро, а затем проверяется, что каждая вершина графа инцидентна хотя бы одному ребру.
Выбор (n – 1) ребра реализован выше, обозначим это множество Е. Пусть задано множество вершин V. Считаем, что ребро задано парой чисел [a, b], где a, b – вершины, инцидентные ребру. Процесс проверки полученного множества E следующий:
- выбираем из Е очередное ребро [a, b]; удаляем из V вершины a, b;
- повторяем, пока V не станет пуст.
Для проверки зададим предикат exam(V, E), где V – список вершин, Е – список рёбер. Если список V пуст, то проверка успешна. Иначе удаляем вершины очередного ребра и проверяем остаток списка Е.
exam([], _).
exam(V, [H|T]):-
[X,Y] = H,
delete(V, X, V1),
delete(V1, Y, V2),
exam(V2, T).
Для удаления используется правило delete(L, X, L1), которое исключает из списка L элемент X и записывает результат в список L1. Если элемента Х в списке L нет, то L1 = L.
delete([], _, []):- !.
delete([H|T], H, T):- !.
delete([H|T], Z, [H|T1]):-delete(T, Z, T1).
3. Задание графа G.
Исходный граф задаётся списком вершин и рёбер, например, граф в виде квадрата:
% graphvertex([1, 2, 3, 4]).
% edgesedge([[1, 2],[1, 3],[2, 4],[3, 4]]).
Целевой предикат сначала определяет множества вершин и рёбер, затем находит степень графа, печатает исходные множества вершин и рёбер и выводит найденные каркасы.
Compiling the file:
C:\Users\User\Downloads\Pr_karkas
0 errors, 0 warnings.
Graph vertices: [1,2,3,4]
Graph edges: [[1,2],[1,3],[2,4],[3,4]]
Karkass:
[[1,2],[1,3],[2,4]]
[[1,2],[1,3],[3,4]]
[[1,2],[2,4],[3,4]]
[[1,3],[2,4],[3,4]]
No.
4. Программа на Strawberry Prolog v.3.0
% goal
?- vertex(V),
write("Graph vertices: "),
write(V), nl,
length(V, N),
edge(E),
write("Graph edges: "),
write(E), nl, nl,
write("Karkass: "), nl,
N1 is N - 1,
combin(E, [], E1, N1),
exam(V, E1),
write(E1),
nl, fail.
% database
% graph
vertex([1, 2, 3, 4]).
% edges
edge([[1, 2],[1, 3],[2, 4],[3, 4]]).
% predicates
% length of list: length(List, N)
length([], 0).
length([Z|T], N):-length(T, N1),
N is N1 + 1.
% confluence two lists, third list as result: conc(L1, L2, L3)
conc([], L, L).
conc([H|T], L, [H|T1]):-conc(T, L, T1).
% combination N elements from list: combin(List, [], Comb, N)
combin(L1, L2, L2, N):-
length(L2, N), !.
combin([H|T], L2, L3, N):-conc(L2, [H], L4),
combin(T, L4, L3, N).
combin([H|T], L2, L3, N):-combin(T, L2, L3, N).
% delete element from list, second list as result: delete(L1, X, L2)
delete([], _, []):- !.
delete([H|T], H, T):- !.
delete([H|T], Z, [H|T1]):-delete(T, Z, T1).
% check karkas: exam(Vertex, Edge)
exam([], _):- !.
exam(V, [H|T]):-
[X,Y] = H,
delete(V, X, V1),
delete(V1, Y, V2),
exam(V2, T).
Тестирование программы:
граф К4
Compiling the file:
C:\Users\User\Downloads\Pr_karkas
0 errors, 0 warnings.
Graph vertices: [1,2,3,4]
Graph edges: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Karkass:
[[1,2],[1,3],[1,4]]
[[1,2],[1,3],[2,4]]
[[1,2],[1,3],[3,4]]
[[1,2],[1,4],[2,3]]
[[1,2],[1,4],[3,4]]
[[1,2],[2,3],[2,4]]
[[1,2],[2,3],[3,4]]
[[1,2],[2,4],[3,4]]
[[1,3],[1,4],[2,3]]
[[1,3],[1,4],[2,4]]
[[1,3],[2,3],[2,4]]
[[1,3],[2,3],[3,4]]
[[1,3],[2,4],[3,4]]
[[1,4],[2,3],[2,4]]
[[1,4],[2,3],[3,4]]
[[1,4],[2,4],[3,4]]
No.
несвязный граф
Graph vertices: [1,2,3,4]
Graph edges: [[1,2],[1,3]]
Karkass:
No.
дерево
Graph vertices: [1,2,3,4]
Graph edges: [[1,2],[1,3],[1,4]]
Karkass:
[[1,2],[1,3],[1,4]]
No.
граф К3
Graph vertices: [1,2,3]
Graph edges: [[1,2],[1,3],[2,3]]
Karkass:
[[1,2],[1,3]]
[[1,2],[2,3]]
[[1,3],[2,3]]
No.