Минимальное остовное дерево, которое минимизирует степень определенного узла

Question

Как мы можем найти минимальное остовное дерево, которое минимизирует степень узла v (среди всех минимальных остовных деревьев)?

Будет ли модифицировать алгоритм Kruskal таким образом, что если есть несколько ребер с одинаковым весом, мы выбираем тот, который не касается v, решает проблему?

Answer 1

Чтобы ответить на вопрос частично, модификация алгоритма Крускаля, как набросанная в вопросе, не решает проблему. Рассмотрим граф G=(V,E,w) где

V = {1,2,3}, 
E = {{1,2}, {2,3}, {3,1}}, 
w({1,2}) = 1, 
w({1,3}) = 1, 
w({2,3}) = 2 

и 1 является узел, степень в минимальном остове должно быть сведено к минимуму. Затем край установлен

S1={{1,2},{1,3}} 

составляет минимальный остов веса 2. Однако модифицированная версия алгоритма Крускаля без ограничения общности может выбрать край {1,2}, который приведет к запрету {1,3}, так что выбирается {2,3}. В общей сложности в выбранном крае установлен

S2={{1,2},{2,3}} 

узел 1 имеет меньшую степень, чем в S2, но общий вес S2 является 3, что означает, что он не является минимальным остовным деревом.

Кроме того, обратите внимание, что степень узла v, которая должна быть сведена к минимуму должно быть, по крайней мере 3, чтобы иметь возможность более чем одной окрестности v в минимальных остовных деревьев.

В исчерпывающем поиске выберите любую возможную окрестность v. Поскольку v имеет не более n соседей, их насчитывается не более 2^n таких районов. Используя алгоритм с помощью Prim, разложите каждый из них на связующее дерево, которое является минимальным по стоимости по отношению к содержанию выбранной окрестности v; во всех этих решениях, которые являются минимальными по стоимости, выберите тот, в котором степень v минимизирована. Однако подход не дает алгоритма полиномиального времени.