Доказательство 1

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

Алгоритм Прима (ближайшего соседа)

1) Строим граф - берем ребро графа , минимального веса;

2) построили. Строим . Среди ребер, соединяющих вершины дерева с вершинами графа , и не входяшие в , выбираем ребро минимального веса.

Для данного алгоритма также справедлива вышеприведенная теорема.

Доказательство 2

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

Пример

1

(2) (3) (1)

2 3 7

(5) (4) (6) (1)

8 4

(5) 5

Построим для данного графа остов минимальной стоимости.

Алгоритм Краскала Алгоритм Прима

1. (1, 5) - 1 1. (1, 5) - 1

2. (3, 5) - 1 2. (1, 2) – 2

3. (1, 2) – 2 3. (7, 5) – 2

4. (7, 5) – 2 4. (1, 3) – 3

(1, 3) брать нельзя, так как получим цикл (1, 3, 5, 7, 1)

5. (2, 4) – 4 5. (2, 4) – 4

6. (2, 8) – 5 6. (4, 6) – 5

7. (4, 6) – 5 7. (2, 8) – 5

Суммарная стоимость равна 20 Суммарная стоимость равна 20