Camino happens exactly once by each of the vertices of the graph. (You can not use all edges
).
In the mathematical field of graph theory, a Hamiltonian path in a graph is a path, a succession of adjacent edges, which visits all vertices of the graph once. If also the last vertex visited is adjacent to the first, the path is a Hamiltonian cycle.
The problem of finding a cycle (or path) Hamiltonian in an arbitrary graph is known to be NP-complete.
Roads and Hamiltonian cycles were named after William Rowan Hamilton, who invented the game of Hamilton, will release a toy that involves finding a Hamiltonian cycle on the edges of a graph of a dodecahedron. Hamilton solved this problem by using quaternions, but this solution does not generalize to all graphs.
A Hamiltonian path is a path that visits each vertex exactly once. A graph containing a Hamiltonian path is called a Hamiltonian cycle or Hamiltonian circuit if it is a cycle that visits each vertex exactly once (except the apex of which party and which arrives). A graph containing a Hamiltonian cycle is called a Hamiltonian graph.
can also say that Hamiltonian graphs are when they meet:
-Hamiltonian-circuit must be related, must be closed.
These concepts can be extended to directed graphs. Examples
The complete graph with more than 2 vertices is Hamiltonian.
All graphs are Hamiltonian cycles.
All Platonic solids, considered graphs are Hamiltonian.
Any Hamiltonian cycle can be converted into a Hamiltonian path by removing any of its vertices, but a Hamiltonian path in the cycle can be extended only if the end vertices are adjacent.
Bondy-Chvatal theorem
The best characterization of Hamiltonian graphs was given in 1972 by the Bondy-Chvatal theorem which generalizes the results previously found by GA Dirac. It basically says that a graph is Hamiltonian if there are enough edges. First we must define what is the lock of a graph.
Given a graph G with n vertices, the lock (cl (G)) is uniquely constructed from G by adding every edge uv if nonadjacent pair of vertices u and v holds that degree (v) + degree (u) ≥ n
A graph is Hamiltonian if and only if the lock graph is Hamiltonian.
Bondy-Chvatal (1972)
Like all complete graphs are Hamiltonian, all graphs which are Hamiltonian lock is complete. This result is based on the theorems of Dirac and Ore.
A graph with n vertices (n> 3) is Hamiltonian if every vertex has degree greater than or equal to n / 2.
Dirac (1952)
A graph with n vertices (n> 3) is Hamiltonian if the sum of the degrees of 2 non-adjacent vertices is greater than or equal to n.
Ore (1960)
However, there is a previous result of all these theorems.
A graph with n vertices (n ≥ 2) is Hamiltonian if the sum of the degrees of 2 vertices is greater than or equal to n-1. L. Redei
(1934)
As you can see, this theorem requested more than the previous hypothesis as the property of grade must be met for every vertex in the graph.
also spoken Hamiltonian path if not imposed return to the starting point, like a museum with a single door. For example, a horse can go all the squares of a chess board without passing twice for the same: it is a Hamiltonian path. Example of a Hamiltonian cycle in the graph of the dodecahedron.
Today, there are no known general methods for finding a Hamiltonian cycle in polynomial time, being force search gross of all possible paths or other methods too expensive. There are, however, methods to eliminate the existence of Hamiltonian cycles and paths in graphs small.
The problem of determining the existence of Hamiltonian cycles, enter all the NP-complete.
In computational complexity theory, the complexity class NP-complete is the subset of decision problems in NP such that any problem in NP can be reduced in each of the NP-complete problems. You could say that the NP-complete problems are NP hard problems and very likely not part of the complexity class P.
0 comments:
Post a Comment