3
$\begingroup$

I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example

The graph:
enter image description here

Calculate minimum spanning tree T:
enter image description here

Calculate the set of vertices O with odd degree in T. They are the same as "the minimum spanning tree T" as the degree of all vertices are odd.

Form the subgraph of G using only the vertices of O (as all are odd, this should give us the original graph): enter image description here

Construct a minimum-weight perfect matching M in this subgraph (I am not sure if I did this right)
enter image description here

Unite matching and spanning tree T ∪ M to form an Eulerian multigraph
enter image description here

This is definitely not right. What went wrong?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

In fact, you have been correct all along. However, you have not finished Christofides algorithm yet.

The next step is "Calculate Euler tour".
In the last picture, you have obtained a multigraph all of whose vertices have even degrees. So it must have an Eulerian path. For example, let us select the Eulerian path A -> F -> A -> C -> B -> D -> E -> D -> A.

The last step is "Remove repeated vertices, giving the algorithm's output".
Removing the second A and the second D on that above path, we obtain a wanted output, A -> F -> C -> B -> D -> E -> A. Done.

Please note it is not very meaningful to apply Christofides algorithm on the given graph.

"The Christofides algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality". The given distances do not obey the triangle inequality, since d(B,D) + d(D, E) = 1 + 4 < 6 = d(B,E). Moreover, the (direct) distance between A and B is not given, raising doubt whether this is a travelling salesman problem at all.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I am new to this, so thank you for the side notes! I got some questions: 1. Does each vertex have to be connected to each other vertex for it to be a valid TSP? I mean it is still possible to create a "TSP" route even with that route missing, so I would say it is valid - but I have been wrong before. 2. Do you think (or know) if it is possible to increase the weights of some of the vertices in my graph in such a way, so that it obey the triangle inequality? I think more messy looking graphs are better at representing real world map scenarios, that's why I created it as it is. $\endgroup$
    – Ryan Cameron
    Commented Nov 14, 2018 at 12:40
  • 1
    $\begingroup$ 1. You can treat is as a TSP if you assume, for example, all missing direct distances between cities are sufficient large or simply infinity. In that way, those missing distances will not affect the solution. However, it is not a metric space still. 2. To obey the triangle inequality, you can just add 10 to each distance you have specified and let the all the missing distances be 20. $\endgroup$
    – John L.
    Commented Nov 14, 2018 at 13:11
  • $\begingroup$ This is not true: "In the last picture, you have obtained a multigraph all of whose vertices have even degrees." - The vertices E, D, A, and F has an odd degree. $\endgroup$
    – Ryan Cameron
    Commented Nov 15, 2018 at 9:22
  • 1
    $\begingroup$ "You have obtained a multigraph", a graph which is permitted to have multiple edges, that is, edges that have the same end nodes. There are two edges between D and E. There are two edges between A and F. $\endgroup$
    – John L.
    Commented Nov 15, 2018 at 12:00
  • 1
    $\begingroup$ You can also check the example at Wikipedia. "That is not an Eulerian path as you visit a vertex more than once in that path". Eulerian path is about visiting each edge exactly once. You are talking about Hamiltonian path. $\endgroup$
    – John L.
    Commented Nov 15, 2018 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.