Как постростроить подграф?

Доброго времени суток. Извиняюсь за возможно корявую постановку задачи, но как могу..

Есть связанный неориентированный граф. Произвольным образом из этого графа выбирается n-ое количество вершин (n намного меньше изначального количества вершин в графе, если это имеет значение). Нужно получить из исходного графа подграф, который будет содержать все выбранные/указанные n вершин, также будет оставаться связанным, но число вершин из исходного графа, не входящих в n, но включаемых в подграф, для сохранения связанности, будет минимальным.

Наверняка такая задача уже имеет решение, подскажите, пожалуйста, куда копать? Если нет ссылки на описание, хотя бы просто название алгоритма.
  • Вопрос задан
  • 209 просмотров
Пригласить эксперта
Ответы на вопрос 1
@Aniro
Исключить из графа все вершины не входящие в выборку, заменив на ребра со сложенным весом. Т.е. допустим есть вершина А, ребра AB=1, AC=1, AD=2. Вершина и ребра заменяются на ребра: BC=2, BD=3, CD=3
Затем найти минимальное остовное дерево. Можно взять алгоритм Краскала, описание есть на вики: https://ru.wikipedia.org/wiki/Алгоритм_Краскала
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы