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

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

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

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

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

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

В неориентированном графе ${\displaystyle G=(V,E)}$ множество его рёбер ${\displaystyle M}$ , где ${\displaystyle M\subset E}$ , называется независимым , если никакая пара ребер несмежна или множество ${\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\}}$ .

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

Примечания

Литература