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
Let it be a simple graph and subsets of the node set .
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 .
If and are one element, one also speaks of the separation of the nodes and .
A pair separates the graph if and only if at least two nodes are separated from .
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.
Special cases
articulation
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 .
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.
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).