Программирование на языке ПРОЛОГ для искуственного интеллекта




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


Граф называется связным, если между любыми двумя его вершинами существует путь. Пусть  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  - связный граф. Можно представить себе алгоритмический процесс построения остовного дерева следующим образом. Начать с пустого множества ребер и постепенно добавлять новые ребра, постоянно следя за тем, чтобы не образовывались циклы. Продолжать этот процесс до тех пор, пока не обнаружится, что нельзя присоединить ни одного ребра, поскольку любое новое ребро порождает цикл. Полученное множество ребер будет остовным деревом. Отсутствие циклов можно обеспечить, если придерживаться следующего простого правила: ребро присоединяется к дереву только в том случае, когда одна из его вершин уже содержится в строящемся дереве, а другая пока еще не включена в него.


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