У меня есть взвешенный ненаправленный полный график. Я хочу создать из него минимальный Звездный лес, общая сумма весов ребер которого должна быть минимальной. Звездный граф - это особый тип графа, в котором вершины m-1 имеют степень 1, а одна вершина имеет степень m - 1. Другими словами, я ищу минимальный остовный лес полного графа, в котором каждое дерево в лесу является звездный график. Дело в том, что у меня есть ограничение, что размер каждого звездного графа должен быть не менее K .
. , Заранее спасибо.