Hamiltonian Path

From Math Images

Jump to: navigation, search


Hamiltonian Paths and Cycles
Field: Graph Theory
Created By: Jorin Schug
Website: [ http://mathforum.org/mathimages/index.php/User:Jschug1]

Hamiltonian Paths and Cycles

In Graph Theory, a Hamiltonian path is a series of edges that visits every vertex of a graph exactly once.


Contents

Basic Description

At its very basis, a Hamiltonian Path is a path along a graph that will visit each vertex (also referred to as a node) exactly once. If a Hamiltonian Path can be created for a graph, then it is determined to be a traceable graph.

Also derived from Hamiltonian paths are Hamiltonian cycles, also known as Hamiltonian Circuits, which follow the same rules, along with the additional rule that the path must return to the node that it began at on the graph. There is no specific characterization of a Hamiltonian Path -- although there is a list of sufficient conditions that they must meet. If a graph has a Hamiltonian cycle, then it is determined to be a Hamiltonian Graph [1].

A More Mathematical Explanation

Theorems

There are a number of ways to tell if a graph will have a Hamiltonian path or cycle. [...]

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 Hamiltonian path or cycle didn't exist, a mathematician would have to exhaust all of the possible paths to prove that. That could surely take a lifetime for difficult graphs. As a result, many theorems were developed to help find the existence of a Hamiltonian cycle and path. Here are two theorems (Dirac from 1952, and Bondy-Chvatal from 1974) and their proofs for determining whether a graph has a Hamiltonian cycle or not. These do not apply to all cases, but the second theorem applies to more than the first.

Dirac's Theorem

If simple graph G has n ≥ 3 vertices and m ≥ n/2, then G is a Hamiltonian graph. In words, if the graph has more than three vertices, 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. [2].

Proof

If this proof is confusing, then there is a particular example below, which illustrates all the concepts of the proof.

In this proof, n denotes the total number of vertices and m represents the lowest vertex degree of the graph. For more helpful terms and concepts, consult the page about the basics of Graph Theory.

We will prove Dirac's Theorem by assuming it is incorrect, and finding a contradiction. So, assume that if n ≥ 3 and m ≥ n/2, then G is non-Hamiltonian. Now, we specially define a graph and sets of vertices in that graph in a particular way so that the result will almost be in plain sight.

First, let a simple graph G be a maximal non-Hamiltonian graph. In other words, we can create a Hamiltonian path in G, but we do not have that one last edge to connect the path and make it a Hamiltonian cycle. If one well-placed edge were to be added to G, then the new graph would be a Hamiltonian graph! Let u and v be two non-adjacent vertices in G, and to make a Hamiltonian cycle, we add the new edge uv. This new graph has a name G + uv, since we are adding an edge to vertices u and v to make a Hamiltonian cycle. Remember, since this graph is simple, it has no loops or unnecessary edges.

Now, since G is non-Hamiltonian, any Hamiltonian cycle in G + uv must go through the edge uv. Since vertices u and v must be part of a Hamiltonian cycle, we can make a cycle in G + uv that begins at u and ends at v. Let's call this path uv1v2...v. We will make more definitions based on this path.

Second, we consider two sets of vertices. We create the set S to be all of the vertices such that the next vertex along the path has an edge connecting it with the vertex u in the graph G, not G + uv. This edge does not necessarily have to be in the Hamiltonian path, but it just has to connect to the vertex u. In math language, that looks lik this:

S = \{v_{i} | uv_{i + 1} \in E\}

where E is the set of edges in G. Remember, the vertex u is the beginning of the Hamiltonian path. The set T is defined similarly. T is all of the vertices that have edges connecting the vertex v in G, which is the last vertex of the path. In math language:

T = \{v_{i} | v_{i}v \in E\}.

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\cupT is all the vertices that are in either S or T. S\capT is all of the vertices that are in both S and T. To denote number of objects in a set, mathematicians use an absolute value sign. For example, |S| is the number of vertices in the set S.

By this defintion,

|S| + |T| = |S\cup T| + |S\cap T|

This is true because the union of the two sets does not take into account the fact that there are doubles of the vertices that S and T have in common. So the intersection must be added to take the doubles into account.

Now all of these names and definitions will actually get us somewhere!

We know that

v \notin S\cup T \Rightarrow |S\cup T| < n.

The vertex v is not in G becuase it is a simple graph. The vertex does not border itself, since there can be no loops, and the edge uv does not exist in G. Thus v meets neither definition of S or T. We also know that

|S\cap T| = 0.

This is because if a vertex were in both S and T, we could create a Hamiltonian cycle in G. To make this supposed cycle, we assume that some vertex vi is in both S and T. Thus it is adjacent to T, and the next vertex along the path, vi + 1 is adjacent to u. So we can construct a Hamiltonian cycle with the vertex sequence uv1...vivvn - 1...vi + 1u. The existence of this path if forbidden by our assumption, so no such vi exists.

Now we also know that, by definition,

|S| = d(u) and |T| = d(v)

For the final step, we consider d(u) + d(v). By substitution,

d(u) + d(v) = |S| + |T|
d(u) + d(v) = |S \cup T| + |S \cap T|
d(u) + d(v) = |S \cup T| < n

So d(u) + d(v) < n. But this contradicts the fact m ≥ n/2, because if

d(u) > \frac{n} {2} \Rightarrow d(v) < \frac{n} {2}
And vice versa. Since either d(u) or d(v) has to be less than n/2, then m is definitely less than n/2. This contradicts our assumption that m ≥ n/2. We have found non-Hamiltonian graphs where m ≤ n/2, which is the opposite of our assumption. Since we have found the contradiction in the negation of Dirac's Theorem, we have proved the truth of Dirac's Theorem!

An Example

A simple non-Hamiltonian graph G, and a Hamiltonian graph G + 34
A simple non-Hamiltonian graph G, and a Hamiltonian graph G + 34
We can use this graph to grasp how this theorem works using numbers instead of variables. This graph only requires one more edge to be Hamiltonian, an edge that goes from vertex 3 to vertex 4. In G we have the Hamiltonian path 4123, where our starting vertex is 4, and our ending vertex is 3. The graph with the extra edge is called G + 34. So our hamiltonian cycle in G + 34 would be 41234.

Now, for the graph G, our m = 1, since d(4) = 1, and n=4, since we have four vertices. Then m ≤ n/2 = 2, and G is non-Hamiltonian, which we can see in the picture. However, when we add 34, m = 2 now. And in fact m ≥ n/2 for this new graph, and it is now Hamiltonian. This discovery follows the theorem, and we have shown that it works for this example. Since Dirac's Theorem is only an "if-statement", the theorem actually tells us nothing about graphs that do not meet its conditions, such as G. It was convenient this time that G was not Hamiltonian when it did not meet the conditions.

However, this simple method could not be employed in the proof, since we had no exact numbers to work with. This is only one case. The theorem needs to be proved for a general case. The following uses the exact same method as the proof, but it is only applied to this one graph. It is meant to show the ideas of the proof without having to use too many variables.

Let us assume that the theorem is wrong and then show that a contradiction arises.

Since the path starts at 4 and ends at 3, vertex 3 would play the part of the u and vertex 4 would play the part of v (as a note for those who read the proof).

In the general case the degree of a vertex could not be found by inspection. Instead we had to use alternate means. That method will now be shown on our example graph, with the same results as the above analysis.

First, we need to define to groups of vertices.

  • We call a set S all the vertices such that the next vertex along the cycle has an edge with the first vertex in the cycle in G.
  • In this example, it would be all of the vertices whose successor has an edge with vertex 4, since 4 is our starter. We can tell that the set S is thus just 4.
  • Our set T is all of the vertices that have an edge with the last vertex in the cylce in G.
  • In this case, the last vertex is 3, and T is 2 and 1.

At this point in the proof, we showed that the last vertex in the Hamiltonian path of G was not a member of either set, since it is not adjacent to itself or the first vertex. In this case, that corresponds to 3 not being in either S or T since it is not adjacent to itself or 4. This means that there are fewer vertices in both the sets than there are vertices total.

The next step was to show that S and T have no vertices in common. In this case, this is also true, since S is just 4, and T is just 2 and 1.

Finally, we showed that the degree of the starting vertex is the same as the number of vertices in the set S, and the degree of the ending vertex is the same as the number of vertices in the set T. In the example, S has 1 element, and d(4) = 1. T has 2 elements, and d(3) = 2. Furthermore, adding the number of total elements in both sets is the same as and the number of elements that the two sets have together plus the ones they have in common. Here in the example, this amounts to one element in S plus 2 elements in T equals 3 elements total plus 0 elements in common. 1 + 2 = 3 + 0.

So now, it is a simple matter of substitution. It is true that the sum of the degrees is 1 + 2. Using the facts we showed above, 1 + 2 = 3 + 0 = 3. This last number we know for a fact is less than the total number of vertices, 3 < 4. Since 1 + 2 < 4, we know that m must be less than n/2. Namely, 1 < n/2 = 2. This contradicts the negation of the theorem! By the negation, m should be greater than or equal to 2. But it isn't! So thus, the theorem is correct in this case.

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

Let G be a simple graph and let u and v be nonadjacent vertices in G such that d(u) + d(v) ≥ n. Then G is Hamiltonian if and only if G + uv is Hamiltonian.

Proof

The proof is based heavily on the proof for Dirac's Theorem, so it will not be hidden. Since the theorem is of the form ''A if and only if B", it has to be proven both as A implies B and B implies A. We start with showing that G being Hamiltonian implies that G + uv is Hamiltonian. This is true since no new vertices were added.

Now, it must be shown that if G + uv is Hamiltonian then G is Hamiltonian. This is another proof by contradiction. So, let us assume that G + uv is Hamiltonian but G is not.

In this case, repeat the proof for Dirac's theorem. This proof shows that d(u) + d(v) < n. However, this is contrary to how we picked u and v, namely d(u) + d(v) ≥ n. Thus we have a found a contradiction, and verified the truth of the Bondy-Chvátal theorem!

An Example

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.
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.
First, we find two vertices such that the sum of their degrees is greater than or equal to the total number of vertices. 2 and 4 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, neither is G.

Which Theorem is Better?

Despite the fact that the proof for Dirac's Theorem contains slightly more information, that theorem applies to fewer graphs and in general less strong than the Bondy-Chvátal theorem. For example, consider the graph with n = 6 and m = 1 from the above image and the hidden example section.

In addition to this, the Bondy-Chvátal theorem is an "if and only if" statement. Therefore, we can determine whether or not a graph is Hamiltonian, depending on one condition. But Dirac's theorem is only and "if" statement. This means that this theorem only applies to graphs that meet the conditions. If the graph doesn't meet the theorem requirements, then we cannot say anything about the graph at all. This makes the Bondy-Chvátal theorem more appealing.

Alternate Statements for the Bondy-Chvátal Theorem

In fact, there are one or two statements that follow from the Bondy-Chvátal theorem that are even stronger than the theorem itself. One of the strongest statements has to do with 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 theorem 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 to 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. Nowhere did the theorem restrict us to adding only one additional edge. The closure of the graph is just a graph where all the helpful edges have been added. Since we have more edges, this statement is stronger than its previous incarnation and is easier to verify.

In many cases, c(G) is a complete graph. A complete graph is a graph where each vertex is adjacent to every other vertex. Complete graphs with more than three 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 easiest to calculate.


NP Completeness Proof

The complete 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, next 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.[3]


Why It's Interesting

Animation of a knight's tour
Animation of a knight's tour
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.

Now, let's assume that we have an algorithm to solve the Traveling Salesman problem. We can use it to make an algorithm for Take a graph G with n vertices. Now, take a complete graph with n nodes. Since the graph 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 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 find a Hamiltonian path in the graph describing all the possible moves of the knight on the chessboard. As it turns out, this graph is in fact Hamiltonian as shown by the animation. Both a Hamiltonian path and cycle can be found. There are 33,439,123,484,294 knight's tours on an 8 by 8 chess board. [4]


Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.




References

  1. ↑ DeLeon, Melissa, "A Study of Sufficient Conditions for Hamiltonian Cycles". Department of Mathematics and Computer Science, Seton Hall University.
  2. ↑ Bondy, J. A., U. S. R. Murty, "Graph Theory with Applications"
  3. ↑ West, Douglas A., Introduction to Graph Theory. Published by Prentice Hall Inc.
  4. ↑ 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

Future Directions for this Page

  • Make Theorems more user-friendly to read?
  • A GIF that draws a Hamiltonian Path?
  • 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.


If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.






Retrieved from "http://mathforum.org/mathimages/index.php/Hamiltonian_Path"
Personal tools
Create or Edit a Page