Разделить неориентированный граф на несколько минимальных остовных деревьев.

Question

Я хочу разбить неориентированный граф на несколько минимальных остовных деревьев. Есть несколько специальных (root) узлов, с которых я хочу начать строить минимальное остовное дерево, и я знаю каждый вес между узлами.

Есть ли какой-нибудь алгоритм для решения этой проблемы? Если нет строгих методов, мне подходят любые приблизительные методы.

Я прилагаю два примера вывода. Я буду рад, если вы мне поможете. Спасибо.

Answer 1

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