Petersen's theorem
The set of Petersen is a mathematical theorem from graph theory. He states that every cubic graph contains a perfect match without a bridge. The set of Petersen is one of the earliest results of graph theory. It is named after the Danish mathematician Julius Petersen.
Set
The set of Petersen says:
That is, if in a graph, each node has exactly three adjacent edges and each edge can be extended to a circle, then there is a selection of edges that touches each node exactly once.
Evidence
It shows that the following applies to every cubic graph without bridges: For each set of nodes is the number of connected components in by the induced graph with an odd number of nodes is at most as large as the number of nodes in itself is followed by the theorem of Tutte that a perfect pairing has.
Let be a connected component with an odd number of nodes in the graph induced by. Next were called in and with the number of edges in the intersection of with the node. Provides summing the nodes in
The edges in at least identifies a node in. because
Is an odd number and an even number, it follows that an odd number must be. Since has no bridge, must apply.
Now let the total number of cutting edges from to. The number of connected components having an odd number of nodes according to the argument in the previous paragraph, a maximum third In the worst case, each edge controls with a node in a connected component with an odd number of nodes. It follows that, and the condition of Tutte's theorem are fulfilled.
History
The theorem was first stated and proved by Julius Petersen. It is considered one of the first results in the field of graph theory, and in 1891 published The theory of regular graphs in the essay. As of today, the original proof of Petersen is considered complicated. A number of simplifications led to the evidence of Orrin Frink (1926) and Dénes König ( 1936).
In current textbooks, the set of Petersen is treated as an application of Tutte's theorem.
Applications
- In a cubic graph with a perfect pairing of the edges form a 2- factor outside of the mating. At a certain orientation of the 2- factor, one can expand the edges of the pairing to two edges to a path of length three. This shows that each cubic graph can be covered without bridges with edge-disjoint paths of length three.
- Using the set of Petersen can also show that each maximum planar graph with edge-disjoint paths of the length may be three covered. Since the dual graph of such a graph is cubic and contains no bridges, one can find there a perfect pairing, which belongs in the original graph to two triangles that share an edge. These joint edges can be extended to paths of length three in a way that no edge appears in several of these extensions.
- A triangular lattice can be used to modify the set of Petersen so that a Hamiltonian path in the dual graph of the mesh exists.
Extensions
Number of perfect pairings in cubic graphs without bridge
From László Lovász and Michael Plummer has been suggested that every cubic graph ( in ) has an exponential number of perfect pairings with knots and without bridge. This conjecture was proved in 1979 for bipartite graphs of Marc Voorhoeve, and 2012 for planar graphs Maria Chudnovsky and Paul Seymour. The general case was finally 2011 by Lois Esperet among others proved. Here it was shown that every cubic graph has at least a perfect pairings without bridges and nodes.
Algorithmic versions
From Therese Biedl et al efficient variants of the set of algorithmic Petersen were examined. Based on Frink evidence, they developed an algorithm for computing a perfect pairing in cubic graphs without bridges with knots. Is it also a planar graph is the same attachment to an algorithm. Subsequent improvements to the data structures used in the algorithm, the running time can be further improved. Further improvements led to an algorithm. When using randomized data structures can search the term even improve upon.