3. Определить минимальное остовное дерево нагруженного графа:
C(G)=
| V{1} | V{2} | V{3} | V{4} | V{5} | V{6} | V{7} | |
|---|---|---|---|---|---|---|---|
| \cline { 2 - 9 }V{1} | ∞ | 42 | 36 | 17 | 6 | 8 | 28 |
| V{2} | 42 | ∞ | 3 | 24 | 38 | 25 | 30 |
| V{3} | 36 | 3 | ∞ | 39 | 11 | 33 | 8 |
| V{4} | 17 | 24 | 39 | ∞ | 4 | 19 | 8 |
| V{5} | 6 | 38 | 11 | 4 | ∞ | 5 | 10 |
| V{6} | 8 | 25 | 33 | 19 | 5 | ∞ | 17 |
| V{7} | 28 | 30 | 8 | 8 | 10 | 17 | ∞ |
Мы воспользуемся алгоритмом Прима для поиска минимального остовного дерева.
Шаг 1. Выбираем произвольную вершину, например V1.
Матрица весов: V1 V2 V3 V4 V5 V6 V7 V1 inf 42 36 17 6 8 28 V2 42 inf 3 24 38 25 30 V3 36 3 inf 39 11 33 8 V4 17 24 39 inf 4 19 8 V5 6 38 11 4 inf 5 10 V6 8 25 33 19 5 inf 17 V7 28 30 8 8 10 17 inf
Lets build MST.
Начинаем с V1: Вершина V1, минимальные рёбра: от V1 к V5 вес 6, к V6 вес 8, к V4 вес 17 и т.д. Минимальный ребро: V1-V5 (6). Добавляем ребро V1-V5 в МСТ. MST: {V1-V5}
Текущий набор вершин: {V1, V5}.
Теперь рассматриваем все ребра, ведущие из {V1, V5} к ...
Не нашел нужную задачу?