Независимое множество

---

Независимое множество в теории графов может быть как независимым множеством вершин, так и независимым множеством рёбер. Независимые множества рассматриваются в задачах покрытия графов.

В неориентированном графе ${\displaystyle G=(V,E)}$ множество его вершин ${\displaystyle S}$, где ${\displaystyle S\subset V}$, называется независимым (или внутренне устойчивым), если любые две вершины в нем несмежны, то есть никакая пара вершин не соединена ребром ^{[1] [2] [3]}, или другими словами множество ${\displaystyle S}$ порождает пустой подграф:

Наибольшее число вершин в таких множествах называется вершинным числом независимости (иногда просто числом независимости) ${\displaystyle \beta _{0}(G)}$ графа ${\displaystyle G}$^[1], то есть, если ${\displaystyle Q}$ есть семейство всех независимых множеств вершин ${\displaystyle S}$, то ^[4] ${\displaystyle \beta _{0}(G)=\max\{|S|:S\in Q\}}$.

В неориентированном графе ${\displaystyle G=(V,E)}$ множество его рёбер ${\displaystyle M}$, где ${\displaystyle M\subset E}$, называется независимым, если никакая пара ребер несмежна ^{[1] [3]} или множество ${\displaystyle M}$ порождает пустой подграф:

---