Как постростроить подграф? Доброго времени суток. Извиняюсь за возможно корявую постановку задачи, но как могу..
Есть связанный неориентированный граф. Произвольным образом из этого графа выбирается n-ое количество вершин (n намного меньше изначального количества вершин в графе, если это имеет значение). Нужно получить из исходного графа подграф, который будет содержать все выбранные/указанные n вершин, также будет оставаться связанным, но число вершин из исходного графа, не входящих в n, но включаемых в подграф, для сохранения связанности, будет минимальным.
Наверняка такая задача уже имеет решение, подскажите, пожалуйста, куда копать? Если нет ссылки на описание, хотя бы просто название алгоритма.
Как постростроить подграф? Доброго времени суток. Извиняюсь за возможно корявую постановку задачи, но как могу..
Есть связанный неориентированный граф. Произвольным образом из этого графа выбирается n-ое количество вершин (n намного меньше изначального количества вершин в графе, если это имеет значение). Нужно получить из исходного графа подграф, который будет содержать все выбранные/указанные n вершин, также будет оставаться связанным, но число вершин из исходного графа, не входящих в n, но включаемых в подграф, для сохранения связанности, будет минимальным.
Наверняка такая задача уже имеет решение, подскажите, пожалуйста, куда копать? Если нет ссылки на описание, хотя бы просто название алгоритма.
Есть связанный неориентированный граф. Произвольным образом из этого графа выбирается n-ое количество вершин (n намного меньше изначального количества вершин в графе, если это имеет значение). Нужно получить из исходного графа подграф, который будет содержать все выбранные/указанные n вершин, также будет оставаться связанным, но число вершин из исходного графа, не входящих в n, но включаемых в подграф, для сохранения связанности, будет минимальным.
Наверняка такая задача уже имеет решение, подскажите, пожалуйста, куда копать? Если нет ссылки на описание, хотя бы просто название алгоритма.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для создания подграфа, содержащего все выбранные n вершин и оставляющего минимальное количество вершин из исходного графа, можно воспользоваться алгоритмом поиска минимального остовного дерева в подграфе, содержащем все выбранные вершины. Один из известных алгоритмов для этой задачи - алгоритм Прима или алгоритм Крускала.
Алгоритм Прима:
Начинаем с произвольной вершины из выбранных n вершин.Добавляем к остовному дереву ребро с наименьшим весом, которое инцидентно вершине из остовного дерева и ведет к вершине не из остовного дерева.Повторяем шаг 2 до тех пор, пока в подграфе не будут содержаться все выбранные n вершин.Алгоритм Крускала:
Сортируем все ребра графа по возрастанию весов.Начинаем с пустого графа и добавляем к нему наименьшее ребро из сортированного списка.Повторяем добавление ребер до тех пор, пока в подграфе не будут содержаться все выбранные n вершин.Оба алгоритма гарантируют построение связанного подграфа с минимальным количеством вершин из исходного графа для сохранения связанности.