Предположим, что нам дано минимальное остовное дерево T данного графа G (с n вершинами и m ребрами) и новое ребро e = (u, v) веса w, которое мы добавим к G.Добавить новое к графу и найти новое связующее дерево
I) Проверьте, остается ли T MST или нет. II) Если нет, дайте эффективный алгоритм для нахождения минимального остовного дерева графа G + e.
Ваш текущий MST T содержит n-1 краев. Дополнение к графике нового ребра e = (u,v) с весом w создает точно один цикл C в графе T + e (T с краем e добавлено). Если новый вес кромки (w) меньше, чем вес самого высокого веса в этом цикле C, тогда вы можете создать меньший вес MST, заменив его более высоким весом e. В противном случае ваш текущий MST остается оптимальным.
Алгоритм в основном это:
P от u к v в Te* в P, который имеет максимальный вес w*w < w*?
T' = T - e* + e является MST для G + e, weight(T') = weight(T) - w* + wT' = T является MST из G + eЭто правда, но откуда вы знаете, что остальные грани в MST остаются в силе? – templatetypedef
@templatetypedef Доказательство правильности или сложности алгоритма выходит за рамки стека переполнения. –
Что ваш вопрос? Что вы пробовали? –
@WernerHenze Несмотря на то, что у вопроса, очевидно, нет попытки попробовать что-либо и почти наверняка домашнее задание, оно * довольно ясно, что вопрос - не до вопроса вопросительного знака. –
@WernerHenze, я уже видел этот вопрос в stackoverflow и получил те же ответы. Я сомневаюсь, что другие грани в MST остаются в силе, но Тимоти Шилдс объяснил ниже. Извините за неполное объяснение. –