Edge connection

The edge connection of a graph is an important term in graph theory and a generalization of the connection . The edge connection is a measure of how difficult it is to split a graph into 2 components by deleting edges . If the edge connection is large, many edges must be deleted.

definition

A simple graph is called k-fold edge-connected if there is no separator with a maximum -element set of edges and an empty set of nodes in (in multigraphs , edges can be removed several times according to their multiplicity ). Equivalent to this is that for all edge sets the cardinality is connected. The edge -related number of a graph is the largest , so that -fold is edge-related. Equivalent to this is that the edge connection number is the smallest thickness of a separator with an empty set of nodes. ${\displaystyle G=(V,E)}$ ${\displaystyle Z=(X,Y)}$ ${\displaystyle (k-1)}$ ${\displaystyle Y}$ ${\displaystyle X=\emptyset }$ ${\displaystyle G}$ ${\displaystyle G'=(V,E\backslash U)}$ ${\displaystyle k-1}$ ${\displaystyle \lambda (G)}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle G}$

example

As an example, consider the house of Santa Claus on the right . It is 2-edge connected, since there are no separators that consist of only one edge. The equivalent of this is that there is no bridge . But if you look at z. B. node 5, then when deleting the two edges incident to node 5 , the graph splits into 2 connected components : node 5 itself and all other nodes. The house is thus 1-fold and 2-fold edge-connected and its edge-connection number is . In this case, the number of edge connections corresponds to the minimum degree of the graph. ${\displaystyle \lambda (G)=2}$

properties

• 

  A 2-edge connected graph
  If , then where is the node connection number and the minimum degree of the graph . ${\displaystyle |G|\geq 2}$ ${\displaystyle \delta (G)\geq \lambda (G)\geq \kappa (G)}$ ${\displaystyle \kappa (G)}$ ${\displaystyle \delta (G)}$ ${\displaystyle G}$
• ${\displaystyle G}$is 2-fold edge-related if and only if it contains no bridge. ${\displaystyle G}$
• ${\displaystyle G}$is -fold edge-connected if and only if there are edge- disjoint paths between two corners . This statement is also known as the global version of Menger's Theorem . ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle k}$

Related terms

The k-connection is a term similar to the edge connection , except that only separators with an empty set of edges and any set of nodes are considered. The k-relationship gives a measure of how many nodes have to be removed from a graph so that it breaks down into different components. A term for directed graphs that is similar to the edge connection is the arc connection .

Algorithms

There is an algorithm which , in polynomial running time, determines the largest one for which a graph is edge-connected. A simple algorithm would determine the maximum flow from to for each pair of nodes , with the capacity of all edges of the graph set to 1 for both directions. A graph is -edge-connected if and only if the maximum flow from to for each pair is at least , so the minimum is - -flow among all node pairs . ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle (u,v)}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle k}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle (u,v)}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle (u,v)}$

If the number of nodes of the graph is then this simple algorithm would iterate the maximum flow problem, the maximum flow problem that can be solved in runtime . Hence the complexity of the simple algorithm described above is overall . ${\displaystyle n}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{5})}$

An improved algorithm solves the problem of maximum flow for each pair , being arbitrary while varying across all nodes. This reduces the complexity to . It can be further improved by an algorithm from Gabow, which has the runtime in the worst case . ${\displaystyle (u,v)}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{3})}$

The Karger-Stein variant of the Karger algorithm offers a faster randomized algorithm for determining the relationship between the graph and the expected running time . ${\displaystyle O(n^{2}\cdot \log ^{3}(n))}$

The related problem of finding a minimal -edge-connected exciting subgraph of a graph is NP-hard for . The subgraph must contain all nodes , but as few edges as possible , so that it is still connected after the edges have been removed . ${\displaystyle k}$ ${\displaystyle k\geq 2}$ ${\displaystyle k-1}$

literature

• Reinhard Diestel: graph theory . Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 pages).

Individual evidence

1. ↑ Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci. , 50 (2): 259-273, 1995.
2. ^ David R. Karger, Clifford Stein: A new approach to the minimum cut problem . In: Journal of the ACM . 43, No. 4, 1996, p. 601. doi : 10.1145 / 234533.234534 .
3. ^ MR Garey and DS Johnson. Computers and Intractability: a Guide to the Theory of NP Completeness . Freeman, San Francisco, CA, 1979.