- Задача о независимом множестве
-
Задача о независимом множестве относится к классу NP-полных задач в области теории графов. Эквивалентна задаче о клике.
Содержание
Определения
Независимый набор из 9 голубых вершинМножество вершин графа называется независимым, если никакие две вершины этого множества не соединены ребром. Другими словами, индуцированный этим множеством подграф состоит из изолированных вершин. Иногда также говорят, что каждое ребро графа инцидентно не более чем одной вершине из независимого множества. Задача распознавания (англ.) выглядит так: существует ли в заданном графе G независимое множество размера k? Соответствующая ей оптимизационная задача, она же задача о независимом множестве, формулируется следующим образом: в заданном графе G требуется найти независимое множество максимального размера.
Иногда эту задачу называют поиском независимого множества максимального размера или максимального (по размеру) независимого множества. Не стоит путать это понятие с максимальным (по включению) независимым множеством, которое определяется как такое независимое множество вершин, что при добавлении к нему еще одной (любой) вершины исходного графа оно перестает быть независимым. Понятно, что таких множеств, вообще говоря, может быть несколько и разных размеров. Максимальное по включению независимое множество отнюдь не всегда является максимальным по размеру. В то же время, каждое независимое множество максимального размера по определению является также и максимальным по включению. Для нахождения (какого-то) максимального по включению независимого множества можно воспользоваться жадным алгоритмом, работающим за полиномиальное время, тогда как задача о независимом множестве максимального размера принадлежит к классу NP-полных задач.
Максимальное независимое множество в дереве
Если данный граф является деревом, то задача о независимом множестве эффективно решается методом динамического программирования.
Оптимальная подструктура задачи
Структура дерева сама подсказывает решение задачи: Обозначим корнем дерева любую вершину и назовем её
. Пусть
обозначает размер максимального независимого множества вершин поддерева, корнем которого является вершина
. Тогда ответом на задачу будет являться
.
Нетрудно видеть, что если мы включаем вершину u в максимальное независимое множество, то его мощность увеличивается на 1, но его детей мы брать не можем (так как они соединены ребром с вершиной u); если же мы не включаем эту вершину, то мощность максимального независимого множества будет равен сумме размеров независимых множеств детей этой вершины. Остается только выбрать максимум из этих двух вариантов, чтобы получить решение задачи:
где grandchild обозначает всякого «внука» вершины, а child обозначает всякого потомка вершины.
Псевдокод
Считаем, что в вершине u хранится
:
function get_independent_set(Node u) { если I(u) уже посчитано, то возвратить I(u) //мощность множества, которое можно получить, если не брать вершину u children_sum = 0 //мощность множества, которое можно получить, если взять вершину u grandchildren_sum = 0 //цикл по всем детям for i := 1 to child_num do children_sum = children_sum + get_independent_set(children[i]) //цикл по всем внукам for i:= 1 to grandchildren_num grandchildren_sum = grandchildren_sum + get_independent_set(grandchildren[i]) //запоминаем, чтобы не персчитывать ещё раз I(u) = max(1 + grandchildren_sum, children_sum) возвратить I(u) }
Вызов get_independent_set(r) даст ответ на задачу. Время выполнения алгоритма, очевидно, O(|V| + |E|).
Литература
- Godsil Chris Algebraic Graph Theory. — New York: Springer, 2004. — ISBN 0-387-95220-9
- Richard Karp (1972). «Reducibility Among Combinatorial Problems». Proceedings of a Symposium on the Complexity of Computer Computations.
- Michael R. Garey, David S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness. — W.H. Freeman, 1979. — ISBN ISBN 0-7167-1045-5 A1.2: GT20, pg.194.
- Sanjoy Dasgupta , Christos H. Papadimitriou, Umesh Vazirani Algorithms. — 1-е изд. — McGraw-Hill Science/Engineering/Math, 2006. — С. 336. — ISBN 0073523402
См. также
- Алгоритм Брона — Кербоша для нахождения максимальных по включению независимых множеств вершин.
Ссылки
- Weisstein, Eric W. Maximal Independent Vertex Set (англ.) на сайте Wolfram MathWorld.
- Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring
- Поликарпова Н., Герасименко А. Методы решения труднорешаемых задач
- Слайды лекции о динамическом программировании
NP-полные задачи Математика Исследование операций:Оптимизация:Комбинаторная оптимизация Максимизационная задача
укладки (упаковки)Упаковка в контейнеры (двумерная упаковка • линейная упаковка • упаковка по весу • упаковка по стоимости) • Задача о ранце (рюкзаке) Теория графов
теория множествЗадача о вершинном покрытии • Задача о клике • Задача о независимом множестве (наборе) • Задача о покрытии множества • Задача Штейнера • Задача коммивояжёра • Обобщённая задача коммивояжёра Алгоритмические задачи Задача выполнимости булевых формул (в конъюнктивной нормальной форме) Логические игры
и головоломкиОбобщённые пятнашки с костяшками >15) (задача поиска кратчайшего решения) • Задачи, решения которых применяются в Тетрис • Задача обобщённого судоку • Задача о заполнении латинского квадрата • Задача какуро См. также Прикладная математика • Теория алгоритмов • Динамическое программирование • 21 NP-полная задача Карпа Классы сложности Категории:- NP-полные задачи
- Теория графов
- Алгоритмы на графах
- Динамическое программирование
Wikimedia Foundation. 2010.