Доброго времени суток. Извиняюсь за возможно корявую постановку задачи, но как могу..
Есть связанный неориентированный граф. Произвольным образом из этого графа выбирается n-ое количество вершин (n намного меньше изначального количества вершин в графе, если это имеет значение). Нужно получить из исходного графа подграф, который будет содержать все выбранные/указанные n вершин, также будет оставаться связанным, но число вершин из исходного графа, не входящих в n, но включаемых в подграф, для сохранения связанности, будет минимальным.
Наверняка такая задача уже имеет решение, подскажите, пожалуйста, куда копать? Если нет ссылки на описание, хотя бы просто название алгоритма.
Исключить из графа все вершины не входящие в выборку, заменив на ребра со сложенным весом. Т.е. допустим есть вершина А, ребра AB=1, AC=1, AD=2. Вершина и ребра заменяются на ребра: BC=2, BD=3, CD=3
Затем найти минимальное остовное дерево. Можно взять алгоритм Краскала, описание есть на вики: https://ru.wikipedia.org/wiki/Алгоритм_Краскала
Aniro контрпример:
по предложенному алгоритму получается
вершины 0-4 вес (4), 0-6(4), 4-6(4), 4-6(3)
минимальное остовное дерево [0-1-2-3-4-8-7-6] из 8 вершин, что, очевидно, неправильно, так как верный ответ будет [0-1-2-3-4, 2-5-6], где 7 вершин
но поддерживаю в том, что в ответе должно быть именно дерево, и оно будет минимально остовным.
Я думал веса ребер проставить проходом в глубину от каждой вершины до каждой, по +1, но все равно в таком случае остается неопределенность с одинаковыми итоговыми весами путей между нужными парами вершин
Простой
