Return to Video

10ps-10 Just Once 2 Solution

  • 0:00 - 0:02
    So the answer here is n,
  • 0:02 - 0:05
    and to see this, let's start from the second part of the statement.
  • 0:05 - 0:10
    Let's say that a graph has a Hamiltonian cycle; then that means it can start
  • 0:10 - 0:15
    at one vertex and end at another, passing through every vertex on the way.
  • 0:15 - 0:22
    Now if each edge has a length 1, then the shortest tour from one end to the other
  • 0:22 - 0:24
    is going to pass through each of those edges.
  • 0:24 - 0:28
    And then the shortest tour for the given graph has a length of n.
  • 0:28 - 0:32
    Now let's say instead that we have a shortest tour for a given graph
  • 0:32 - 0:37
    with n vertices, and it has length n, with the stipulation that each edge has length 1.
  • 0:37 -
    Then we can simply use that shortest tour as the Hamiltonian cycle and be done.
Cím:
10ps-10 Just Once 2 Solution
Team:
Udacity
Projekt:
CS313 - Theoretical Computer Science
Duration:
0:44
Amara Bot hozzáadott egy fordítást

English subtitles

Felülvizsgálatok