Доказать, что в связном взвешанном графе любой минимальный остов может быть получен применением алгоритма Прима при любом выборе начальной вершины

Дано: Связный взвешенный граф $G$.

Найти: Доказать, что любой минимальный остов графа $G$ может быть получен с помощью алгоритма Прима при любом выборе начальной вершины.

Решение:

Чтобы доказать это утверждение, воспользуемся методом от противного и свойствами минимальных остовов.

1. Определения:
   • Минимальный остов графа — это подмножество рёбер, которое соединяет все вершины графа, имеет минимальную сумму весов рёбер и не содержит циклов.
   • Алгоритм Прима строит остов, начиная с произвольной вершины и добавляя рёбра минимального веса, которые соединяют уже в...