Separator

Separator --- сепаратор.

1. (Separator of a graph) In a connected graph [math]\displaystyle{ G }[/math], a separator [math]\displaystyle{ S }[/math] is a subset of vertices whose removal separates [math]\displaystyle{ G }[/math] into at least two connected components. [math]\displaystyle{ S }[/math] is called an (a --- b) separator iff it disconnects the vertices [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math]. An (a --- b) separator is said to be a minimal separator iff it does not contain any other (a --- b) separator. A minimum separator is a separator of minimum size. Clearly, every minimum separator is a minimal separator. The (vertex) connectivity [math]\displaystyle{ \kappa(G) }[/math] is defined to be the size of a minimum separator. The connectivity of a complete graph is [math]\displaystyle{ |V| - 1 }[/math]. It doesn't have any separator.

See also

• Cutset, (a,b)-cut.

2. (Separator of a hypergraph) Let [math]\displaystyle{ {\mathcal H} }[/math] be a hypergraph and [math]\displaystyle{ X }[/math] be a subset of [math]\displaystyle{ V({\mathcal H}) }[/math]. A proper subset [math]\displaystyle{ X }[/math] of [math]\displaystyle{ V({\mathcal H}) }[/math] is a separator of [math]\displaystyle{ {\mathcal H} }[/math], if [math]\displaystyle{ \langle \bar{X}\rangle }[/math] is not connected.

Special separators are given by borders defined as follows. Let [math]\displaystyle{ {\mathcal C} }[/math] be a connected induced subhypergraph of [math]\displaystyle{ {\mathcal H} }[/math]. The boundary of [math]\displaystyle{ {\mathcal C} }[/math] in [math]\displaystyle{ {\mathcal H} }[/math], denoted [math]\displaystyle{ \partial_{H}{\mathcal C} }[/math], is the set of vertices that do not belong to [math]\displaystyle{ V({\mathcal C}) }[/math] and are adjacent to some vertex of [math]\displaystyle{ {\mathcal C} }[/math]; the closure of [math]\displaystyle{ {\mathcal C} }[/math] in [math]\displaystyle{ {\mathcal H} }[/math], denoted by [math]\displaystyle{ [{\mathcal C}]_{H} }[/math], is the subhypergraph of [math]\displaystyle{ {\mathcal H} }[/math] induced by [math]\displaystyle{ V({\mathcal C}) \cup \partial_{H}{\mathcal C} }[/math]. A border is a separator of [math]\displaystyle{ {\mathcal H} }[/math] that is the boundary of an [math]\displaystyle{ e }[/math]-component of [math]\displaystyle{ {\mathcal H} }[/math] for some edge [math]\displaystyle{ e }[/math] of [math]\displaystyle{ {\mathcal H} }[/math].

A partial edge of [math]\displaystyle{ {\mathcal H} }[/math] which is a separator is called a partial-edge separator of [math]\displaystyle{ {\mathcal H} }[/math]. A partial-edge separator [math]\displaystyle{ X }[/math] of [math]\displaystyle{ {\mathcal H} }[/math] is a divider, if there exist two vertices [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] of [math]\displaystyle{ {\mathcal H} }[/math] that are separated by [math]\displaystyle{ X }[/math] but not by any proper subset of [math]\displaystyle{ X }[/math].

We say that two vertices of [math]\displaystyle{ {\mathcal H} }[/math] are tightly connected in [math]\displaystyle{ {\mathcal H} }[/math], if they are separated in [math]\displaystyle{ {\mathcal H} }[/math] but not in any partial edge of [math]\displaystyle{ {\mathcal H} }[/math]. Moreover, by a compact of [math]\displaystyle{ {\mathcal H} }[/math] we mean a set of pairwise tightly connected vertices of [math]\displaystyle{ {\mathcal H} }[/math].