Vertex separator

Vertex separator --- вершинный сепаратор.

Given a graph [math]\displaystyle{ G = (V,E) }[/math], a subset [math]\displaystyle{ S \subset V }[/math] is called a vertex separator for nonadjacent vertices [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] in [math]\displaystyle{ V \setminus S }[/math], if [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] are in different connected components of [math]\displaystyle{ G[V \setminus S] }[/math]. If [math]\displaystyle{ S }[/math] is a v.s. for [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] but no proper subset of [math]\displaystyle{ S }[/math] separates [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] in this way, then [math]\displaystyle{ S }[/math] is called a minimal vertex separator for [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math]. A subset [math]\displaystyle{ S \subseteq V }[/math] is called a vertex separator, if there exists a pair of nonadjacent vertices for which [math]\displaystyle{ S }[/math] is a minimal vertex separator.