Задача о независимом множестве
Зада́ча о незави́симом мно́жестве относится к классу NP-полных задач в области теории графов. Эквивалентна задаче о клике.
Множество вершин графа называется независимым, если никакие две вершины этого множества не соединены ребром. Другими словами, индуцированный этим множеством подграф состоит из изолированных вершин. Иногда также говорят, что каждое ребро графа инцидентно не более чем одной вершине из независимого множества. Задача распознавания (проблема разрешимости) выглядит так: существует ли в заданном графе G независимое множество размера k? Соответствующая ей оптимизационная задача, она же задача о независимом множестве, формулируется следующим образом: в заданном графе G требуется найти независимое множество максимального размера. Этот размер называют числом независимости, числом внутренней плотности или неплотностью и обозначают как [1][2].
Иногда эту задачу называют поиском наибольшего независимого множества. Не стоит путать это понятие с максимальным независимым множеством, или максимальным по включению независимым множеством, которое определяется как такое независимое множество вершин, что при добавлении к нему ещё одной (любой) вершины исходного графа оно перестаёт быть независимым (вообще говоря, таких множеств может быть несколько и разных размеров). Максимальное по включению независимое множество отнюдь не всегда является наибольшим. В то же время каждое наибольшее независимое множество по определению является также и максимальным по включению. Для нахождения (какого-то) максимального по включению независимого множества можно воспользоваться жадным алгоритмом, работающим за полиномиальное время, тогда как задача о наибольшем независимом множестве принадлежит к классу NP-полных задач.
Максимальное по включению независимое множество является доминирующим множеством. Любой граф содержит максимум 3n/3 максимальных по включению независимых множеств[3], однако бо́льшая часть графов имеет их куда меньше.
Число максимальных по включению независимых множеств в циклах из n вершин — это числа Перрина, а число максимальных по включению независимых множеств в путях с n вершинами задаётся последовательностью Падована[4]. Таким образом, оба числа пропорциональны степени 1,324718, пластическому числу.
Множество независимо тогда и только тогда, когда оно является кликой в дополнении графа, так что два понятия дополняют друг друга. Достаточно большие графы без больших клик имеют большие независимые множества, что является предметом исследования в теории Рамсея.