4551
правка
Остовное дерево с максимальным количеством листьев: различия между версиями
Материал из WEGA
Остовное дерево с максимальным количеством листьев (посмотреть исходный код)
Версия от 21:50, 29 августа 2016
, 29 августа 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача построения остовного дерева с максимальным количеством листьев (ОДМЛ; MAX LEAF SPANNING TREE) заключается в нахождении [[остовное дерево|остовного дерева]], имеющего не менее k листьев, | Задача построения остовного дерева с максимальным количеством листьев (ОДМЛ; MAX LEAF SPANNING TREE) заключается в нахождении [[остовное дерево|остовного дерева]], имеющего не менее k листьев, в неориентированном графе. Версия разрешимости для параметризованной задачи построения ОДМЛ выглядит следующим образом: | ||
