Остовное дерево с максимальным количеством листьев: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 58: | Строка 58: | ||
Рис. 1. Правила редукции были выведены для редукции данной структуры графа Клейтмана-Веста | Рис. 1. Правила редукции были выведены для редукции данной структуры графа Клейтмана-Веста | ||
Если перефразировать задачу в терминах структурной теории, важнейший вопрос будет звучать следующим образом: какова структура графов, не имеющих подграфа с k листьями? Результат Клейтмана и Веста из теории графов показывает, что граф с минимальной степенью не менее 3, не включающий подграф с k листьями, имеет не более 4(k - 3) вершин. На рис. 1 показано, что это лучший возможный результат для данной гипотезы. Однако исследование структуры при помощи экстремальных методов выявляет необходимость в применении правила редукции, показанного на рис. 2. Примерно 20 различных правил редукции с полиномиальнымвременем выполнения (некоторые из них являются намного более сложными и «глобальными» по своей структуре, чем приведенное для примера простое локальное правило редукции) будет достаточно для кернелизации графа с минимальной степенью 2, имеющего не более 3,5k вершин. | |||
[[Файл:MLST_2.png]] | |||
Рис. 2. Правило редукции для графа Клейтмана-Веста | |||