Остовное дерево с максимальным количеством листьев: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Связное доминирующее множество; [[экстремальная структу…») |
(нет различий)
|
Версия от 15:00, 4 августа 2016
Ключевые слова и синонимы
Связное доминирующее множество; экстремальная структура
Постановка задачи
Задача построения максимального листового остовного дерева заключается в нахождении остовного дерева, имеющего не менее k листьев, на неориентированном графе. Версия с принятием решений параметризованной задачи построения максимального листового остовного дерева выглядите следующим образом:
Дано: связный граф G, целое число k.
Параметр: целое число k.
Вопрос: имеет ли граф G с не менее чем k листьями?