Алгоритм Прима. Построить транспортную сеть с минимальными затратами. Бесплатный доступ к решению задач

Реферат.Справочник
Решенные задачи по высшей математике
Алгоритм Прима. Построить транспортную сеть с минимальными затратами

Алгоритм Прима. Построить транспортную сеть с минимальными затратами .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Алгоритм Прима. Построить транспортную сеть с минимальными затратами.

Решение

Потяни, чтобы посмотреть

Реализуем алгоритм Прима.
Находим ребро минимального веса V1, V6=1.
Вводим эти вершины в множество V*=V1, V6.
Выбираем ребро минимального веса, исходящее из вершин множества V*: V1, V2=2.
Добавляем V2 в множество V*: V*=V1, V2, V6.
Выбираем ребро минимального веса, смежное с вершинами множества V*: V6, V7=3.
Добавляем V7 в множество V*: V*=V1, V2, V6, V7.
Выбираем ребро минимального веса, смежное с вершинами множества V*: V3, V7=4.
Добавляем V3 в множество V*: V*=V1, V2, V3, V6, V7.
Выбираем ребро минимального веса, смежное с вершинами множества V*: V3, V9=4.
Добавляем V9 в множество V*: V*=V1, V2, V3, V6, V7, V9.
Выбираем ребро минимального веса, смежное с вершинами множества V*: V6, V10=5.
Добавляем V10 в множество V*: V*=V1, V2, V3, V6, V7, V9, V10.
Выбираем ребро минимального веса, смежное с вершинами множества V*: V3, V4=6.
Добавляем V4 в множество V*: V*=V1, V2, V3, V4, V6, V7, V9, V10.
Выбираем два ребра минимального веса, смежное с вершинами множества V*: V2, V5=7 и V8, V9=7.
Добавляем V8 и V5 в множество V*: V*=V1, V2, V3, V4, V5, V6, V7, V9, V8,V9,V10.
Так как неохваченных вершин не осталось, то минимальное остовное дерево построено.
Длина остовного дерева равна L=1+2+3+4+4+5+6+7+7=39.

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу