Будет ли стандартный подход, основанный на Kruskal для MST, работать, если фиксируются некоторые ребра?

Question

Проблема: вам нужно найти минимальное связующее дерево графа (т. Е. Множество S ребер в указанном графе такое, что ребра в S вместе с соответствующими вершинами образуют дерево, кроме того, из всех таких множеств сумма стоимости всех ребер в S должна быть минимальной). Но есть улов. Вам задан начальный набор фиксированных ребер K таких, что K должен быть включен в S.

Другими словами, найдите некоторый MST графа с включенным исходным набором фиксированных ребер.

Мой подход: стандартный алгоритм Kruskal, но прежде чем что-либо еще соединить все вершины, как указано набором фиксированных ребер. То есть, если K = {1,2}, {4,5} применяю алгоритм Крускала, но вместо того, чтобы изначально иметь каждый узел в своем собственном индивидуальном наборе, вместо этого узлы 1 и 2 находятся в одном наборе, а узлы 4 и 5 находятся в одном наборе.

Вопрос: это работает? Есть ли доказательство того, что это всегда дает правильный результат? Если нет, может ли кто-нибудь предоставить встречный пример?

P.S. проблема только запрашивает поиск ONE MST. Не интересует их всех.

Answer 1

Да, это будет работать до тех пор, пока ваш исходный набор ребер не образует цикл.

Помните, что результирующее дерево может не быть минимальным по весу, поскольку исправленные вами ребра могут не быть частью любого MST на графике. Но вы получите самое легкое остовное дерево, которое удовлетворяет ограничению того, что эти фиксированные края являются частью дерева.

Как реализовать:

Для реализации этого, вы можете просто изменить реберный вес ребер, которые необходимо исправить. Просто выберите самый нижний крайний вес в вашем графике, скажем min_w, вычтите 1 из него и назначьте этот новый вес, т. Е. (min_w-1) к краям, которые необходимо исправить. Затем запустите Kruskal на этом графике.

Почему это работает:

Очевидно Крускал подберет все ребра, нужны (так как это самое легкое в настоящее время), прежде чем выбрать любой другой край на графике. Когда Крускаль заканчивает результирующее множество ребер, MST в G '(график, где вы изменили некоторые веса). Обратите внимание, что поскольку вы только изменили значения вашего фиксированного набора ребер, алгоритм никогда не сделал бы другого выбора на других ребрах (те, которые не являются частью вашего фиксированного набора).Если вы думаете о краях, которые Kruskal считает как отсортированный список ребер, то изменение значений ребер, которые нужно исправить, перемещает эти ребра в начало списка, но не меняет порядок остальных ребер в список по отношению друг к другу.

Примечание: Как вы можете заметить, придание легкого веса вашим краям в основном та же самая вещь, что и вы. Но я думаю, что немного легче понять, почему это работает. Пойдите с тем, что вы предпочитаете.

---

Я бы не рекомендовал Prim, поскольку этот алгоритм расширяет остова постепенно от текущего подключенного компонента (в начале одного, как правило, начинается с одного узла). Случай, когда вы присоединяетесь к более крупным компонентам (поскольку ваши фиксированные края могут быть не все в одном компоненте), необходимо будет обрабатывать отдельно - это может быть не сложно, но вам придется позаботиться об этом. OTOH с Kruskal вам не нужно ничего адаптировать, а просто немного манипулируйте своим графиком перед запуском обычного алгоритма.

Answer 2

Если я правильно понял вопрос, Prim's algorithm был бы более подходящим для этого, так как можно инициализировать подключенные компоненты точно такими ребрами, которые должны встречаться в полученном остовном дереве (плюс оставшиеся изолированные узлы) , Желательным краям не разрешается содержать цикл, в противном случае нет связующего дерева, включая их.

Это, как утверждается, может быть использовано, по-видимому, Kruskal's algorithm, поскольку в нем явно указано, что можно использовать для нахождения ребра, которое соединяет два леса минимально затратным образом.

Грубо говоря, поскольку леса данного графика образуют Matroid, жадный подход дает желаемый результат (а именно дерево минимальной по весу) независимо от independent set, с которого вы начинаете.