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

Question

Я должен решить эту проблему:

Учитывая взвешенный связный неориентированный граф G = (V, E) и вершину и в V. описать алгоритм, который находит MST для G так что степень u минимальна; выход T алгоритма MST и для каждого другого минимальное остовное дерево T 'является степенью u в T, меньшей или равной , равной степени u в T'.

Я думал об этом алгоритме (после некоторого Googling я нашел это решение аналогичной задачи here):

• Временно удалить вершину и.
• Для каждого из полученных соединенных компонентов C1, ..., Cm обнаруживают MST, например, Алгоритм Крускала или Прима.
• Повторно добавьте вершину u и для каждого Ci добавьте самый дешевый край между 1 и Ci.

EDIT:

я понял, что этот алгоритм может получить неправильный MST (см @AndyG комментария), так что я думал о другом:

• пусть к минимальному приращение между каждые два веса в G и добавьте 0 < x < k к каждому смежному краю u. (например, если все веса являются натуральными числами, так что k = 1, а x - дробь).
• найти MST с использованием алгоритма Крускала.

Это решение основано на том факте, что алгоритм Крускала итерации края упорядоченные по весу, так что разница между всеми МСЦ из G является каждое ребро был выбран из числа всех ребер одного и того же веса. Поэтому, если мы увеличим степень смежных ребер u, алгоритм выберет остальные ребра в той же степени, а не смежные по u, если это ребро не будет необходимо для MST, а степень u будет минимальной во всех MSTs G.

Я до сих пор не знаю, работает ли это и как доказать правильность этого алгоритма.

Буду признателен за любую помощь.

Answer 1

Резюмируя предложенный алгоритм [с ужесточили требования по эпсилон (которые вы называемых х)]:

• Pick крошечное эпсилон (например, что эпсилон * град (и) меньше г, наименьшее не -размерная разница в весе между любыми парами подграфов). В случае, когда все исходные веса являются натуральными числами, достаточно epsilon = 1/(deg (u) +1).
• Добавить эпсилон к весам всех ребер, падающих на u
• Найти минимальное остовное дерево.

Мы докажем, что эта процедура находит MST исходного графа, который минимизирует число ребер, инцидентных u.

Пусть W - вес любого минимального связующего дерева в исходном графе.

Сначала мы покажем, что каждый MST нового графика является MST исходного графа. Любой не-MST в исходном графе должен иметь вес не менее W + d. Любой MST в новом графе должен иметь вес не более W + deg (u) * epsilon (так как любой MST в исходном графе имеет не более этого веса на новом графике). Поскольку мы выбрали epsilon таким образом, что deg (u) * epsilon < d, мы заключаем, что любой MST в новом графе также является MST в исходном графе.

Во-вторых, мы покажем, что MST нового графика является MST исходного графа, который минимизирует число ребер, инцидентных u. MST, T, исходного графа имеет вес W + k * epsilon в новом графе, где k - число ребер T, инцидентных u. Мы уже показали, что каждый MST нового графика также является MST исходного графа. Следовательно, MST нового графа является MST исходного графа, который минимизирует k (число ребер, инцидентных u).