4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 69: | Строка 69: | ||
В общем случае экземпляр параметризованной задачи состоит из пары (x, k) и «границы», которая вычисляется посредством фиксации x и изменения k с последующим определением, какой ответ имеет [[задача разрешимости]] – «да» или | В общем случае экземпляр параметризованной задачи состоит из пары (x, k) и «границы», которая вычисляется посредством фиксации x и изменения k с последующим определением, какой ответ имеет [[задача разрешимости]] – «да» или «нет». Представляет интерес величина границы при редукции x. Типичная граничная лемма выглядит следующим образом. | ||
'''Лемма 2.''' Пусть (G, k) – экземпляр задачи построения остовного дерева с максимальным количеством листьев после редукции, для которого (G, k) является «да-экземпляром», а (G, k + 1) – «нет-экземпляром». Тогда <math>|G| \le ck \;</math> (где c – небольшая константа, значение которой будет вычислено в результате | '''Лемма 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| | Доказательство граничной леммы выполняется при помощи минимального контрпримера. Контрпримером будет служить граф, такой, что (1) (G, k) – экземпляр задачи ОДМЛ после редукции; (2) (G, k) является «да-экземпляром»; (3) (G, k + 1) является «нет-экземпляром»; (4) |G| > ck. | ||
правка