Independent set

Independent set --- независимое множество.

Let [math]\displaystyle{ G }[/math] be an undirected graph. [math]\displaystyle{ V' \subseteq V }[/math] is an independent set or stable set in [math]\displaystyle{ G }[/math] (or empty subgraph) if for all [math]\displaystyle{ u,v \in V' }[/math] [math]\displaystyle{ (u,v) \not \in E }[/math]. [math]\displaystyle{ S }[/math] is a maximal independent set if [math]\displaystyle{ S }[/math] is independent and for each vertex [math]\displaystyle{ u \in V(G) - S }[/math] the set [math]\displaystyle{ S \cup \{u\} }[/math] is not independent.

Let [math]\displaystyle{ G }[/math] be a directed graph. A set of vertices [math]\displaystyle{ W \subseteq V }[/math] is called independent if for every pair of vertices [math]\displaystyle{ u, v \in W }[/math] neither [math]\displaystyle{ (u,v) }[/math] nor [math]\displaystyle{ (v,u) }[/math] is present in the digraph. [math]\displaystyle{ W \subseteq V }[/math] is absorbent if for each [math]\displaystyle{ u \in V \setminus W }[/math] there exists [math]\displaystyle{ (u,v) \in A(G) }[/math] with [math]\displaystyle{ v \in W }[/math] and dominant if for each [math]\displaystyle{ v \in V\setminus W }[/math] there exists [math]\displaystyle{ (u,v) \in A(G) }[/math] with [math]\displaystyle{ u \in W }[/math]. A set [math]\displaystyle{ W \subseteq V }[/math] is a kernel of [math]\displaystyle{ G }[/math] if [math]\displaystyle{ W }[/math] is independent and absorbent and [math]\displaystyle{ W }[/math] is a solution of [math]\displaystyle{ G }[/math] if [math]\displaystyle{ W }[/math] is independent and dominant.

Independent set [math]\displaystyle{ Y }[/math] is called an essential independent set if there is [math]\displaystyle{ \{y_{1},y_{2}\} \subseteq Y }[/math] such that [math]\displaystyle{ dist(y_{1},y_{2}) = 2 }[/math].