English subtitles

← 10ps-10 Just Once 2 Solution

Get Embed Code
1 Language


Showing Revision 1 created 10/24/2012 by Amara Bot.

  1. So the answer here is n,
  2. and to see this, let's start from the second part of the statement.
  3. Let's say that a graph has a Hamiltonian cycle; then that means it can start
  4. at one vertex and end at another, passing through every vertex on the way.
  5. Now if each edge has a length 1, then the shortest tour from one end to the other
  6. is going to pass through each of those edges.
  7. And then the shortest tour for the given graph has a length of n.
  8. Now let's say instead that we have a shortest tour for a given graph
  9. with n vertices, and it has length n, with the stipulation that each edge has length 1.
  10. Then we can simply use that shortest tour as the Hamiltonian cycle and be done.