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

Самой эффективной техникой является метод ветвления и поиска, широко использовавшийся в алгоритмах решения задачи о вершинном покрытии и многих других NP-полных задач. Этот метод можно описать следующим образом. Пусть (G, k) – экземпляр задачи о вершинном покрытии. Предположим, что каким-либо образом определено семейство <math>\{ C_1, ..., C_b \} \;</math> подмножеств графа G (где для каждого i подмножество <math>C_i \;</math> имеет <math>c_i \;</math> вершин), такое, что если граф G содержит вершинное покрытие из k вершин, то по меньшей мере для одного из подмножеств <math>C_i \;</math> существует вершинное покрытие из k вершин для G, содержащее все вершины из <math>C_i \;</math>. После этого можно построить семейство экземпляров меньшего размера <math>(G_i, k_i) \;</math>, где <math>1 \le i \le b \;</math>; <math>k_i = k - c_i \;</math>, а <math>G_i \;</math> получается из G путем удаления всех вершин, входящих в <math>C_i \;</math>. Отметим, что исходный граф G имеет вершинное покрытие из k вершин в том и только том случае, если один из меньших экземпляров <math>(G_i, k_i) \;</math> графа <math>G_i \;</math> имеет вершинное покрытие из <math>k_i \;</math> вершин. Таким образом, процесс может быть разветвлен на b подпроцессов, каждый из которых на меньшем экземпляре задачи <math>(G_i, k_i) \;</math> рекурсивно выполняет поиск вершинного покрытия из <math>k_i \;</math> вершин для графа <math>G_i \;</math>.

Пусть T(k) – количество листьев в дереве поиска для вышеописанного процесса ветвления и поиска на экземпляре задачи (G, k). Тогда операция ветвления дает следующее рекуррентное соотношение: