Найдите остовное дерево наименьшей цены (ОДНЦ) графов G и H: G H G H

Найдите остовное дерево наименьшей цены (ОДНЦ) графов G и H:
G H
G H (Решение → 24361)

Найдите остовное дерево наименьшей цены (ОДНЦ) графов G и H: G H G H



Найдите остовное дерево наименьшей цены (ОДНЦ) графов G и H:
G H
G H (Решение → 24361)

Построим остовное дерево алгоритмом Прима, в котором поддерживается уже обработанная часть графа (минимального остовного дерева), постепенно расширяемая за счёт ближайших вершин. Таким образом, для нахождения минимального остовного дерева начинается с произвольной вершины и постепенно добавляются минимальные ребра, не образующие цикл, ближайшие к уже имеющимся. Для графа G построение начнем с вершины 1: Для графа H построение начнем с вершины 1: