показанные иа рис. 9.18, можно представить в виде следующего множества предложений:
связь( а, b).
связь( b, с).
. . .
дуга( s, t, 3).
дуга( t, v, 1).
дуга( u, t, 2).
. . .
Другой способ - весь граф представлять как один объект. В этом случае графу соответствует пара множеств - множество вершин и множество ребер. Каждое множество можно задавать при помощи списка, каждое ребро - парой вершин. Для объединения двух множеств в пару будем применять функтор граф, а для записи ребра - функтор р. Тогда (ненаправленный) граф рис. 9.18 примет вид:
G1 = граф( [a, b, c, d],
[р( а, b), р( b, d), р( 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]]
Здесь символы '->' и '/' - инфиксные операторы.
Какой из способов представления окажется более удобным, зависит от конкретного приложения, а также от того, какие операции имеется в виду выполнять над графами. Вот типичные операции:
найти путь между двумя заданными вершинами;
найти подграф, обладающий некоторыми заданными свойствами.
Примером последней операции может служить построение основного дерева графа. В последующих разделах, мы рассмотрим некоторые простые программы для поиска пути в графе и построения основного дерева.
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, необходимо:
