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

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

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

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