Читаем Prolog полностью

        Дер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.

Упражнение

Перейти на страницу:

Похожие книги

C++ Primer Plus
C++ Primer Plus

C++ Primer Plus is a carefully crafted, complete tutorial on one of the most significant and widely used programming languages today. An accessible and easy-to-use self-study guide, this book is appropriate for both serious students of programming as well as developers already proficient in other languages.The sixth edition of C++ Primer Plus has been updated and expanded to cover the latest developments in C++, including a detailed look at the new C++11 standard.Author and educator Stephen Prata has created an introduction to C++ that is instructive, clear, and insightful. Fundamental programming concepts are explained along with details of the C++ language. Many short, practical examples illustrate just one or two concepts at a time, encouraging readers to master new topics by immediately putting them to use.Review questions and programming exercises at the end of each chapter help readers zero in on the most critical information and digest the most difficult concepts.In C++ Primer Plus, you'll find depth, breadth, and a variety of teaching techniques and tools to enhance your learning:• A new detailed chapter on the changes and additional capabilities introduced in the C++11 standard• Complete, integrated discussion of both basic C language and additional C++ features• Clear guidance about when and why to use a feature• Hands-on learning with concise and simple examples that develop your understanding a concept or two at a time• Hundreds of practical sample programs• Review questions and programming exercises at the end of each chapter to test your understanding• Coverage of generic C++ gives you the greatest possible flexibility• Teaches the ISO standard, including discussions of templates, the Standard Template Library, the string class, exceptions, RTTI, and namespaces

Стивен Прата

Программирование, программы, базы данных
1001 совет по обустройству компьютера
1001 совет по обустройству компьютера

В книге собраны и обобщены советы по решению различных проблем, которые рано или поздно возникают при эксплуатации как экономичных нетбуков, так и современных настольных моделей. Все приведенные рецепты опробованы на практике и разбиты по темам: аппаратные средства персональных компьютеров, компьютерные сети и подключение к Интернету, установка, настройка и ремонт ОС Windows, работа в Интернете, защита от вирусов. Рассмотрены не только готовые решения внезапно возникающих проблем, но и ответы на многие вопросы, которые возникают еще до покупки компьютера. Приведен необходимый минимум технических сведений, позволяющий принять осознанное решение.Компакт-диск прилагается только к печатному изданию книги.

Юрий Всеволодович Ревич

Программирование, программы, базы данных / Интернет / Компьютерное «железо» / ОС и Сети / Программное обеспечение / Книги по IT
3ds Max 2008
3ds Max 2008

Одни уверены, что нет лучшего способа обучения 3ds Мах, чем прочитать хорошую книгу. Другие склоняются к тому, что эффективнее учиться у преподавателя, который показывает, что и как нужно делать. Данное издание объединяет оба подхода. Его цель – сделать освоение 3ds Мах 2008 максимально быстрым и результативным. Часто после изучения книги у читателя возникают вопросы, почему не получился тот или иной пример. Видеокурс – это гарантия, что такие вопросы не возникнут: ведь автор не только рассказывает, но и показывает, как нужно работать в 3ds Мах.В отличие от большинства интерактивных курсов, где работа в 3ds Мах иллюстрируется на кубиках-шариках, данный видеокурс полностью практический. Все приемы работы с инструментами 3ds Мах 2008 показаны на конкретных примерах, благодаря чему после просмотра курса читатель сможет самостоятельно выполнять даже сложные проекты.

Владимир Антонович Верстак , Владимир Верстак

Программирование, программы, базы данных / Программное обеспечение / Книги по IT