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

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

${\displaystyle G(S,E^{\prime })\subset G~~\Rightarrow ~~E^{\prime }=\varnothing }$

Наибольшее число вершин в таких множествах называется вершинным числом независимости (иногда просто числом независимости) ${\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}$ порождает пустой подграф:

${\displaystyle G(V^{\prime },M)\subset G~~\Rightarrow ~~V^{\prime }=\varnothing }$

Наибольшее число рёбер в таких множествах называется рёберным числом независимости ${\displaystyle \beta _{1}(G)}$ графа ${\displaystyle G}$, то есть, если ${\displaystyle W}$ есть семейство всех независимых множеств рёбер ${\displaystyle M}$, то ${\displaystyle \beta _{1}(G)=\max\{|M|:M\in W\}}$.

Множество независимых рёбер также называют паросочетанием [5]. Поэтому независимое множество ${\displaystyle M}$, имеющее кардинальное число ${\displaystyle \beta _{1}}$ называется наибольшим паросочетанием графа ${\displaystyle G}$.