...
дуга( s, t, 3).
дуга( t, v, 1).
дуга( u, t, 2).
...
Другой способ — весь граф представлять как один объект. В этом случае графу соответствует пара множеств — множество вершин и множество ребер. Каждое множество можно задавать при помощи списка, каждое ребро — парой вершин. Для объединения двух множеств в пару будем применять функтор граф, а для записи ребра — функтор p. Тогда (ненаправленный) граф рис. 9.18 примет вид:
G1 = граф( [a, b, c, d],
[p( а, b), p( b, d), p( b, с), p( c, d)] )
Рис. 9.18. (а) Граф. (b) Направленный граф. Каждой дуге приписана ее стоимость.
Для представления направленного графа (рис. 9.18), применив функторы диграф и д (для дуг), получим
G2 = диграф( [s, t, u, v],
[д( s, t, 3), д( t, v, 1), д( t, u, 5), д( u, t, 2),
д( v, u, 2) ] )
Если каждая вершина графа соединена ребром еще по крайней мере с одной вершиной, то в представлении графа можно опустить множество вершин, поскольку оно неявным образом содержится в списке ребер.
Еще один способ представления графа — связать с каждой вершиной список смежных с ней вершин. В этом случае граф превращается в список пар, каждая из которых состоит из вершины- плюс ее список смежности. Наши графы (рис. 9.18), например, можно представить как
G1 = [ a->[b1, b->[a, c, d], c->[b, d], d->[b, c] ]
G2 = [s->[t/3], t->[u/5, v/l], u->[t/2], v->[u/2]]
Здесь символы '->' и '/' — инфиксные операторы.
Какой из способов представления окажется более удобным, зависит от конкретного приложения, а также от того, какие операции имеется в виду выполнять над графами. Вот типичные операции:
• найти путь между двумя заданными вершинами;
• найти подграф, обладающий некоторыми заданными свойствами.
Примером последней операции может служить построение основного дерева графа. В последующих разделах, мы рассмотрим некоторые простые программы для поиска пути в графе и построения основного дерева.
Пусть G — граф, а А и Z — две его вершины. Определим отношение
путь( А, Z, G, P)
где P — ациклический путь между А и Z в графе G. Если G — граф, показанный в левой части рис. 9.18, то верно:
путь( a, d, G, [a, b, d] )
путь( а, d, G, [a, b, c, d] )
Поскольку путь не должен содержать циклов, любая вершина может присутствовать в пути не более одного раза. Вот один из методов поиска пути:
Для того, чтобы найти ациклический путь P между А и Z в графе G, необходимо:
Если А = Z , то положить P = [А], иначе найти ациклический путь P1 из произвольной вершины Y в Z, а затем найти путь из А в Y, не содержащий вершин из P1.
В этой формулировке неявно предполагается, что существует еще одно отношение, соответствующее поиску пути со следующий ограничением: путь не должен проходить через вершины из некоторого подмножества (в данном случае P1) множества всех вершин графа. В связи с этим мы определим ещё одну процедуру:
путь1( А, P1, G, P)
Аргументы в соответствии с рис. 9.19 имеют следующий смысл:
• А — некоторая вершина,
• G — граф,
• P1 — путь в G,
• P — ациклический путь в G, идущий из А в начальную вершину пути P1, а затем — вдоль пути P1 вплоть до его конца.
Pис. 9.19. Отношение путь1: Путь — это путь между А и Z, в своей заключительной части он перекрывается с Путь1.
Между путь и путь1 имеется следующее соотношение:
путь( А, Z, G, P) :- путь1( А, [Z], G, P).
На рис. 9.19 показана идея рекурсивного определения отношения путь1. Существует "граничный" случай, когда начальная вершина пути P1 (Y на рис. 9.19) совпадает с начальной вершиной А пути P. Если же начальные вершины этих двух путей не совпадают, то должна существовать такая вершина X, что
(1) Y — вершина, смежная с X,
(2) X не содержится в P1 и
(3) для P выполняется отношение путь1( А, [X | P1], G, P).
путь( A, Z, Граф, Путь) :-
путь1( А, [Z], Граф, Путь).
путь1( А, [А | Путь1, _, [А | Путь1] ).
путь1( А, [Y | Путь1], Граф, Путь) :-
смеж( X, Y, Граф),
принадлежит( X, Путь1), % Условие отсутствия цикла
путь1( А, [ X, Y | Путь1], Граф, Путь).
Рис. 9.20. Поиск в графе Граф ациклического пути Путь из А в Z.
