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

В общем случае экземпляр параметризованной задачи состоит из пары (x, k) и «границы», которая вычисляется посредством фиксации x и изменения k с последующим определением, какой ответ имеет [[задача разрешимости]] – «да» или «нет. Представляет интерес величина границы при редукции x. Типичная граничная лемма выглядит следующим образом.

'''Лемма 2.''' Пусть (G, k) – экземпляр задачи построения остовного дерева с максимальным количеством листьев после редукции, для которого (G, k) является «да-экземпляром», а (G, k + 1) – «нет-экземпляром». Тогда <math>|G| \le ck \;</math> (где c – небольшая константа, значение которой будет вычислено в результате решения).

Доказательство граничной леммы выполняется при помощи минимального контрпримера. Контрпримером будет служить граф, такой, что (1) (G, k) – экземпляр задачи ОДМЛ после редукции; (2) (G, k) является «да-экземпляром»; (3) (G, k + 1) является «нет-экземпляром»; (4) |G| < ck.