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

Самой эффективной техникой является метод ветвления и поиска, широко использовавшийся в алгоритмах решения задачи о вершинном покрытии и многих других NP-полных задач. Этот метод можно описать следующим образом. Пусть (G, k) – экземпляр задачи о вершинном покрытии. Предположим, что каким-либо образом определено семейство fC1... C bg подмножеств графа G (где для каждого i подмножество Ci имеет ci вершин), такое, что если граф G содержит вершинное покрытие из k вершин, то по меньшей мере для одного из подмножеств Ci существует вершинное покрытие из k вершин для G, содержащее все вершины из Q. После этого можно построить семейство экземпляров меньшего размера (Gi, ki), где 1 < i < b; ki = k — ci, а Gi получается из G путем удаления всех вершин, входящих в Q. Отметим, что исходный граф G имеет вершинное покрытие из k вершин в том и только том случае, если один из меньших экземпляров (Gi, ki) графа Gi имеет вершинное покрытие из ki вершин. Таким образом, процесс может быть разветвлен на b подпроцессов, каждый из которых на меньшем экземпляре задачи (Gi, ki) рекурсивно выполняет поиск вершинного покрытия из ki вершин для графа Gi.