Нахождение MST такого, что конкретная вершина имеет минимальную степень

Во-первых, обратите внимание, что алгоритм Крускала можно применить к любому взвешенному графу, независимо от того, связан он или нет. Как правило, это приводит к созданию минимального связующего леса (MSF) с одним MST для каждого подключенного компонента. Чтобы доказать, что ваша модификация алгоритма Крускала успешно находит MST, для которого v имеет минимальную степень, помогает доказать несколько более сильный результат: если вы примените свой алгоритм к возможно несвязному графу, то ему удастся найти MSF, где степень v свернуто.

Доказательство проводится индукцией по числу k различных весов.

Базовый случай (k = 1). В этом случае весами можно пренебречь, и мы пытаемся найти остовный лес, в котором степень v минимальна. В этом случае ваш алгоритм можно описать следующим образом: выбирать ребра как можно дольше в соответствии со следующими двумя правилами:

1) Ни одно выбранное ребро не образует цикл с ранее выбранными ребрами

2) Ребро, включающее v, не выбирается, если любое ребро, не включающее v, не нарушает правило 1.

Пусть G' обозначает граф, из которого v и все инцидентные ребра были удалены из G. Легко видеть, что алгоритм в этом частном случае работает следующим образом. Он начинается с создания связующего леса для G'. Затем он берет те деревья в лесу, которые содержатся в v's компоненте связности в исходном графе G, и соединяет каждый компонент с v одним ребром. Поскольку компоненты, соединенные с v на втором этапе, не могут быть связаны друг с другом никаким другим образом (поскольку, если бы существовало какое-либо соединительное ребро, не включающее v, оно было бы выбрано по правилу 2), легко видеть, что степень v равна минимальный.

Индуктивный случай: предположим, что результат верен для k и G является взвешенным графом с k+1 различными весами, а v является указанной вершиной в G. Отсортируйте различные веса в порядке возрастания (так, чтобы вес k+1 был самым длинным из различных весов — скажем, w_{k+1}). Пусть G' будет подграфом G с тем же набором вершин, но с удаленными всеми ребрами веса w_{k+1}. Поскольку ребра сортируются в порядке возрастания веса, обратите внимание, что модифицированный алгоритм Крускала в действительности начинается с применения самого себя к G'. Таким образом, по предположению индукции до рассмотрения ребер веса w_{k+1} алгоритму удалось построить MSF F' из G', для которого минимизируется степень d' из v в G'.

В качестве последнего шага модифицированный алгоритм Крускала, примененный к общему графу G, объединит некоторые деревья в F' вместе, добавив ребра веса w_{k+1}. Один из способов осмыслить последний шаг — представить F' как граф, в котором два дерева соединены ровно тогда, когда существует ребро веса w_{k+1} от некоторого узла в первом дереве к некоторому узлу во втором дереве. У нас есть (почти) базовый случай с F'. Модифицированный Kruskal будет добавлять ребро веса w_{k+1} до тех пор, пока он больше не сможет этого делать, и не будет добавлять ребро, соединяющееся с v, если нет другого способа соединиться с деревьями в F', которые необходимо соединить, чтобы получить остовный лес. для исходного графика G.

Конечная степень v в результирующем MSF равна d = d'+d", где d" — количество ребер веса w_{k+1}, добавленных на последнем шаге. Ни d', ни d" нельзя сделать меньше, отсюда следует, что d нельзя сделать меньше (поскольку степень v в любом остовном лесу можно записать как сумму количества ребер, вес которых меньше w_{k+1} приходящих в v и количество ребер веса w_{k+1} входящих в v).

КЭД.

В этом все еще есть элемент махания руками, особенно на последнем шаге, но Stack Overflow не является рецензируемым журналом. В любом случае, общая логика должна быть достаточно ясной.

И последнее замечание: кажется довольно ясным, что алгоритм Прима можно аналогичным образом модифицировать для этой задачи. Вы смотрели на это?