Независимое множество (теория графов)
В теории графов независимое множество , стабильное множество , коклика или антиклика — это множество вершин в графе , никакие две из которых не являются смежными. То есть это набор вершин, такой, что для каждых двух вершин в нет ни одного ребра , соединяющего их. Эквивалентно, каждое ребро в графе имеет не более одной конечной точки в . Множество независимо тогда и только тогда, когда оно является кликой в дополнении к графу.. Размер независимого множества — это количество содержащихся в нем вершин. Независимые множества также называют «внутренне устойчивыми множествами», сокращением которых является «стабильное множество». [1]
Максимальное независимое множество — это независимое множество, которое не является собственным подмножеством какого-либо другого независимого множества.
Максимальный независимый набор — это независимый набор максимально возможного размера для данного графа . Эта величина называется числом независимости и обычно обозначается . [2] Задача оптимизации нахождения такого множества называется задачей максимального независимого множества. Это сильно NP-трудная задача. [3] Таким образом, маловероятно, что существует эффективный алгоритм для нахождения максимального независимого множества графа.
Каждое максимальное независимое множество также является максимальным, но обратная импликация не обязательна.
Множество независимо тогда и только тогда, когда оно является кликой в дополнении к графу , поэтому эти два понятия дополняют друг друга. На самом деле достаточно большие графы без больших клик имеют большие независимые множества — тема, которая исследуется в теории Рамсея .
Множество независимо тогда и только тогда, когда его дополнение является вершинным покрытием . [4] Таким образом, сумма размера наибольшего независимого множества и размера минимального вершинного покрытия равна количеству вершин в графе.
