38. Задача о минимальном остовном дереве. Алгоритмы Прима и Краскала.

Пусть дан граф Gс множ (N,U)-связный. Каждому ребру поставлено в соответствии неотрицательное число cij, которое называется весом ребра. Графы такого типа называются взвешаными сетями.

Необходимо найти минимальное по весу остовное дерево.В данном случае под весом понимают сумму весов его рёбер.

Теорема. Пусть G(N,U)-связный взвешаный граф, взвешаны рёбра с матрицей весов cij. D1(N1,U1),D2(N2,U2),…,Dk(Nk,Uk)-остовный лес.

N=∪Ni Ni≠∩j=i≠j

(p,l)-ребро исходного графа такое, что pЄN1, l∉N1. Среди подобных рёбер (p,l) имеет минимальный вес. Тогда среди всех остовных деревьев D, включавших {Di} в качестве остовного леса, найдётся дерево минимального веса, содержащее ребро (p,l).

Доказательство. Предположим противное: описаное в теореме остовное дерево Т не содержит ребро (p,l). Добавим в дерево Т ребро (p,l). При этом новый граф Т’ имеет в точности 1 цикл с ребром (p,l). В этом цикле обязательно найдётся ребро (α,β) такое, что αЄD1, β∉D1. Возможны 2 случая:

1.Вес ребра (p,l) совпадает с весом ребра (α,β). В этом случае выбрасываем ребро (α,β) и тогда новый граф Т’’ совпадает с деревом, описанным в условии теоремы.

2. Если ребро (α,β)> веса ребра (p,l). Cα,β>cp,l. Тогда исходное дерево Т не является минимальным по весу. Противоречие получено. Теорема доказана.

Алгоритм Краскала-алгоритм решения задачи по минимальным остовных деревьев.

1.Среди все рёбер графа G находим ребро минимального веса, удаляем его из графа и заносим его в строящееся остовное дерево.

2.Если в строющемся дереве n-1 вершин, где n-колич вершин остовного дерева, то оптимальное ребро построено. Конец работы алгоритма. Иначе переходим на шаг 3.

3. Среди всех рёбер графа G таких, что добавление любого из них в строющееся дерево не приводит к появлению цикла. Выбираем ребро минимального веса. Удаляем его из цикла и заносим его в дерево. Переходим на шаг 2.

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

1.Выбираем произвольную вершину i. Среди всех рёбер, инцидентных этой вершине, выбирается ребро минимального веса, удаляется из графа и заносится в остовное дерево.

2. Если в дереве n-1 ребро, где n-количество вершин исходного графа, то оптимальное дерево построено. Конец работы алгоритма. Иначе переходим на шаг 3.

3.Среди всех рёбер графа G, таких, что в каждой из них инцидентна в точности одной вершине, вошедшей в строющееся дерево находим ребро минимального веса, удаляем его из графа и заносим его в строющееся дерево. Переходим на шаг 2.