11. Остов в графе. Жадный алгоритмы и алгоритм Прима. Их сравнения
Остовом графа G называется его частичный граф типа дерево.
Таким образом, остов выделяется из графа G удалением  из него ребер до тех пор, пока он не станет графом типа дерево, включающим все вершины.

Так, на рис. 3.7 приведен граф, в котором толстыми линиями выделен один из его остовов. В графе может быть несколько различных остовов.

Если ребра графа взвешены, то возникает задача выделения остова с минимальной или максимальной оценкой.

Семантика задачи. Предположим, что вершинам графа сопоставлены полюса схемы, на которые необходимо подать питание, а ребрам - разрешенные связи для цепи питания. Тогда  любой из остовов будет определять вариант цепи питания.

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

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

Рассмотрим два алгоритма решения задачи: жадный алгоритм и алгоритм Прима.

Жадный алгоритм.

Выбирается ребро, имеющее минимальный вес среди всех рёбер, и  включается в остов. Из оставшихся ребер выбирается  снова то, которое имеет минимальный вес, и включается в остов, если при этом не образуются циклы. Процесс продолжается до тех пор, пока все вершины не будут включены в остов.

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

Поиск по этому алгоритму в графе на рис.3.7 приведет к решению, которое представим в виде последовательности просмотренных ребер: (1,4), (3,5), (1,2), [(2,4)], (2,3), (5,7), [(2,5)], [(4,5)], [(4,7)], (4,8), [(5,8)], [(7,8)], (3,6). В квадратные скобки заключены те ребра, которые не включены в остов из-за появления циклов.

Алгоритм Прима.

1. Включим  любую вершину в остов.

2. Рассмотрим все ребра, исходящие из вершин, включенных в остов к оставшимся вершинам, и из них выберем ребро с минимальным весом. Его концевую вершину включим в остов. Повторяем этот пункт, пока не все вершины включены в остов.

В этом алгоритме не нужно следить за образованием циклов. Алгоритм начинает работу с произвольно выбранной вершины. Кроме того, на каждом шаге просматривается только одна строка матрицы смежности.

Задача. Докажите, что независимо от выбора начальной вершины получается минимальное решение.

Если для графа на рис 3.7 алгоритм начать с вершины 7 , то последовательность действий будет такой:

Пункт 1. Вершину 7 отнесем к остову.

Пункт 2. Оценим ребра от вершины 7 к 4, 5 и 8. Выберем ребро с минимальным весом (7,5) и вершину 5 отнесем к остову.

Пункт 2. Для вершин 5, 7 рассмотрим ребра в вершины 1, 2, 3, 6, 8, 4 и по минимальной стоимости ребра отнесем вершину 3 к остову.

Пункт 2. Из вершин 5, 7, 3 ребра идут к вершинам 1, 2, 4, 6, 8. По наименьшему из этих ребер в остов отнесем вершину  2.

Пункт 2. Для вершин 5, 7, 3,2 рассматриваем ребра в вершины 1, 4, 6, 8.

По минимальному ребру отнесем к остову вершину 1.

Пункт 2. Для вершин 5, 7, 3, 2, 1 по минимальному исходящему из них ребру выберем  вершину 4.

Пункт 2. Для вершин остова 1, 2, 3, 4, 5, 7 по минимальному исходящему из них ребру выделим вершину 6.

Пункт 2. Для вершины 8 определим связывающее ее ребро с вершиной или 4, или 7, или 5.

Решение построено.