Задача о независимом наборе
Материал из Википедии — свободной энциклопедии
Задача о независимом наборе относится к классу NP-полных задач в области теории графов. По сути, она полностью эквивалентна задаче о клике
Независимым набором (independent set) в графе называется такой набор вершин, никакие две из которых не связаны между собой ребром. Другими словами, это подграф, состоящий из изолированных вершин. В качестве иной формулировки говорят, что каждое ребро графа имеет не более одной вершины из независимого набора. Размер (size) независимого набора - число вершин, содержащихся в нем. Задача разрешения выглядит так: существует ли в заданном графе G независимый набор размера k? Соответствующая ей оптимизационная задача формулируется следующим образом: в заданном графе G требуется найти независимый набор максимального размера. Последняя и называется задачей о независимом наборе.
Иногда это задачу называют поиском независимого набора максимального размера. Не стоит путать это понятние с максимальным независимым набором. Последний - это такой набор изолированных вершин, что при прибавлении к нему еще одной вершины исходного графа получившийся подграф будет содержать хотя бы одно ребро. Очевидно, что таких наборов может быть несколько и они могут иметь разные размеры. Максимальный независимый набор отнюдь не всегда является независимым набором максимального размера, однако каждый независмый набор максимального размера, по определению, является максимальным независимым набором. Для нахождения последнего можно воспользоваться жадным алгоритмом, работающим за полиномиальное время, тогда как задача о независимом наборе максимального размера принадлежит, как было уже сказано, к классу NP-полных задач.
[править] Литература
- Chris Godsil Algebraic Graph Theory. — New York: Springer, 2004. — ISBN 0-387-95220-9
- Richard Karp. Reducibility Among Combinatorial Problems. Proceedings of a Symposium on the Complexity of Computer Computations. 1972.
- 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.
