Cut (graph theory)

In graph theory, a cut denotes a partition of the node set of a graph . Sections in connection with networks are of particular importance . However, sections can also be defined and examined independently of networks.

definition

Set of knots (red) and remaining amount (black) of a cut and the intersecting cut edges (blue)

{\ displaystyle X}

{\ displaystyle V \ setminus X}

{\ displaystyle E (X, V \ setminus X)}

Every non-empty subset of the vertex set of an undirected graph defines a section of the graph. ${\ displaystyle X \ subset V}$ ${\ displaystyle G = (V, E)}$ ${\ displaystyle (X, V \ backslash X)}$

This clearly shows the number of cut edges

{\ displaystyle E (X, V \ backslash X) = \ {(u, v) \ in E: u \ in X, v \ in V \ backslash X \}}

induced. It includes all edges of the graph, one end node of which lies in the subset and the other in the set of the other nodes. ${\ displaystyle X}$

In directed graphs there are different definitions of the intersection edges. Often one uses ${\ displaystyle D = (V, A)}$

{\ displaystyle A (X, V \ backslash X) = \ {(u, v) \ in A: u \ in X, v \ in V \ backslash X \}}

.

Obviously, in contrast to undirected graphs, the following applies here: can be. ${\ displaystyle A (X, V \ backslash X) \ neq A (V \ backslash X, X)}$

Another possibility to define intersection edges in directed graphs is to include the edges in initially independent of their orientation, so that again would apply. In this case, and would split up into the two subsets . If it then holds that either or , one speaks of a directed cut , i.e. H. all directed edges either point into or out of the set . ${\ displaystyle A (X, V \ backslash X)}$ ${\ displaystyle A (X, V \ backslash X) = A (V \ backslash X, X)}$ ${\ displaystyle A}$ ${\ displaystyle A ^ {+}}$ ${\ displaystyle A ^ {-}}$ ${\ displaystyle A ^ {+} = \ emptyset}$ ${\ displaystyle A ^ {-} = \ emptyset}$ ${\ displaystyle X}$

Important sentences and statements

Context and minimal cuts

If one were to remove all edges of a section from the graph , there would be no more path between and . If the graph was connected before the edges of the section were removed, it is no longer connected afterwards. ${\ displaystyle E (X, V \ backslash X)}$ ${\ displaystyle G}$ ${\ displaystyle X}$ ${\ displaystyle V \ backslash X}$

The left cut is not minimal as it contains the two right cuts

In this context, a section is also referred to as a minimum section if, after removing the edges of the section from the graph, exactly two connected components arise. It can be shown that this is the case if and only if a set of vertices can be chosen in such a way that the intersection induced by it does not contain any subsets of edges that form a intersection induced by another set of vertices. In short: A cut is minimal if a subset of the cut does not already form a cut. ${\ displaystyle X}$

Disjoint paths and cuts

The mathematician Karl Menger established a connection between node- and edge-disjoint paths and sections. This theorem from Menger was later generalized to the Max-Flow-Min-Cut theorem .

Consider a connected graph with two subsets of the nodes with and . Between two nodes with and one examines the number of edge- disjoint paths as well as the cardinality (i.e. number of edges) of a cut . Since all edge-disjoint paths have to go from to through the cut (because removing the edges of the cut destroys all paths from to ) and, since the paths have to be edge-disjoint, a different edge of the cut must be used every time, obviously the The cardinality of the section must be at least as large as the number of edge-disjoint paths between and . Menger finally showed that the maximum number of edge-disjoint paths corresponds exactly to a minimum separating edge set. ${\ displaystyle G = (V, E)}$ ${\ displaystyle S, T}$ ${\ displaystyle S \ subset V}$ ${\ displaystyle T = V \ setminus S}$ ${\ displaystyle u, v}$ ${\ displaystyle u \ in S}$ ${\ displaystyle v \ in T}$ ${\ displaystyle E (S, T)}$ ${\ displaystyle u}$ ${\ displaystyle v}$ ${\ displaystyle u}$ ${\ displaystyle v}$ ${\ displaystyle u}$ ${\ displaystyle v}$

This knowledge applies to both directed and undirected graphs. It can also be transferred from edge-disjoint to node-disjoint paths and then states that the maximum number of node-disjoint paths between two nodes and the cardinality corresponds to a minimum separating node set. ${\ displaystyle u}$ ${\ displaystyle v}$

The k-connection of a graph then means not only that you have to remove at least nodes in order to destroy the connection, but also that there must always be at least node-disjoint paths between any two nodes of a graph . ${\ displaystyle k}$ ${\ displaystyle k}$

Cuts and circles

There are also some relationships between cuts and circles . The cardinality of the intersection of the edges of a section and a circle must be straight. Imagine a circular edge for which it applies that it also lies on the cut, so o. B. d. A. and his. If the circle would now begin in and then use, the edge under consideration cannot be the only intersection of the circle and intersection, since you are now in the subset and still have to use an odd number of intersection edges between the circle and intersection in order to return to change back the subset in which is located. Overall, there must be an even number of cut edges. ${\ displaystyle E (S, T)}$ ${\ displaystyle C}$ ${\ displaystyle | E (S, T) \ cap C |}$ ${\ displaystyle e = (u, v) \ in C}$ ${\ displaystyle u \ in S}$ ${\ displaystyle v \ in T}$ ${\ displaystyle u}$ ${\ displaystyle e}$ ${\ displaystyle T}$ ${\ displaystyle S}$ ${\ displaystyle u}$

In a graph that is too dual , sections become circles and circles become sections. ${\ displaystyle G}$ ${\ displaystyle G ^ {*}}$

Strong connection

If a directed graph is strongly connected , one can again consider sets of nodes . Then it must hold for all possible sets that the cut is. According to the definition of directed cuts, this is equivalent to the statement that there must be no directed cut. Because with the "correct" choice of there could then be a directed cut , which by definition must mean that is, which would contradict the previous statement. ${\ displaystyle D = (V, A)}$ ${\ displaystyle S \ subset V}$ ${\ displaystyle S}$ ${\ displaystyle A ^ {+} (S, V \ backslash S) \ neq \ emptyset}$ ${\ displaystyle S}$ ${\ displaystyle A ^ {-} (S, V \ backslash S)}$ ${\ displaystyle A ^ {+} (S, V \ backslash S) = \ emptyset}$