Hamilton cycle problem

A Hamilton cycle is a closed path in a graph that contains every node exactly once. The question of whether such a circle exists in a given graph is an important problem in graph theory . In contrast to the easily solvable Euler circle problem , in which a circle is sought that runs through all edges exactly once, the Hamilton circle problem is NP-complete .

A distinction is made between the directed Hamilton cycle problem in directed graphs and the undirected Hamilton cycle problem in undirected graphs. A special case of the Hamilton circle problem is the traveling salesman problem , in which the question is asked for a shortest Hamilton circle in a graph with edge weights.

history

The dodecahedron, like all Platonic solids , is Hamiltonian.

The problem is named after the Irish astronomer and mathematician Sir William Rowan Hamilton , who invented the game “The Icosian Game ” in 1857 (and later improved it to “Traveller's Dodecahedron or A Voyage Round The World”).

The “Traveller's Dodecahedron” consists of a wooden, regular dodecahedron , the 20 nodes being associated with names of well-known cities. The goal is to find an itinerary along the edges of the dodecahedron that visits each city exactly once and ends where it begins.

Initially, the task appears to be similar to the Königsberg bridge problem solved by Leonhard Euler (negative) in 1736 , a special case of the Euler's circle problem and the laying of the foundation stone for graph theory. While there are particularly efficient solution algorithms for the Euler circle problem, it is known that both variants of the Hamilton circle problem are problems that are particularly difficult to solve algorithmically. Both the directed and the undirected variant of the Hamilton circle problem belong to the list of the 21 classical NP-complete problems , for which Richard M. Karp proved to belong to this class of problems in his famous 1972 article.

Definitions

Let be a graph with nodes (or vertices) and edges . ${\displaystyle G=(V,E)}$ ${\displaystyle |V|=n}$ ${\displaystyle |E|=m}$

${\displaystyle G}$is called Hamiltonian if it allows a Hamilton cycle, d. i.e., if there is a circle in that contains all the nodes from . A Hamilton path is a path in that contains all nodes from . If Hamilton has paths but no Hamiltonian, it is called semi-Hamiltonian . ${\displaystyle G}$ ${\displaystyle V}$ ${\displaystyle G}$ ${\displaystyle V}$ ${\displaystyle G}$ ${\displaystyle G}$

To the power of a graph : For a graph and denotes the graph in which two nodes are adjacent if and only if they are at a distance less than or equal . Apparently applies . ${\displaystyle G}$ ${\displaystyle d\in \mathbb {N} }$ ${\displaystyle G^{d}}$ ${\displaystyle V}$ ${\displaystyle G}$ ${\displaystyle d}$ ${\displaystyle G=G^{1}\subseteq G^{2}\subseteq G^{3}\subseteq \ldots }$

An arbitrary tuple of natural numbers is called Hamiltonian if every graph with vertices and pointwise larger degree sequence is Hamiltonian. A degree sequence is called point-wise greater than if applies to all . ${\displaystyle (a_{1},\dotsc ,a_{n})}$ ${\displaystyle n}$ ${\displaystyle (d_{1},\dotsc ,d_{n})}$ ${\displaystyle (a_{1},\dotsc ,a_{n})}$ ${\displaystyle d_{i}\geq a_{i}}$ ${\displaystyle i}$

A graph is called hypohamiltonian if it does not have a Hamiltonian circle, but for each of its nodes there is a circle that contains all other nodes. ${\displaystyle G}$

The Hamilton closure of a graph is the upper graph of edges with an identical set of nodes and additional iteratively inserted edges that connect nonadjacent nodes with degree sums greater than or equal to one another, as long as this is possible. The Hamilton closure of a graph is unique. ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle n}$

properties

Every Hamilton cycle can be converted into a Hamilton path by removing one of its edges . However, a Hamilton path can only be expanded to a Hamilton cycle if its end nodes are adjacent.

All Hamiltonian graphs are 2- connected , but a 2-connected graph does not have to be Hamiltonian, for example the Petersen graph .

An Eulerian graph , i.e. a connected graph in which every node has an even degree , necessarily has an Euler circle, with the closed path running through every edge exactly once . This path corresponds to a Hamilton circle in the associated edge graph , so that the edge graph of every Eulerian graph is a Hamiltonian graph. Edge graphs can have other Hamilton circles that do not correspond to Euler circles, and in particular the edge graph of every Hamiltonian graph is itself Hamiltonian, regardless of whether the graph is an Eulerian graph.

A tournament graph with more than two nodes is a Hamiltonian graph if and only if it is strongly connected .

The number of different Hamilton cycles in a complete undirected graph with nodes is and in a complete directed graph with nodes . Hamilton circles, which are the same except for their starting node, are not counted multiple times. ${\displaystyle n}$ ${\displaystyle {\tfrac {1}{2}}\cdot (n-1)!}$ ${\displaystyle n}$ ${\displaystyle (n-1)!}$

Theorems about Hamilton circles

What conditions to a Graphen with result in the existence of a Hamilton cycle ? Particularly important theorems are listed chronologically below. ${\displaystyle G}$ ${\displaystyle n\geq 3}$

sentences

• GA Dirac (1952), the historical starting point for the discovery of a gaA series of conditions: Every simple graph with minimum degree at least has a Hamilton cycle . ${\displaystyle G}$ ${\displaystyle {\tfrac {n}{2}}}$

• WT Tutte (1956): Everyone 4 togetherhanging planar graph has a Hamilton circle .

• O. Ore (1960): If the sum of the degrees of each pair of one of the adjacent non-nodes of a simple graph least , it is Hamiltonian. ${\displaystyle n}$ ${\displaystyle G}$

• L. Pósa (1962) with a generalization of earlier results by GA Dirac and Ø. Ore: Be a simple graph with nodes . It is also true for all natural numbers that the number of nodes with degrees is less than . If is odd, let the number of all nodes with degree be less than or equal . Then has a Hamilton cycle. ${\displaystyle G}$ ${\displaystyle n\geq 3}$ ${\displaystyle k<{\tfrac {n-1}{2}}}$ ${\displaystyle v\leq k}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle v\leq {\tfrac {n-1}{2}}}$ ${\displaystyle {\tfrac {n-1}{2}}}$ ${\displaystyle G}$

• P. Erdős (1962): Sci ${\displaystyle G_{l}^{n}(k)}$a simple graph with nodes and edges. Each knot in have a degree . It applies and it is . ${\displaystyle n}$ ${\displaystyle l}$ ${\displaystyle P}$ ${\displaystyle G_{l}^{n}(k)}$ ${\displaystyle v(P)\geq k}$ ${\displaystyle 1\leq k<{\tfrac {n}{2}}}$ ${\displaystyle l(k,n)=1+\max _{k\leq t<{\tfrac {n}{2}}}{\binom {n-t}{2}}+t^{2}}$ Then:
  • 1. Every graph with has a Hamilton cycle. ${\displaystyle G_{l}^{n}(k)}$ ${\displaystyle l\geq l(k,n)}$
  • 2. There is a graph that does not have a Hamilton cycle. ${\displaystyle G_{l(k,n)-1}^{n}(k)}$

• V. Chvátal (1972): A tuple of natural numbers with exactly then Hamiltonian if for every where: . ${\displaystyle (a_{1},\dotsc ,a_{n})}$ ${\displaystyle a_{1}\leq \cdots \leq a_{n}<n}$ ${\displaystyle i<{\tfrac {n}{2}}}$ ${\displaystyle a_{i}\leq i\Rightarrow a_{n-i}\geq n-i}$

• V. Chvátal and P. Erdős (1972): If k- is connected and the thickness of any set of independent nodes is off , then it is Hamiltonian. ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle \leq k}$ ${\displaystyle G}$

• H. Fleischner (1974): If 2-connected, then has a Hamilton cycle. ${\displaystyle G}$ ${\displaystyle G^{2}}$

• JA Bondy and V. Chvátal (1976): is Hamiltonian if and only if his Hamilton degree is Hamiltonian. ${\displaystyle G}$

Other sufficient properties

A graph is Hamiltonian if it is

• is a complete graph with at least three nodes .
• Is the edge graph of an Eulerian or Hamiltonian graph.
• has a subgraph from which only edges have been removed, which is the edge graph of an Eulerian or Hamiltonian graph.
• is a pan-cyclic graph .

Necessary properties

If a graph has a Hamilton cycle, then

• it has no cut knot .
• he has no bridge .
• its block graph is an isolated node .
• he has a 2 factor .
• it is 2- connected .
• his minimum degree is at least 2.
• its diameter is at most . ${\displaystyle {\tfrac {n}{2}}}$
• is he 1 tough, i.e. H. for every non-empty set of nodes , the graph without these nodes has at most connected components. ${\displaystyle s}$ ${\displaystyle s}$
• is path-tough, d. H. for every node, the graph without this node has a Hamiltonian path, that is, a path that contains all the nodes of the graph.

assumptions

In this context, these important - not generally resolved - assumptions were made :

• DW Barnette (1969): Every 3-connected bipartite cubic planar graph is Hamiltonian.

• P. Seymour (1974): If the minimum degree is , then has a Hamilton cycle with . For this corresponds to the theorem of GA Dirac, 1952, (see above). The statement for was already suspected in 1963 by L. Pósa and was proven in 1996 for sufficiently large by J. Komlós , GN Sárközy & E. Szemerédi . ${\displaystyle G}$ ${\displaystyle \delta (G)\geq {\tfrac {k}{k+1}}n}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle H^{k}\subseteq G}$ ${\displaystyle k=1}$
  ${\displaystyle k=2}$ ${\displaystyle n}$

See also

• A special case of the Hamilton cycle is the so-called Springer problem .
• The Gray codes are the solutions to the Hamilton circle problem for a hypercube.

Individual evidence

1. ↑ ^{a b c d} Horst Sachs : Introduction to the theory of finite graphs (Volume 1) . 1st edition. BSB BG Teubner Verlagsgesellschaft, Leipzig 1970.

Web links

Commons : Hamiltonian paths  - collection of images, videos and audio files

• Eric W. Weisstein. "Hamiltonian Cycle." From MathWorld --A Wolfram Web Resource (English)
• Puzzle Museum: Hamilton's games "The Icosian Game" and "Traveller's Dodecahedron" (English)