Hamiltonian Path
From Math Images
m |
|||
Line 8: | Line 8: | ||
Mathematicians have not yet found a simple and quick way to find Hamiltonian paths or cycles in any graph, but they have developed some ideas that make the search easier. <ref>DeLeon, Melissa, "A Study of Sufficient Conditions for Hamiltonian Cycles". Department of Mathematics and Computer Science, Seton Hall University.</ref><ref>West, Douglas B., ''Introduction to Graph Theory''. Upper Saddle River: Prentice Hall Inc, 1996.</ref> The More Mathematical Explanation lays out some of the theorems that determine whether a graph is Hamiltonian or not, as well as a discussion of the NP-completeness of finding Hamiltonian paths. | Mathematicians have not yet found a simple and quick way to find Hamiltonian paths or cycles in any graph, but they have developed some ideas that make the search easier. <ref>DeLeon, Melissa, "A Study of Sufficient Conditions for Hamiltonian Cycles". Department of Mathematics and Computer Science, Seton Hall University.</ref><ref>West, Douglas B., ''Introduction to Graph Theory''. Upper Saddle River: Prentice Hall Inc, 1996.</ref> The More Mathematical Explanation lays out some of the theorems that determine whether a graph is Hamiltonian or not, as well as a discussion of the NP-completeness of finding Hamiltonian paths. | ||
+ | |||
|ImageDesc=== Theorems == | |ImageDesc=== Theorems == | ||
There are a number of ways to tell if a graph will have a Hamiltonian path or cycle. For some simpler graphs, it can be done by hand. However, with larger graphs, a direct inspection of the graph will not provide a solution quickly. Furthermore, if a Hamiltonian path or cycle didn't exist, a mathematician would have to exhaust all of the possible paths to prove it. That could surely take a lifetime for large and difficult graphs. As a result, many theorems were developed to help find the existence of a Hamiltonian cycle and path. Two useful theorems (Dirac from 1952, and Bondy-Chvatal from 1974) are presented below. | There are a number of ways to tell if a graph will have a Hamiltonian path or cycle. For some simpler graphs, it can be done by hand. However, with larger graphs, a direct inspection of the graph will not provide a solution quickly. Furthermore, if a Hamiltonian path or cycle didn't exist, a mathematician would have to exhaust all of the possible paths to prove it. That could surely take a lifetime for large and difficult graphs. As a result, many theorems were developed to help find the existence of a Hamiltonian cycle and path. Two useful theorems (Dirac from 1952, and Bondy-Chvatal from 1974) are presented below. | ||
Line 14: | Line 15: | ||
If simple graph ''G'' has ''n'' ≥ 3 vertices and ''m'' ≥ ''n''/2, where ''m'' is the minimum vertex degree in ''G'', then ''G'' is a Hamiltonian graph. In words, if the graph has three vertices or more, '''and''' the degree of the vertex with the smallest degree is greater than half the number of vertices, then the graph has a Hamiltonian cycle. <ref>Bondy, J. A., U. S. R. Murty, "Graph Theory with Applications"</ref> | If simple graph ''G'' has ''n'' ≥ 3 vertices and ''m'' ≥ ''n''/2, where ''m'' is the minimum vertex degree in ''G'', then ''G'' is a Hamiltonian graph. In words, if the graph has three vertices or more, '''and''' the degree of the vertex with the smallest degree is greater than half the number of vertices, then the graph has a Hamiltonian cycle. <ref>Bondy, J. A., U. S. R. Murty, "Graph Theory with Applications"</ref> | ||
- | + | ||
====Proof==== | ====Proof==== | ||
{{hide|1= | {{hide|1= | ||
Line 35: | Line 36: | ||
:<math>T = \{v_{i} | v_{i}v \in E\}</math>. | :<math>T = \{v_{i} | v_{i}v \in E\}</math>. | ||
- | Note that we are only considering edges in the graph ''G'', not in ''G'' + ''uv''. Finally, to add a little extra notation, we say that ''S'' | + | Note that we are only considering edges in the graph ''G'', not in ''G'' + ''uv''. Finally, to add a little extra notation, we say that ''S'' ∪ ''T'' is all the vertices that are in either ''S'' or ''T''. ''S'' ∩ ''T'' is all of the vertices that are in both ''S'' and ''T''. To denote the number of objects in a set, mathematicians use an absolute value sign. For example, <nowiki>|</nowiki>''S''<nowiki>|</nowiki> is the number of vertices in the set ''S''. |
By this defintion, | By this defintion, | ||
Line 103: | Line 104: | ||
Since in the general proof, all of these numbers were replaced with variables, we had to use this very complex method. | Since in the general proof, all of these numbers were replaced with variables, we had to use this very complex method. | ||
- | |||
}} | }} | ||
}} | }} | ||
===Bondy-Chvátal Theorem=== | ===Bondy-Chvátal Theorem=== | ||
Let ''G'' be a simple graph and let ''n'' be the number of vertices in ''G''. Let ''u'' and ''v'' be two nonadjacent vertices in ''G'' such that ''d''(''u'') + ''d''(''v'') ≥ ''n''. Then ''G'' is Hamiltonian if and only if ''G'' + ''uv'' is Hamiltonian. | Let ''G'' be a simple graph and let ''n'' be the number of vertices in ''G''. Let ''u'' and ''v'' be two nonadjacent vertices in ''G'' such that ''d''(''u'') + ''d''(''v'') ≥ ''n''. Then ''G'' is Hamiltonian if and only if ''G'' + ''uv'' is Hamiltonian. | ||
- | + | ||
====Proof==== | ====Proof==== | ||
{{hide|1= | {{hide|1= | ||
Line 121: | Line 121: | ||
{{hide|1= | {{hide|1= | ||
[[Image:schugygraph3.jpg|right|thumb|250px|A simple non-Hamiltonian graph ''G'', and an added edge 25. The Bondy-Chvátal theorem applies to this edge, since ''d(''2'')'' + ''d(''5'')'' ≥ 6.]]Consider the graph to the right. First, we find two vertices such that the sum of their degrees is greater than or equal to the total number of vertices. Vertices 2 and 5 apply, since they are not already attached, and ''d(2)'' + ''d(5)'' = 3 + 3 = 6 ≥ 6 = ''n''. So we add the edge 25 to the graph ''G''. However, this graph is non-Hamiltonian because there is only one way we can get to vertex 1, and no way out. So no Hamiltonian cycle can be made in ''G'' + 25. Thus ''G'' + 25 is non-Hamiltonian and by the Bondy-Chvátal theorem, so is ''G''. | [[Image:schugygraph3.jpg|right|thumb|250px|A simple non-Hamiltonian graph ''G'', and an added edge 25. The Bondy-Chvátal theorem applies to this edge, since ''d(''2'')'' + ''d(''5'')'' ≥ 6.]]Consider the graph to the right. First, we find two vertices such that the sum of their degrees is greater than or equal to the total number of vertices. Vertices 2 and 5 apply, since they are not already attached, and ''d(2)'' + ''d(5)'' = 3 + 3 = 6 ≥ 6 = ''n''. So we add the edge 25 to the graph ''G''. However, this graph is non-Hamiltonian because there is only one way we can get to vertex 1, and no way out. So no Hamiltonian cycle can be made in ''G'' + 25. Thus ''G'' + 25 is non-Hamiltonian and by the Bondy-Chvátal theorem, so is ''G''. | ||
- | |||
}} | }} | ||
===Using the Two Theorems=== | ===Using the Two Theorems=== | ||
- | |||
- | |||
[[Image:diracgraph.png|right|thumb|250px|Here is a graph with ''n'' =8 and ''m'' = 4. The Bondy-Chvátal theorem does not really help us, even though it applies. Dirac's theorem gives us a simple check for the existence of a Hamiltonian cycle.]]Dirac's theorem is useful for simple graphs. For example, consider the graph in figure 1. Applying the Bondy-Chvátal theorem to this graph would not really help. Even though the theorem applies, one must still determine whether a Hamiltonian cycle is in this mess at all. However, Dirac's theorem provides a simple answer. A quick count of the vertices shows that ''n'' = 8 ≥ 3. Another quick inspection reveals that each vertex has a degree of 4, so ''m'' = 4. Since ''m'' = 4 ≥ 8/2 = ''n''/2, Dirac's theorem applies, and this graph has a Hamiltonian cycle. Again, there is still the matter of finding the Hamiltonian cycle, but at least we now know one is there. | [[Image:diracgraph.png|right|thumb|250px|Here is a graph with ''n'' =8 and ''m'' = 4. The Bondy-Chvátal theorem does not really help us, even though it applies. Dirac's theorem gives us a simple check for the existence of a Hamiltonian cycle.]]Dirac's theorem is useful for simple graphs. For example, consider the graph in figure 1. Applying the Bondy-Chvátal theorem to this graph would not really help. Even though the theorem applies, one must still determine whether a Hamiltonian cycle is in this mess at all. However, Dirac's theorem provides a simple answer. A quick count of the vertices shows that ''n'' = 8 ≥ 3. Another quick inspection reveals that each vertex has a degree of 4, so ''m'' = 4. Since ''m'' = 4 ≥ 8/2 = ''n''/2, Dirac's theorem applies, and this graph has a Hamiltonian cycle. Again, there is still the matter of finding the Hamiltonian cycle, but at least we now know one is there. | ||
Line 132: | Line 129: | ||
The Bondy-Chvátal theorem is an "if and only if" statement. Therefore, we can determine whether or not any graph is Hamiltonian, depending on its sole condition. Dirac's theorem is only an "if" statement. This means that the theorem does not apply to every graph. If the graph doesn't meet the theorem requirements that ''m'' ≥ ''n''/2 and ''n'' = 2, then we cannot say anything about the graph at all. | The Bondy-Chvátal theorem is an "if and only if" statement. Therefore, we can determine whether or not any graph is Hamiltonian, depending on its sole condition. Dirac's theorem is only an "if" statement. This means that the theorem does not apply to every graph. If the graph doesn't meet the theorem requirements that ''m'' ≥ ''n''/2 and ''n'' = 2, then we cannot say anything about the graph at all. | ||
- | |||
===Extension of the Bondy-Chvátal Theorem=== | ===Extension of the Bondy-Chvátal Theorem=== | ||
- | |||
There are extensions of the Bondy-Chvátal theorem that have great use for Hamiltonian paths. They relate to a new concept called the '''closure''' of a graph, denoted ''c(G)''. | There are extensions of the Bondy-Chvátal theorem that have great use for Hamiltonian paths. They relate to a new concept called the '''closure''' of a graph, denoted ''c(G)''. | ||
Line 141: | Line 136: | ||
In many cases, ''c(G)'' is a complete graph, one where each vertex is adjacent to every other. Complete graphs with three or more vertices are definitely Hamiltonian, since any necessary edge to complete the cycle is always present. Thus, if ''c(G)'' is complete, then ''G'' is Hamiltonian. This version of the theorem applies to the most cases and is the easy to calculate. For example, consider the graph in figure 2 again. Since the degree of every vertex is 4, then it clear that ''d''(''u'') + ''d''(''v'') = 4 + 4 = 8 ≥ ''n''. So, by the extended Bondy-Chvátal theorem, we can make a new edge between every pair of non-adjacent vertices to make the closure of the graph ''c''(''G''). This definitely creates a complete graph, and so the graph is Hamiltonian. This agrees with Dirac's theorem. | In many cases, ''c(G)'' is a complete graph, one where each vertex is adjacent to every other. Complete graphs with three or more vertices are definitely Hamiltonian, since any necessary edge to complete the cycle is always present. Thus, if ''c(G)'' is complete, then ''G'' is Hamiltonian. This version of the theorem applies to the most cases and is the easy to calculate. For example, consider the graph in figure 2 again. Since the degree of every vertex is 4, then it clear that ''d''(''u'') + ''d''(''v'') = 4 + 4 = 8 ≥ ''n''. So, by the extended Bondy-Chvátal theorem, we can make a new edge between every pair of non-adjacent vertices to make the closure of the graph ''c''(''G''). This definitely creates a complete graph, and so the graph is Hamiltonian. This agrees with Dirac's theorem. | ||
- | + | ||
== NP Completeness Proof == | == NP Completeness Proof == |
Current revision
Hamiltonian Path |
---|
Hamiltonian Path
- In Graph Theory, a Hamiltonian path is a series of vertices and edges such that every vertex is included only once.
Contents |
Basic Description
All graphs have vertices and edges. Now, imagine traveling from vertex to vertex along the edges. We can mathematically characterize this "trip around the graph" with a list in order of the vertices and edges that make up the "trip". This series of vertices and edges is called a walk. In a walk, there are very few restrictions, so the edges or vertices can be visited any number of times. A walk where a vertex is not repeated is a called a path. A Hamiltonian path visits all the vertices exactly once.If we extend a Hamiltonian path to connect the ending vertex to the starting vertex by means of an existing edge, then we have created something new—a Hamiltonian cycle. A cycle is a walk that connects back to its starting vertex, while a Hamiltonian cycle must hit all of the vertices exactly once before coming back to the starting vertex. If a graph has a Hamiltonian cycle, then it is called a Hamiltonian graph.
Mathematicians have not yet found a simple and quick way to find Hamiltonian paths or cycles in any graph, but they have developed some ideas that make the search easier. ^{[1]}^{[2]} The More Mathematical Explanation lays out some of the theorems that determine whether a graph is Hamiltonian or not, as well as a discussion of the NP-completeness of finding Hamiltonian paths.
A More Mathematical Explanation
Theorems
There are a number of ways to tell if a graph will have a Hamiltonian path or cycle. For some simpler graphs, it can be done by hand. However, with larger graphs, a direct inspection of the graph will not provide a solution quickly. Furthermore, if a Hamiltonian path or cycle didn't exist, a mathematician would have to exhaust all of the possible paths to prove it. That could surely take a lifetime for large and difficult graphs. As a result, many theorems were developed to help find the existence of a Hamiltonian cycle and path. Two useful theorems (Dirac from 1952, and Bondy-Chvatal from 1974) are presented below.
Dirac's Theorem
If simple graph G has n ≥ 3 vertices and m ≥ n/2, where m is the minimum vertex degree in G, then G is a Hamiltonian graph. In words, if the graph has three vertices or more, and the degree of the vertex with the smallest degree is greater than half the number of vertices, then the graph has a Hamiltonian cycle. ^{[3]}
Proof
An Example
Bondy-Chvátal Theorem
Let G be a simple graph and let n be the number of vertices in G. Let u and v be two nonadjacent vertices in G such that d(u) + d(v) ≥ n. Then G is Hamiltonian if and only if G + uv is Hamiltonian.
Proof
An Example
Using the Two Theorems
Dirac's theorem is useful for simple graphs. For example, consider the graph in figure 1. Applying the Bondy-Chvátal theorem to this graph would not really help. Even though the theorem applies, one must still determine whether a Hamiltonian cycle is in this mess at all. However, Dirac's theorem provides a simple answer. A quick count of the vertices shows that n = 8 ≥ 3. Another quick inspection reveals that each vertex has a degree of 4, so m = 4. Since m = 4 ≥ 8/2 = n/2, Dirac's theorem applies, and this graph has a Hamiltonian cycle. Again, there is still the matter of finding the Hamiltonian cycle, but at least we now know one is there.Unfortunately, Dirac's theorem applies to fewer graphs than the Bondy-Chvátal theorem. For example, consider the graph in the hidden example section. Dirac's Theorem does not apply since the minimum vertex degree is not greater than or equal to n/2, but Bondy-Chvátal works.
The Bondy-Chvátal theorem is an "if and only if" statement. Therefore, we can determine whether or not any graph is Hamiltonian, depending on its sole condition. Dirac's theorem is only an "if" statement. This means that the theorem does not apply to every graph. If the graph doesn't meet the theorem requirements that m ≥ n/2 and n = 2, then we cannot say anything about the graph at all.
Extension of the Bondy-Chvátal Theorem
There are extensions of the Bondy-Chvátal theorem that have great use for Hamiltonian paths. They relate to a new concept called the closure of a graph, denoted c(G).
To create the c(G), we need to consider all of the pairs of nonadjacent vertices u and v such that d(u) + d(v) ≥ n. Once all of these pairs are joined, c(G) has been created. The extension of the Bondy-Chvátal states that if c(G) is Hamiltonian then so is G. Surprisingly, this requires little proof. This is because the Bondy-Chvátal theorem applies to each new edge. We can thus apply that theorem recursively until we obtain c(G). More simply stated, if the Bondy-Chvátal theorem can add one helpful edge uv, there is no reason that we cannot add more. The closure of the graph is just a graph where all the helpful edges have been added.
In many cases, c(G) is a complete graph, one where each vertex is adjacent to every other. Complete graphs with three or more vertices are definitely Hamiltonian, since any necessary edge to complete the cycle is always present. Thus, if c(G) is complete, then G is Hamiltonian. This version of the theorem applies to the most cases and is the easy to calculate. For example, consider the graph in figure 2 again. Since the degree of every vertex is 4, then it clear that d(u) + d(v) = 4 + 4 = 8 ≥ n. So, by the extended Bondy-Chvátal theorem, we can make a new edge between every pair of non-adjacent vertices to make the closure of the graph c(G). This definitely creates a complete graph, and so the graph is Hamiltonian. This agrees with Dirac's theorem.
NP Completeness Proof
The full proof for the NP-completeness of finding a Hamiltonian path is long and difficult. However, the outline of those proofs are not as difficult. If it is known that problem A is NP-complete, and problem A can be transformed into problem B, then problem B is also NP-complete. This method doesn't have to be limited to only two problems. A whole chain of transformations can occur. This is exactly how finding a Hamiltonian path was shown to be NP-complete. The seed is a problem in logic, called Satisfiability. This problem involves finding a series of true statements such that the truth of larger statements is satisfied. This problem was proved NP-complete in 1972. This problem was then transformed into finding a chromatic number of a graph, then to finding an maximal independent set of vertices, then to finding a vertex cover of a graph, then to finding a digraph Hamiltonian path, and finally to finding a Hamiltonian path any graph. These transformations had been proved by 1985.^{[4]}
Why It's Interesting
The Traveling Salesman problem solution has roots in finding Hamiltonian paths and cycles. In that problem, each edge of a graph has a number associated with it, called a weight. The salesman needs to take the Hamiltonian path or cycle with the lowest weight in order to minimize the cost of his travels. So once someone has an algorithm to find a Hamiltonian cycle, its a matter of finding the optimum cycle to solve the Traveling Salesman problem.However, an algorithm for finding a Hamiltonian path or cycle can also be found from an algorithm for the Traveling Salesman problem.
To do this, take a graph G with n vertices and the complete graph with n vertices, called K_{n}. Since K_{n} is complete, G is a subgraph of it. So all the edges in G are also contained in the complete graph. Now, if an edge exists in G, we give it a weight of 0 in the complete graph. If it doesn't exist in G, give it a weight 1 in the complete graph. Now, we can apply our assumed Traveling Salesman algorithm to this complete graph. Any Hamiltonian path in the complete graph with a total weight of 0 will be a Hamiltonian path in G. Thus, a Hamiltonian path or cycle can be found with a Traveling Salesman algorithm. All the transformations of problems from one to another listed above in the NP-completeness section look something like this.
Another application of Hamiltonian paths is finding a knight's tour. The knight's tour is a challenge to have a knight move to every space on a chess board only once. It is the equivalent of finding a Hamiltonian path in the graph describing all the possible moves of the knight on the chessboard. As it turns out, this graph of knight's moves has a Hamiltonian path, as shown by the animation. In fact, both a Hamiltonian path and a Hamiltonian cycle can be found. There are 33,439,123,484,294 knight's tours on an 8 by 8 chess board. ^{[5]}
Teaching Materials
- There are currently no teaching materials for this page. Add teaching materials.
References
- ↑ DeLeon, Melissa, "A Study of Sufficient Conditions for Hamiltonian Cycles". Department of Mathematics and Computer Science, Seton Hall University.
- ↑ West, Douglas B., Introduction to Graph Theory. Upper Saddle River: Prentice Hall Inc, 1996.
- ↑ Bondy, J. A., U. S. R. Murty, "Graph Theory with Applications"
- ↑ West, Douglas A., Introduction to Graph Theory. Published by Prentice Hall Inc.
- ↑ Martin Loebbing; Ingo Wegener (1996). "The Number of Knight's Tours Equals 33,439,123,484,294 — Counting with Binary Decision Diagrams". The Electronic Journal of Combinatorics 3
- Weisstein, Eric W. "Hamiltonian Graph." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/HamiltonianGraph.html
- Weisstein, Eric W. "Hamiltonian Cycle." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/HamiltonianCycle.html
Future Directions for this Page
- Maybe add more that is not in the more mathematical section
- more applications of Hamiltonian paths?
- There's a good applet here, find the terms of use for it?
- Create a Traveling Salesman Problem page -- not as a helper page, but a full-fledged page for extended explanation.
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.