Назад | Содержание| Вперёд 9. 5. Графы 9. 5. 1. ...

Назад | Содержание| Вперёд

9. 5. Графы

9. 5. 1. Представление графов

Графы используются во многихприложениях, например для представленияотношений, ситуаций или структур задач. Графопределяется как множество вершинвместе с множеством ребер, причем каждоеребро задается парой вершин. Если ребранаправлены, то их также называют дугами.Дуги задаются упорядоченными парами. Такие графы называются направленными.Ребрам можно приписывать стоимости, имена илиметки произвольного вида, в зависимости отконкретного приложения. На рис. 6.18 показаныпримеры графов.

В Прологе графы можно представлять различнымиспособами. Один из них - каждое ребро записывать ввиде отдельного предложения. Например, графы,показанные иа рис. 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)] )

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), Реб).

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

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

путь( _, _, Граф, Путь),

всевершины( Путь, Граф).

всевершины( Путь,Граф) :-

not (вершина( В, Граф),

not принадлежит( В, Путь) ).

Здесь вершина( В, Граф) означает: В- вершина графа Граф.

Каждому пути можно приписать его стоимость.Стоимость пути равна сумме стоимостей входящих внего дуг. Если дугам не приписаны стоимости, тотогда, вместо стоимости, говорят о длине пути.

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

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

путь1( A, P1, C1, G, Р, С)

Здесь С - стоимость пути Р, a C1 - стоимость пути Р1.В отношении смеж также появитсядополнительный аргумент, стоимость дуги. На рис.9.21 показана программа поиска пути, котораястроит путь и вычисляет его стоимость.

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

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

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

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

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

not принадлежит( X, Путь1),

Ст2 is Ст1 + СтXY,

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

Рис. 9. 21. Поиск пути вграфе: Путь - путь между А и Z в графе Графстоимостью Ст.

Эту процедуру можно использовать длянахождения пути минимальной стоимости. Мы можемпостроить путь минимальной стоимости междувершинами Верш1, Верш2 графа Граф,задав цели

путь( Bepш1, Верш2,Граф, МинПуть, МинСт),

not ( путь( Верш1, Верш2, Граф,_, Ст), Ст<МинСт )

Аналогично можно среди всех путей междувершинами графа найти путь максимальнойстоимости, задав цели

путь( _, _, Граф,МаксПуть, МаксСт),

not ( путь( _, _, Граф, _, Ст), Ст> МаксСт)

Заметим, что приведенный способ поискамаксимальных и минимальных путей крайненеэффективен, так как он предполагает просмотрвсех возможных путей и потому не подходит длябольших графов из-за своей высокой временнойсложности. В искусственном интеллекте задачапоиска пути возникает довольно часто. В главах 11и 12 мы изучим более сложные методы нахожденияоптимальных путей.

9. 5. 3. Построение остовного дерева

Граф называется связным, если между любымидвумя его вершинами существует путь. Пусть G = (V, Е) - связный граф с множествомвершин V и множеством ребep Е. Остовноедерево графа G - это связный граф Т = ( V, Е'), где Е' - подмножество Е такое, что

(1) Т - связный граф,

(2) в Т нет циклов.

Выполнение этих двух условий гарантирует то,что Т - дерево. Для графа, изображенного в левойчасти рис. 9.18, существует три остовных дерева,соответствующих следующим трем спискам ребер:

Дер1 = [а-b, b-c, c-d]

Дер2 = [а-b, b-d, d-с]

Дер3 = [а-b, b-d, b-c]

Здесь каждый терм вида X-Y обозначает ребро,соединяющее вершины Х и Y. В качестве корня можновзять любую из вершин, указанных в списке.Остовные деревья представляют интерес, напримерв задачах проектирования сетей связи, посколькуони позволяют, имея минимальное число линий,установить связь между любыми двумя узлами,соответствующими вершинам графа.

Определим процедуру

остдерево( G, Т)

где Т - остовное дерево графа G. Будем предполагать, что G - связный граф.Можно представить себе алгоритмический процесспостроения остовного дерева следующим образом.Начать с пустого множества ребер и постепеннодобавлять новые ребра, постоянно следя за тем,чтобы не образовывались циклы. Продолжать этотпроцесс до тех пор, пока не обнаружится, чтонельзя присоединить ни одного ребра, посколькулюбое новое ребро порождает цикл. Полученноемножество ребер будет остовным деревом.Отсутствие циклов можно обеспечить, еслипридерживаться следующего простого правила:ребро присоединяется к дереву только в томслучае, когда одна из его вершин уже содержится встроящемся дереве, а другая пока еще не включенав него. Программа, реализующая эту идею, показанана рис. 9.22. Основное отношение, используемое вэтой программе, - это

расширить( Дер1, Дер,G)

Здесь все три аргумента - множества ребер. G-

% Построение остовного дереваграфа

% Деревья и графы представлены списками

% своих ребер, например:

% Граф = [а-b,b-с, b-d, c-d]

остдерево( Граф,Дер) :- % Дер - остовное деревоГраф'а

принадлежит( Ребро, Граф),

расширить( [Ребро], Дер, Граф).

расширить( Дер1, Дер,Граф) :-

добребро( Дер1, Дер2, Граф),

расширить( Дер2, Дер, Граф).

расширить( Дер, Дер,Граф) :-

not добребро( Дер, _, Граф).

% Добавление любого ребра приводит к циклу

добребро( Дер, [А-В |Дер], Граф) :-

смеж( А, В, Граф), % А и В - смежные вершины

вершина( А, Дер). % А содержится в Дер

не вершина( В, Дер). % А-В не порождает цикла

смеж( А, В, Граф) :-

принадлежит ( А-В, Граф);

принадлежит ( В-А, Граф).

вершина( А, Граф) :- % А содержится в графе, если

смеж( А, _, Граф). % А смежна какой-нибудь вершине

Pис. 9. 22. Построениеостовного дерева: алгоритмический подход.

Предполагается, что Граф - связныйграф.

связный граф; Дер1 и Дер - дваподмножества G, являющиеся деревьями. Дер- остовное дерево графа G, полученноедобавлением некоторого (может быть пустого)множества ребер из G к Дер1.Можно сказать, что "Дер1 расширено до Дер".

Интересно, что можно написать программупостроения остовного дерева совершенно другим,полностью декларативным способом, простоформулируя на Прологе некоторые математическиеопределения. Допустим, что как графы, так идеревья задаются списками своих ребер, как впрограмме рис. 9.22. Нам понадобятся следующиеопределения:

(1) Т является остовнымдеревом графа G, если

Т - это подмножество графа G и

Т - дерево и

Т "накрывает" G, т.е. каждая вершина из G содержится также в Т.

(2) Множество ребер Т естьдерево, если

Т - связный граф и

Т не содержит циклов.

Эти определения можно сформулировать наПрологе (с использованием нашей программы путьиз предыдущего раздела) так, как показано на рис.9.23. Следует, однако, заметить, что эта программа втаком ее виде не представляет практическогоинтереса из-за своей неэффективности.

% Построение остовного дерева

% Графы и деревья представлены списками ребер.

остдерево( Граф,Дер) :-

подмнож( Граф, Дер),

дерево( Дер),

накрывает( Дер, Граф).

дерево( Дер) :-

связи( Дер),

not имеетцикл( Дер).

связи( Дер) :-

not ( вершина( А, Дер), вершина( В, Дер),

not путь( А, А, Дер, _ ) ).

имеетцикл( Дер) :-

смеж( А, В, Дер),

путь( А, В, Дер, [А, X, Y | _ ). % Длина пути > 1

накрывает( Дер,Граф) :-

not ( вершина( А, Граф), not вершина( А, Дер) ).

подмнож( [ ], [ ]).

подмнож( [ Х | L], S) :-

подмнож( L, L1),

( S = L1; S = [ Х | L1] ).

Рис. 9. 23. Построениеостовного дерева: "декларативный подход".

Отношения вершина и смежсм. на рис. 9. 22.

Упражнение

9. 15. Рассмотрите остовныедеревья в случае, когда каждому ребру графаприписана его стоимость. Пусть стоимостьостовного дерева определена как суммастоимостей составляющих его ребер. Напишитепрограмму построения для заданного графа егоостовного дерева минимальной стоимости.

Резюме

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

Списки:

варианты представления списков

сортировка списков:

сортировка методом "пузырька"

сортировка со вставками

быстрая сортировка

эффективность этих процедур

Представление множеств двоичными деревьями и двоичными справочниками:

поиск элемента в дереве

добавление элемента

удаление элемента

добавление в качестве листа или корня

сбалансированность деревьев и его связь с

эффективностью этих операций

отображение деревьев

Графы:

представление графов

поиск пути в графе

построение остовного дерева

Литература

В этой главе мы занимались такими важнымитемами, как сортировка и работа со структурамиданных для представления множеств. Общееописание структур данных, а также алгоритмов,запрограммированных в данной главе, можно найти,например, в Aho, Hopcroft and Ullman (1974, 1983) или Baase (1978). Влитературе рассматривается также поведение этихалгоритмов, особенно их временная сложность.Хороший и краткий обзор соответствующихалгоритмов и результатов их математическогоанализа можно найти в Gonnet (1984).

Прологовская программа для внесения новогоэлемента на произвольный уровень дерева (раздел9.3) была впервые показана автору М. Ван Эмденом(при личном общении).

Aho А. V., Hopcroft J. Е. and Ullman J. D. (1974). The Design and Analysis ofComputer Algorithms. Addison-Wesley. [Имеется перевод: Ахо А.,Хопкрофт Дж. Построение и анализ вычислительныхалгоритмов. Пер. с англ. - М-: Мир, 1979.]

Aho А. V., Hopcroft J. Е. and Ullman J. D. (1983). Data Structures andAlgorithms. Addison-Wesley.

Baase S. (1978). Computer Algorithms. Addison-Wesley.

Gonnet G. H. (1984). Handbook of Algorithms and Data Structures.Addison-Wesley.

Назад | Содержание| Вперёд

Оглавление