Hardprob/Minimum Steiner Tree
Материал из DISCOPAL
Версия от 14:53, 7 апреля 2023; StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --> * Полный граф <m>G=\left(V,E\right)</m>, метрика — веса на ребрах <m>s: E\rightarrow N</m>, некоторое по…»)
- Полный граф , метрика — веса на ребрах , некоторое подмножество требуемых вершин.
- Найти дерево Штейнера, т.е. поддерево G которое включает все вершины из S.
- Минимизировать сумму весов ребер этого поддерево.
Задача в лаб17 (рид-онли просмотр)
- Задача в базе NP-полных задач Вигго Кана
- Код задачи в книге «ГД» → «ND12»
- Задача в википедии
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.