MAT344H1 Lecture Notes - Lecture 10: Hamiltonian Path
Document Summary
Start with a single vertex then grow your circuit one vertex at a time. To get from find the vertex w nearest to. Say w is the nearest in cost to , specifically to , then we put w in front of in the new. Proof: draw an optimal h. c. , let"s call it h. If (cost of the edges between i and j from two directions are equal) and are satisfied , then this algorithm is less than or equal to 2 times the cheapest hamilton. Suppose (e is the most expensive edge in h) Every time we add vertex to we remove an edge from . Do this in such a way that the cost of edge e is 2 times the increase in cost form to. Note that there is an unique path in from to the next vertex in e= a-b, the 1st edge in the unique path from to new vertex c along.
