Имеется симметричная матрица взвешенных расстояний M(6,6), элементы mij которой заданы так: mij = 3 +3×i×j при i≠j, mij = ∞ при i=j, Используя алгоритм Прима, определить древовидную связную сеть, имеющую наименьшую суммарную внешнюю длину (в качестве ответа привести матрицу результатов расчёта структуры).

Для решения данной задачи сначала составим матрицу расстояний M(6,6):

M = [[inf, 6, 9, 12, 15, 18], [6, inf, 12, 18, 24, 30], [9, 12, inf, 24, 36, 48], [12, 18, 24, inf, 60, 72], [15, 24, 36, 60, inf, 90], [18, 30, 48, 72, 90, inf]]

Теперь применим алгоритм Прима для построения древовидной связной сети с наименьшей суммарной внешней длиной. Начнем с вершины 1.

1. Добавляем ребро (1, 2) длиной 6
2. Добавляем ребро (2, 3) длиной 12
3. Добавляем ребро (3, 4) длиной 24
4. Добавляем ребро (4, 5) длиной 60
5. Добавляем ребро (5, 6) длиной 90

Итоговая матрица результатов расчета структуры будет иметь вид:

[[inf, 6, 0, 0, 0, 0], [6, inf, 12, 0, 0, 0], [0, 12, inf, 24, 0, 0], [0, 0, 24, inf, 60, 0], [0, 0, 0, 60, inf, 90], [0, 0, 0, 0, 90, inf]]

Таким образом, древовидная связная сеть с наименьшей суммарной внешней длиной будет иметь структуру, описанную выше.