Неизвестно - Prolog

Для представления направленного графа (рис. 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]]

Здесь символы '->' и '/' - инфиксные операторы.

Какой из способов представления окажется более удобным, зависит от конкретного приложения, а также от того, какие операции имеется в виду выполнять над графами. Вот типичные операции:

найти путь между двумя заданными вершинами;

найти подграф, обладающий некоторыми заданными свойствами.

Примером последней операции может служить построение основного дерева графа. В последующих разделах, мы рассмотрим некоторые простые программы для поиска пути в графе и построения основного дерева.

9. 5. 2. Поиск пути в графе

Пусть G - граф, а А и Z - две его вершины. Определим отношение

путь( А, Z, G, Р)

где Р - ациклический путь между А и Z в графе G. Если G - граф, показанный в левой части рис. 9.18, то верно:

путь( a, d, G, [a, b, d] )

путь( а, d, G, [a, b, c, d] )

Поскольку путь не должен содержать циклов, любая вершина может присутствовать в пути не более одного раза. Вот один из методов поиска пути:

Для того, чтобы найти ациклический путь Р между А и Z в графе G, необходимо:

Если А = Z , то положить Р = [А], иначе найти ациклический путь Р1 из произвольной вершины Y в Z, а затем найти путь из А в Y, не содержащий вершин из Р1.

В этой формулировке неявно предполагается, что существует еще одно отношение, соответствующее поиску пути со следующий ограничением: путь не должен проходить через вершины из некоторого подмножества (в данном случае Р1) множества всех вершин графа. В связи с этим мы определим ещё одну процедуру:

путь1( А, Р1, G, Р)

Аргументы в соответствии с рис. 9.19 имеют следующий смысл:

А - некоторая вершина,

Pис. 9. 19. Отношение путь1: Путь- это путь между Аи Z, в своей

заключительной части он перекрывается с Путь1.

G - граф,

P1 - путь в G,

Р - ациклический путь в G, идущий из А в начальную вершину пути Р1, а затем - вдоль пути Р1 вплоть до его конца.

Между путьи путь1имеется следующее соотношение:

путь( А, Z, G, Р) :- путь1( А, [Z], G, Р).

На рис. 9.19 показана идея рекурсивного определения отношения путь1. Существует "граничный" случай, когда начальная вершина пути P1 (Y на рис. 9.19) совпадает с начальной вершиной А пути Р. Если же начальные вершины этих двух путей не совпадают, то должна существовать такая вершина X, что

(1) Y - вершина, смежная с X,

(2) Х не содержится в Р1 и

(3) для Р выполняется отношение

путь1( А, [Х | Р1], G, Р).

путь( A, Z, Граф, Путь) :-

путь1( А, [Z], Граф, Путь).

путь1( А, [А | Путь1, _, [А | Путь1] ).

путь1( А, [Y | Путь1], Граф, Путь) :-

смеж( X, Y, Граф),

принадлежит( X, Путь1), % Условие отсутствия цикла

путь1( А, [ X, Y | Путь1], Граф, Путь).

Рис. 9. 20. Поиск в графе Графациклического пути Путьиз А в Z.

На рис. 9.20 программа показана полностью. Здесь принадлежит- отношение принадлежности элемента списку. Отношение

смеж( X, Y, G)

означает, что в графе G существует дуга, ведущая из Х в Y. Определение этого отношения зависит от способа представления графа. Если G представлен как пара множеств (вершин и ребер)

G = граф( Верш, Реб)

то

смеж( X, Y, граф( Верш, Реб) ) :-

принадлежит( р( X, Y), Реб);

принадлежит( р( Y, X), Реб).

Классическая задача на графах - поиск Гамильтонова цикла, т.е. ациклического пути, проходящего через все вершины графа. Используя отношение путь, эту задачу можно решить так:

гамильтон( Граф, Путь) :-