4446
правок
Остовное дерево с максимальным количеством листьев: различия между версиями
Перейти к навигации
Перейти к поиску
Остовное дерево с максимальным количеством листьев (посмотреть исходный код)
Версия от 09:53, 12 августа 2016
, 12 августа 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 66: | Строка 66: | ||
Рис. 2. Правило редукции для графа Клейтмана-Веста | Рис. 2. Правило редукции для графа Клейтмана-Веста | ||
В общем случае экземпляр параметризованной задачи состоит из пары (x, k) и «границы», которая вычисляется посредством фиксации x и изменения k с послеующим определением, является ли ответом на задачу разрешимости «да» или «нет. Представляет интерес величина границы при редукции x. Типичная граничная лемма выглядит следующим образом. | |||
Лемма 2. Пусть (G, k) – экземпляр задачи построения максимального листового остовного дерева после редукции, для которого (G, k) является «да-экземпляром», а (G, k + 1) – «нет-экземпляром». Тогда |G| < ck (где c – небольшая константа, значение которой будет вычислено в результате решения). | |||
Доказательство граничной леммы выполняется при помощи минимального контрпримера. Контрпримером будет служить граф, такой, что (G, k) – экземпляр задачи МЛОД после редукции; (2) (G, k) является «да-экземпляром»; (3) (G, k + 1) не является «нет-экземпляром»; (4) |G| < ck | |||
Доказательство граничной леммы будет производиться постепенно. Изначально неизвестно, при каком значении границы будет достигнут успех, а также точнонеизвестно, что подразумевается под редукцией. В ходе доказательства эти аспекты станут ясны. По мере раскрытия аргументов положение структуры подскажет новые правила редукции. При доказательстве граничной леммы необходимо будет принимать следующие стратегические решения: | |||
(1) Определение полярности границы и формулировка граничной леммы. | |||
(2) Выбор структуры для представления. | |||
(3) Задание индуктивных приоритетов. | |||
(4) Разработка серии утверждений по поводу структуры, описывающих ситуацию на границе. | |||
(5) Определение правил редукции, выполняющихся за полиномиальное время над релевантными компонентами структуры на границе. | |||
(6) По мере уточнения структуры на границе – заполнение неизвестных компонентов границы кернелизации. | |||
Общая структура аргумента вычисляется при помощи минимального контрпримера согласно приоритетам, заданным в результате выбора (3), который обычно ссылается на выбор (2). Доказательство развивается посредством серии небольших шагов, состоящих из серии утверждений по поводу структуры, которые в сумме ведут к получению детального представления структур на «границе» и, следовательно, позволяют определить границу размера G, на основе которой выводится заключение леммы. Полное доказательство объединяет серию утверждений по поводу пограничного дерева, различных множеств вершин и индуктивных приоритетов индукции и формирует основное неравенство, на основе которого производится доказательство по индукции, и ядро задачи размера 3,5k. | |||