Локальная замена.

Этот метод состоит в том, что выбирается некоторое характерное свойство известной NP-полной задачи, с помощью него образуется семейство основных модулей, а соответствующие индивидуальные задачи исследуемой задачи получаются путём единообразной замены каждого основного модуля некоторой другой структурой. Важным моментом является то, что каждая замена приводит только к локальному изменению структуры, причём замены не зависят друг от друга.

Задача РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ.

Условие: Задан граф G=(V,E) число вершин которого кратно 3, т.е. |V|=3q.

Вопрос: Существует ли такое разбиение V на q непересекающихся подмножеств V₁,V₂, …, V_q, каждое из которых содержит ровно 3 элемента, и для каждого V_i={v_i1, v_i2, v_i3} рёбра {v_i1, v_i2}, {v_i2, v_i3}, {v_i3, v_i1} принадлежат E.

Сведём задачу ТП-3 к задаче РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ.

Пусть множество X (|X|=3q) и семейство C его трёхэлементных подмножеств образуют условие произвольной индивидуальной задачи из ТП-3. Построим граф G=(V,E), такой, что |V|=3q’ и для него существует искомое разбиение тогда и только тогда, когда семейство C содержит точное покрытие множества.

Основными модулями рассматриваемой индивидуальной задачи из ТП-3 будут трёхэлементные подмножества из C. Операция локальной замены превращает каждое элементарное подмножество C_i=(x_i, y_i, z_i)C в набор E_i, состоящий из 18 рёбер. Это преобразование можно изобразить следующим образом:

Таким образом, формируемый графG будет таким:

Заметим, что по построению только вершины из множества X могут быть инцидентны более чем одному множеству E_i. Кроме того, количество вершин |V|=3q+9|С|=3q’, где С – семейство трёхэлементных подмножеств.

Индивидуальную задачу РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ можно построить за полиномиальное время из задачи ТП-3. Если c₁, c₂, …, c_q – трёхэлементные подмножества из C, которые образуют ТП-3, то соответствующее разбиение V на треугольники V₁, V₂, …, V_q’ строится следующим образом. Если c_i=(x_i, y_i, z_i) – элемент точного покрытия, то из множества E_i выбираются элементы: (x_i, a_i[1], a_i[2]) (y_i, a_i[4], a_i[5]) (z_i, a_i[7], a_i[8]) (a_i[3], a_i[6], a_i[9]). Если же элемент C_i=(x_i, y_i, z_i) не входит в точное покрытие, то из множества E_i выбираются тройки (a_i[1], a_i[2], a_i[3]) (a_i[4], a_i[5], a_i[6]) (a_i[7], a_i[8], a_i[9]). Такой выбор элементов обеспечивает то, что каждый элемент из множества X содержится ровно в одном трёхвершинном подмножестве рассматриваемого разбиения.

Обратно, если V=V₁V₂V₃ … V_q’ – произвольное разбиение графа G на треугольники, то соответствующее точное покрытие множества X получается, если выбирать те подмножества c_i, для которых (a_i[3], a_i[6], a_i[9])=V_j при некотором j, 1 ≤ j ≤ q’.

Приведённый пример представляет собой доказательство метода локальной замены в “чистом виде”. Здесь структура рассматриваемой индивидуальной задачи однозначно определялась структурой исходной задачи (NP-полнота которой известна).

Часто оказывается полезным дополнить рассматриваемую индивидуальную задачу вспомогательными элементами, которые играют роль ограничителя, налагающего дополнительные ограничения на способы получения ответа “да”.