простой способ узнать, улучшится ли MST, если стоимость конкретного края уменьшится?

G — неориентированный связный граф с положительными затратами на всех ребрах. Дано ребро e, стоимость которого строго больше 10. Нам нужно ответить, улучшится ли стоимость MST, если стоимость e уменьшится на 10.

Я знаю решение, которое включает в себя создание нового графа только с ребрами с cost<cost(e)-10. Что не так с этим гораздо более простым решением: возьмите одну из вершин e v. Найдите минимальную границу затрат, связанную с v. Теперь уменьшите стоимость e и снова найдите минимальное стоимостное преимущество, связанное с v. Если было изменение, это означает, что prim найдет лучший MST, и стоимость улучшится. Если нет, это означает, что prim найдет тот же MST, и стоимость останется прежней.

Что не так с этой логикой?

связанные с Обновить минимальное остовное дерево с модификацией края


graph-algorithm prims-algorithm minimum-spanning-tree kruskals-algorithm
person ihadanny    schedule 02.10.2020    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Я не думаю, что ваше решение является правильным.

Рассмотрим следующий граф G = (V, E), V = {a, b, c, d, e}, E = {ab, bc, cd, de, ae, bd} и соответствующие веса {5, 10 , 10, 5, 17}.

Запустив Крускала или Прима, мы обнаружим, что наш MST равен {ab, bc, cd, de}, а его вес равен 30.

Теперь давайте уменьшим вес ребра bd с 17 до 7 и снова рассмотрим ребра.

Запуск Prim или Kruskal с G' выведет MST, который весит 27 (на самом деле у нас есть 2 таких MST {ab, bd, de, cd} и {ab, bd, de, bc}).

Но если мы воспользуемся вашим алгоритмом, мы получим точно такое же дерево, потому что когда мы исследуем узлы b или d, ребро bd не будет самым легким ребром, примыкающим к любому из этих узлов.

person Daniel Shterenberg    schedule 02.10.2020

arrow_upward
1
arrow_downward

Пусть G = (V, E) будет графом.
Определение
1
где w(<u,v>) – это вес <u,v>.

Лемма 1
Пусть G — граф, v — вершина G, а e — ребро G, инцидентное v. Если w(e) = C(v), то e принадлежит некоторому MST из G.

Это правда, что если значение C(v) изменится, когда стоимость e уменьшится на 10, то стоимость MST улучшится, если стоимость e уменьшится на 10 по лемме 1.

Первая половина нормально. Давайте посмотрим на вторую часть.

Если нет, это означает, что prim найдет тот же MST, и стоимость останется прежней.

Общее объяснение
Вышеупомянутая цитата ложно подразумевает, что обратная лемма 1 верна (e принадлежит некоторой MST G, затем w(e) = C(v)), поскольку утверждается, что если мы уменьшим стоимость e на 10 и w(e) != C(v) тогда стоимость MST сохраняется, что означает, что e не принадлежит ни одному MST из G.

Короткое объяснение: контрпример
Давайте G = ({1, 2, 3, 4}, {<1, 2>, <1, 3>, <2, 4>, <3, 4>, <1, 4>}) с весовой функцией w(<1, 2>) = 1, w(<1, 3>) = 3, w(<2, 4>) = 3, w(<3, 4>) = 1, w(<1, 4>) = 12 и e = <1, 4>.

После уменьшения стоимости e мы знаем, что C(1) = C(4) = 1 != w(e). Предлагаемый алгоритм утверждает, что: prim найдет тот же MST, а стоимость останется прежней.

Проверим, уменьшается ли стоимость MST G при уменьшении стоимости e на 10:
стоимость MST до уменьшения стоимости e на 10: 5
стоимость MST после уменьшения стоимости e на 10: 4

Поскольку происходит снижение стоимости MST, то такое утверждение (приведенное) является ложным и предложенный алгоритм не работает.

Примечание. Алгоритм неверен независимо от того, какой алгоритм MST используется, поскольку контрдоказательство опирается только на свойства MST.

person Eloy Pérez Torres    schedule 07.10.2020