Остовное дерево с максимальным количеством листьев

Материал из WEGA
Версия от 15:00, 4 августа 2016; Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Связное доминирующее множество; [[экстремальная структу…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Ключевые слова и синонимы

Связное доминирующее множество; экстремальная структура


Постановка задачи

Задача построения максимального листового остовного дерева заключается в нахождении остовного дерева, имеющего не менее k листьев, на неориентированном графе. Версия с принятием решений параметризованной задачи построения максимального листового остовного дерева выглядите следующим образом:


Дано: связный граф G, целое число k.

Параметр: целое число k.

Вопрос: имеет ли граф G с не менее чем k листьями?