Алгоритм Краскала. Пусть дан полный граф. Ребрам приписаны штрафы

Пусть дан полный граф. Ребрам приписаны штрафы. На основе этого графа строят дерево, имеющее минимальный суммарный штраф.

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

.

Пример.

2 3 5 5

6

4 4 8 6

6

Жирными линиями выделено минимальное дерево

Теорема Кэли для раскрашенных деревьев.

Для n вершин существует n^n-2 различных помеченных деревьев.

Например, существует 16 различных деревьев с четырьмя вершинами.

1 2 3 4

4 3 2 1

4 вершины Þ 4^{4 - 2} = 16 различных помеченных деревьев

1 2 3

Дата добавления: 2014-01-06