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

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

Независимое множество из 9 голубых вершин

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

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

$G(S,E^{\mathrm{\prime <!--\; \prime \; -->}})\subset <!--\; \subset \; -->G\Rightarrow <!--\; \Rightarrow \; -->E^{\mathrm{\prime <!--\; \prime \; -->}}=\mathrm{\varnothing <!--\; \varnothing \; -->}$$G(S,E^{\prime })\subset G~~\Rightarrow ~~E^{\prime }=\varnothing$ 

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

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

В неориентированном графе $G=(V,E)$$G=(V,E)$  множество его рёбер $M$$M$ , где $M\subset <!--\; \subset \; -->E$$M\subset E$ , называется независимым, если никакая пара ребер несмежна или множество $M$$M$  порождает пустой подграф:

$G(V^{\mathrm{\prime <!--\; \prime \; -->}},M)\subset <!--\; \subset \; -->G\Rightarrow <!--\; \Rightarrow \; -->V^{\mathrm{\prime <!--\; \prime \; -->}}=\mathrm{\varnothing <!--\; \varnothing \; -->}$$G(V^{\prime },M)\subset G~~\Rightarrow ~~V^{\prime }=\varnothing$ 

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

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