Восстанавливать минимальное остовное дерево за линейное время?
Если существует граф G с V вершинами и E ребрами, и я уже знаю его минимальное остовное дерево T из G, а затем, если некоторые ребра из E взяты и их веса увеличены, скажем, на 50, эти ребра могут или не могут быть в минимальном остовном дереве. Помня вышеупомянутый сценарий, есть ли способ восстановить новое минимальное остовное дерево за линейное время? примечание: количество ребер, вес которых был изменен, составляет всего 5.