Separator (graph theory)

In graph theory, separators are special subsets of nodes and edges of a graph , whose removal from the graph makes certain paths in the graph impossible.

definition

The crowd is a - -separator ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle B}$

The knot is a hinge point, the edge is a bridge. ${\displaystyle a}$ ${\displaystyle e}$

Let it be a simple graph and subsets of the node set . ${\displaystyle G=(V,E)}$ ${\displaystyle A,B\subset V}$ ${\displaystyle V}$

A pair consisting of a set of nodes and a set of edges is called - - separator or - - separator of the graph, if each - -path contains at least one node from or one edge from . One then also says that the sets of nodes and separates . ${\displaystyle Z=(X,Y)}$ ${\displaystyle X\subseteq V}$ ${\displaystyle Y\subseteq E}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle A}$ ${\displaystyle B}$

If and are one element, one also speaks of the separation of the nodes and . ${\displaystyle A=\{a\}}$ ${\displaystyle B=\{b\}}$ ${\displaystyle a}$ ${\displaystyle b}$

A pair separates the graph if and only if at least two nodes are separated from . ${\displaystyle Z=(X,Y)}$ ${\displaystyle G}$ ${\displaystyle Z}$ ${\displaystyle G}$

Equivalent definition

Sometimes in the literature a - separator for a graph is also defined as a set of nodes and edges, so that each - path contains at least one element from . The further definitions are analogous to the above. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle G=(V,E)}$ ${\displaystyle X\subseteq V\cup E}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle X}$

Special cases

articulation

→ Main article : pivot point (graph theory)

If a node separates two nodes that belong to the same connected component of the graph, it is called an articulation , an articulation point or an intersection node of the graph. A separator with and corresponds to a hinge point . ${\displaystyle v\in V}$ ${\displaystyle v}$ ${\displaystyle Z=(X,Y)}$ ${\displaystyle X=\{v\}}$ ${\displaystyle Y=\emptyset }$

If a connected graph has an articulation point, its node connection number is equal to 1 and it is referred to as separable.

bridge

If there is an edge that separates its two end nodes, it is called a bridge . A separator with and corresponds to a bridge . Equivalent to this is that there is no circle in the graph. ${\displaystyle e\in E}$ ${\displaystyle e}$ ${\displaystyle Z=(X,Y)}$ ${\displaystyle X=\emptyset }$ ${\displaystyle Y=\{e\}}$ ${\displaystyle e}$

If a connected graph has a bridge, its edge connection number is 1.

use

Separators are one of the basic concepts of graph theory. They are used, for example, to define the graph properties k-connection and edge connection . In both of these cases, separators are of interest that only consist of nodes or only edges.

literature

• Reinhard Diestel : graph theory . 4th edition. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (English, diestel-graph-theory.com - first edition: 1996).