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