? Справочник по математике для экономистов - Глава: 11.9. матрицы графов

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

11.12. алгоритм построения деревьев

Пусть имеется некоторый граф G и каждому его ребру (х, у) поставлено в соответствие число т(х, у), которое называется его весом. Вес дерева определяется как сумма весов составляющих его ребер. Для графа G необходимо построить покрывающее дерево минимального веса.

Алгоритм построения минимального покрывающего дерева. Просматривают ребра графа G в порядке возрастания их весов. Если ребро включается в покрывающее дерево, то его окрашивают в голубой цвет, если не включается—в оранжевый. Ребра, включенные в дерево, образуют граф, состоящий из нескольких компонент. Если концевые вершины просматриваемого ребра принадлежат одной и той же компоненте, то ребро образует цикл с ребрами, ранее включенными в дерево. Такое ребро не включают в дерево. Если же концевые вершины не принадлежат одной компоненте, то ребро включают в дерево. Вершины одной связной компоненты составляют букет.

1. Берут любое ребро, не являющееся петлей. Окрашивают его в голубой цвет, а его концевые вершины включают в первый букет.

323

Выбирают неокрашенное ребро и окрашивают его:

а)       в оранжевый цвет, если концевые вершины ребра принадлежат одному и тому же букету;

б)       в голубой цвет, если:

концевые вершины не принадлежат ни одному из букетов (в этом случае вершины включают в новый букет);

концевые вершины принадлежат разным букетам (в этом случае эти букеты объединяют в один);

один конец ребра принадлежит некоторому букету, а второй не входит ни в один букет (в этом случае второй конец включают в тот же букет).

Заканчивают процедуру, если все вершины графа вошли в один букет. В противном случае переходят в шагу 2.

Число шагов при выполнении алгоритма конечно, так как оно не превышает числа ребер графа. Если голубые ребра не образуют покрывающего дерева, то у исходного графа его нет.

О Пример. В новом районе имеется шесть жилых массивов. Нужно соединить их между собой дорогами, стоимость прокладки которых была бы минимальна. В таблице приведена стоимость постройки дорог между каждой парой жилых массивов:

Рис. 11.22

Построено покрывающее дерево, вес которого равен 25 (рис. 11.22). •