Если А = 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), Реб).
