Остовное дерево с максимальным количеством листьев: различия между версиями

Перейти к навигации Перейти к поиску
Строка 78: Строка 78:




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


(1) Определение полярности границы и формулировка граничной леммы.
(1) Определение полярности границы и формулировка граничной леммы.
Строка 88: Строка 88:
(4) Разработка серии утверждений по поводу структуры, описывающих ситуацию на границе.
(4) Разработка серии утверждений по поводу структуры, описывающих ситуацию на границе.


(5) Определение правил редукции, выполняющихся за полиномиальное время над релевантными компонентами структуры на границе.
(5) Определение правил редукции, выполняющихся за полиномиальное время над релевантными структурными ситуациями на границе.


(6) По мере уточнения структуры на границе – заполнение неизвестных компонентов границы кернелизации.
(6) По мере уточнения структуры на границе – заполнение неизвестных компонентов границы кернелизации.




Общая структура аргумента вычисляется при помощи минимального контрпримера согласно приоритетам, заданным в результате выбора (3), который обычно ссылается на выбор (2). Доказательство развивается посредством серии небольших шагов, состоящих из серии утверждений по поводу структуры, которые в сумме ведут к получению детальной картины представления структур на «границе» и, следовательно, позволяют определить границу размера G, на основе которой выводится заключение леммы. Полное доказательство объединяет серию утверждений по поводу дерева-свидетеля, различных множеств вершин и индуктивных приоритетов индукции и формулирует основное неравенство, на основе которого производится доказательство по индукции, и ядро задачи размера 3,5k.
Общая структура аргумента вычисляется при помощи минимального контрпримера согласно приоритетам, заданным в результате выбора (3), который обычно ссылается на выбор (2). Доказательство развивается посредством серии небольших шагов, состоящих из утверждений по поводу структуры, которые в сумме ведут к получению детальной структурной картины на «границе» и, следовательно, позволяют определить границу размера G, которая и представляет собой заключение леммы. Полное доказательство объединяет серию утверждений по поводу дерева-свидетеля, различных множеств вершин и индуктивных приоритетов и формулирует основное неравенство, на основе которого производится доказательство по индукции, и ядро задачи размера 3,5k.




Источник — http://pco.iis.nsk.su/wega/index.php/Остовное_дерево_с_максимальным_количеством_листьев