In step 6 of the Christofides algorithm it is implicitly suggested that there is an invarient that the euler circuit can always be shortcutted to an hamilton circuit, what exactly assures us that? e.g (let u,v,w be vertices in the graph.) in the euler circuit, if vertex v has already been visited once, and is being revisited after visiting u and right before visiting w what makes the shortcut edge u-w to always exist?

  • 2
    $\begingroup$ It's assumed that the graph $G$ is complete, so the edge $(u, v)$ exists by definition. Look at the example on the Wiki page you referred to $\endgroup$ – HEKTO Apr 21 '17 at 19:14
  • $\begingroup$ right, missed that in the TSP problem definition. thanks! $\endgroup$ – Ofek Ron Apr 22 '17 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.