Как представить минимальное связующее дерево в ограничениях линейного программирования?

Question

Предположим, нам дан взвешенный граф G и остовное дерево T его. Мы хотим изменить веса ребер, чтобы T было минимальным остовным деревом и суммой всех | w_i - w'_i | быть минимальным, где w_i - вес ребра i_th, а w'_i - вес ребра i_th после его изменения.

Я думаю, что очевидно, что наша цель - минимизировать сумму | w_i - w'_i | для всех i и наших переменных w'_i, но я не могу найти, как представлять T, является минимальным связующим деревом в ограничениях.

Answer 1

Для каждого я такой, что я ^й край не в Т, для каждого J таким образом, что J ^й ребро лежит на уникальном пути в T от одной конечной точки I ^го края до другое, существует ограничение w _i '- w _j' ≥ 0.

Answer 2

Вы можете использовать модифицированную версию Prim's algorithm.

Этот алгоритм создает подключенный компонент в каждой точке, добавляя край с наименьшим весом от компонента к вершине вне компонента.

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

Вы можете изучить все потенциальные ребра (от компонента к внешнему компоненту) и вычислить минимальный вес. Затем вам нужно изменить ребро e от его первоначального веса до вычисленного минимального веса.

Затем вы можете добавить ребро e к компоненту и повторить, пока не вычислите минимальное связующее дерево, используя все исходные края остовного дерева.