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

Question

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

Будет ли модифицировать алгоритм Крускала так, чтобы при наличии нескольких ребер с одинаковым весом мы выбирали тот, который не касается 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 сводится к минимуму Однако этот подход не дает алгоритм полиномиального времени.