Независимое множество (теория графов)

В теории графов независимое множество , устойчивое множество , коклика или антиклика — это множество вершин графа , никакие две из которых не являются смежными . То есть это набор вершин, в котором для каждых двух вершин в , нет ребра, соединяющего их. Эквивалентно, каждое ребро графа имеет не более одной конечной точки в . Множество независимо тогда и только тогда, когда оно является кликой в дополнении графа . Размер независимого множества — это количество содержащихся в нем вершин. Независимые множества также называют «внутренне стабильными множествами», сокращением которых является «стабильный набор». ^[1] $S$ $S$ $S$

Максимальное независимое множество — это независимое множество, которое не является собственным подмножеством какого-либо другого независимого множества.

Максимальный независимый набор — это независимый набор максимально возможного размера для данного графа . Эта величина называется числом независимости и обычно обозначается . ^[2] Оптимизационная задача поиска такого набора называется проблемой максимального независимого множества. Это сильно NP-трудная задача. ^[3] Таким образом, маловероятно, что существует эффективный алгоритм поиска максимального независимого множества графа. $G$ $G$ $\альфа (G)$

Каждое максимальное независимое множество также является максимальным, но обратное импликация не обязательно имеет место.

Множество независимо тогда и только тогда, когда оно является кликой в дополнении графа , поэтому эти две концепции дополняют друг друга. Фактически, достаточно большие графы без больших клик имеют большие независимые множества — тема, которая исследуется в теории Рамсея .

Множество независимо тогда и только тогда, когда его дополнение является вершинным покрытием . ^[4] Следовательно, сумма размера наибольшего независимого множества и размера минимального вершинного покрытия равна количеству вершин в графе. $\альфа (G)$ $\бета (G)$