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

ШАГ 1. Вначале текущее множество вершин V_Т и рёбер X_Т искомого минимального остовного дерева Т = (V_Т , X_Т) устанавливают пустыми: V_Т := Ø, X_Т := Ø.

ШАГ 2. В цикле по всем ребрам из X \ X_Т , добавление которых к уже имеющемуся множеству X_Т не вызовет появление цикла в текущем Т, выбирают ребро минимального веса X¢ = (V¢ , V¢¢) . Его добавляют к уже имеющемуся множеству X_Т. В качестве нового множества вершин принимают V_Т È { V¢ , V¢¢ }.

ШАГ 3. Проверка окончания цикла: V_Т = V ― все вершины исходного графа G = (V, X, D)исчерпаны. Если выполняется строгое включение V_Т Ì V, то переход на ШАГ 2.

Справедлива

Теорема 1.1.Алгоритм Прима всегда находит во взвешенном графе (псевдографе) остовное дерево минимального веса.

В случае определения во взвешенном графе (псевдографе) остовного дерева с максимальным суммарным весов ребер, в алгоритме Прима на ШАГЕ 2 выбирают ребро максимального веса.

Задачи

1. Доказать, что в любом дереве Т_n число рёбер равно n -1.

2. Доказать, что любой лес W_n,k имеет число рёбер n - k.

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

4. Cвязный граф имеет один цикл длины m. Сколькими способами можно выделить в нем остовное дерево?

5. Доказать, что в любом дереве Т_n , имеющем хотя бы одно ребро, число висячих вершин не менее 2.