Path1(А, Р1, G, Р)

Постановка 5.

Ациклічний шлях Р між вершинами А і Z у заданому явно графі G позначимо відношенням path(А, Z, G, Р).

Для графа G на рис. 1 (а) вірними є твердження:

path(a, d, G, [a, b, d])

path(а, d, G, [a, b, c, d]).

Оскільки шлях має бути ациклічним, всяка вершина у шляху може зустрітись лише раз. Один з методів пошуку шляху відповідно до предикату path(А, Z, G, Р):

§ якщо А=Z, то покласти шлях Р= [А],

§ інакше знайти ациклічний шлях Р1 з довільної вершини Y в вершину Z, а потім шлях з А в Y без використання вершин з шляху Р1.

Для цього визначено ще один предикат:

чиї аргументи мають наступний смисл:

§ А - деяка вершина,

§ P1 - шлях в G,

§ G - граф,

§ Р - ациклічний шлях в G, що йде з А в початкову вершину шляху Р1, а потім - уздовж шляху Р1.

Pис. 3. Відношення path фіксує шлях Р між А і Z, що у своїй заключній частині співпадає зі шляхом Р1 між вершинами Y і Z відношення path1.

Між path і path1 має місце наступне співвідношення:

path(А, Z, G, Р):- path1(А, [Z], G, Р).

На рис.3 показана ідея рекурсивного визначення відношення path1. Існує "граничний" випадок, коли початкова вершина шляху P1 (Y на рис. 3) збігається з початковою вершиною А шляху Р. Якщо ж початкові вершини цих двох шляхів не збігаються, то має існувати така вершина X, що

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

(2) Х не втримується в Р1 та

(3) для Р виконується відношення

path1(А, [Х | Р1], G, Р).

Таким чином, пошук у графі G ациклічного шляху Р з вершини А в Z визначається наступною програмою:

path(A, Z, G, Р):- path1(А, [Z], G, Р).

path1(А, [А | Р1], _, [А | Р1]).

path1(А, [Y | Р1], G, Р):- incident(X, Y, G),

not(member(X, Р1)), % Умова відсутності циклу

path1(А, [ X, Y | Р1], G, Р).

Тут відношення інцидентності (суміжності) вершин

Дата добавления: 2014-01-04