Минимальный остов графа получается алгоритмом Прима

Question

мне нужна помощь по проблеме алгоритма А Прима:

Пусть Т минимальное покрывающее дерево графа G, полученный с помощью алгоритма Прима. Пусть Gnew - граф, полученный добавлением в G новой вершины и некоторых ребер с весами, соединяющих новую вершину с некоторыми вершинами из G. Можно ли построить минимальное остовное дерево Gnew, добавив одно из новых ребер к T? Если вы ответите «да», объясните, как; если нет, объясните, почему.

Спасибо заранее!

Answer 1

Можно ли построить минимальное остовное дерево Gnew, добавив один из новых ребер к T?

Нет. Не в общем. Предположим T была сформирована с учетом verteices того v1,v2,...,vn-1

Пусть vn быть новая вершина и (v1,vn) быть взвешенное ребро (v1 ​​является корнем Т), если вес (v1,vn) меньше, чем вес (v1,v2) в Т, это больше не будет MST.

Answer 2

не во всех случаях мы можем добавить новый ребро в T, это зависит от веса новых ребер, потому что иногда старый MST (T) изменяется, если новый вес ребер меньше другого веса на графике