Найти диаграмму минимального веса, которая охватывает заданное минимальное остовное дерево

Question

Позвольте T = (V, E) быть деревом |V| вершин и |E| = |V-1| краями с известными расходами. Мы хотим построить минимальный вес График G = (V, E '), который охватывает T как уникальное минимальное остовное дерево.

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

Минимальный вес полный граф G, которая охватывает T в качестве уникального MST является следующее:

---

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

1) Найдите разрез графика, который содержит самый тяжелый край MST веса w_max и никаких других краев MST. Все остальные края должны быть w_max + 1. Следующие фотографии иллюстрирует мою мысль:

Edges (1--2), (1--4), (4--5), (2--3) и (2--5) включены в этот разрез C. Единственный край, который включен в MST, - это край (2--3), и это самый тяжелый край в MST, с w=56. Таким образом, все остальные края должны иметь w=57. Доказательство. Предположим противное; мы можем заменить (2--3) другим ребром и по-прежнему поддерживать дерево. Теперь вес дерева легче, поэтому (2--3) не принадлежит к MST. Противоречие.

2) Повторите для всех других кромок e_i из MST, вес w_i, в порядке уменьшения веса. Возьмите разрез, который включает только e_i и никаких других краев MST. Любой неизвестный не-MST край этого разреза должен иметь вес w_i + 1.

---

Вопросы:

1) Является ли выше алгоритм правильно? Согласно собственности Cut, это должно быть.

2) Могу ли я сделать это более эффективно? У меня нет алгоритма поиска разрезов на моей голове, но я не считаю, что этот подход может быть эффективным.

---

редактировать: Другой подход, который я имел в своем уме был подход, основанный на алгоритме Крускала:

1) Использование Союз-Find, я перебирать все ребра MST, по возрастанию стоимости, и унифицировать соответствующие вершины под одной и той же компонентой.

2) На каждом шаге два разных компонента унифицированы через край стоимости w. Любые другие ребра, которые образуют цикл в одном и том же (новом) компоненте, должны иметь стоимость w+1.

Answer 1

Отвечая на мой собственный вопрос

Вот эффективный ответ, который я придумал, следуя также обратную связь от @sasha. Предположим, что мы хотим рассчитать общий вес полного графа G, т. Е.

Пусть T = (V, E) является деревом | V | вершины и | E | = | V | -1 ребер с известными весами. Рассчитайте общий вес w_total полного веса с минимальным весом G = (V, E '), который охватывает T как свое единственное минимальное остовное дерево. NB: вес кромки - натуральные числа.

Алгоритм:

1. Инициализировать Union-Find с |V| компонентами одноплодной.
2. Сортировка всех краев T по возрастанию. Время работы: O (| V | * log | V |).
3. Итерация следующего края e = (v1,v2) от T. Добавьте свой вес w_e в w_total.
4. Найти v1 'с и v2' s компоненты в Юнион-Find: set1, set2, содержащие size1 и size2 вершины соответственно.
5. Эти компоненты будут унифицированы. Так как G - полный график, то будут добавлены края size1 × size2: один край - край MST e, все остальные должны быть более тяжелыми, чем e, так что алгоритм Kruskal будет игнорировать их. Таким образом, их минимальный вес должен быть не менее w_e + 1.
6. w_total += (size1 × size2 - 1) × (w_e + 1).
7. Унифицируйте два компонента set1 и set2.
8. Повторите с шага 2 для следующего края MST e.

Продолжительность спектакля: O (| V | * log | V |).

---

Если проблема становится: список подробно все ребра e = (v1, v2) полного графа и их вес w, мы просто должны сделать, между шагами 6 и 7:

for all vertices v1 in set1 
    for all vertices v2 in set2 
    create edge e = (v1, v2); ignore if edge is the MST edge 
    w_e = w_mst_edge + 1 

Таким образом, время работы О (| E | + | V | * log | V |) = O (| V |^2), так как | E | = | V | * (| V | -1)/2 ребер на полном графике G.