Menu
I was reading up algorithms for finding the minimum spanning tree(in case of weighted graphs) and for finding if a graph has a hamiltonian path(which depends on the presence of a hamiltonian cycle). I got everything messed up. So whats the difference between a hamiltonian path and a spanning tree? Both cover all the vertices in the graph. While we can have efficient algorithms to find a spanning tree(perhaps a minimum spanning tree), why cant we have algorithms for finding a hamiltonian circuit?? We can keep on adding and removing one edge at a time till we reach a cycle and perhaps, we could find a hamiltonian cycle??
927
Hamilton Paths and Hamilton CircuitsA Hamilton Path is a path that goes through every Vertex of a graph exactly once. A Hamilton Circuit is a Hamilton Path that begins and ends at the same vertex.
We note that a Hamiltonian path is a spanning tree by definition with at most 2 leaves (accounting for the trivial edge cases of the empty graph and the graph on one node). Conversely, a spanning tree with at most 2 leaves is a also Hamiltonian path.
We have to show Hamiltonian Path is NP-Complete. Hamiltonian Path or HAMPATH in a directed graph G is a directed path that goes through each node exactly once. We Consider the problem of testing whether a directed graph contain a Hamiltonian path connecting two specified nodes, i.e.
If at any instant the number of vertices with label "IN STACK" is equal to the total number of vertices in the graph then a Hamiltonian Path exists in the graph.
The two problems are quite different. Think of the minimum spanning tree as the problem of connecting places where you only have to pay once to build the road, but you can use it as many times as you like. It's easy to come up with the cheapest configuration of roads (e.g. by Kruskal's algorithm) that allows you to travel from any place to any other.
The Hamiltonian cycle, on the other hand, wants you to minimize the actual travel distance, i.e. every move from one place to another counts. (It also asks you never to visit a place twice, but that's a minor detail.) This problem is fundamentally non-local, in the sense that you cannot tell whether you're doing the right thing just by locally exploring the options for the next step. By comparison, the greedy MST algorithm is guaranteed to pick the right next edge to add to the tree at every step.
By the way, nobody says that "we cannot have efficient algorithms for HP". It might be that we just haven't found one yet :-)
151
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
