2
$\begingroup$

I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance)

  • $\alpha$ denotes the start and end vertex of the Eulerian path enter image description here

Step 1 - Calculate minimum spanning tree $T$

enter image description here enter image description here

Step 2 - Calculate the set of verices $O$ with odd degree in $T$

enter image description here enter image description here

Step 3 - Form the subgraph of $G$ using only the vertices of $O$

This is starting to get confusing

enter image description here

enter image description here enter image description here

Step 4 - Construct a minimum-weight perfect matching $M$ in this subgraph

enter image description here

Step 5 - Unite matching and spanning tree $T$ and $M$ to form an Eulerian multigraph

enter image description here

I am NOT satisfied

Did I do something wrong or did I simply just hit an sub-optimal solution. It is not hard to see that the Eulerian path easily could be improved by either connection $G \rightarrow H$ or $A \rightarrow B$ as illustrated underneath:

enter image description here

Improve this question
$\endgroup$
3
  • $\begingroup$ Christofides’ algorithm is an approximation algorithm. It is not guaranteed to produce an optimal solution. $\endgroup$
    – Yuval Filmus
    Commented Nov 27, 2018 at 21:07
  • $\begingroup$ @YuvalFilmus That's why I am questioning whether I just hit a sub-optimal solution, however, it could also be a result of an error. I am new to the field of graph theory. All the terms are new to me, and so I could likely have made an error. Can you approve I did it right? $\endgroup$
    – Sebastian Nielsen
    Commented Nov 27, 2018 at 21:46
  • $\begingroup$ I’m not going to check your solution. I can help you with any conceptual difficulties. $\endgroup$
    – Yuval Filmus
    Commented Nov 27, 2018 at 21:49

2 Answers 2

Reset to default
5
$\begingroup$

As mentioned by Yuval, Christofides’ algorithm is an approximation algorithm to the travelling salesman problem. It is not guaranteed to produce an optimal solution. So it is not unexpected that you could end up with a sub-optimal solution of

On the other hand, you did make a mistake while computing the minimal spanning tree. In your step 1 that calculates the minimum spanning tree, edge H$\alpha$ should be replaced by edge HG.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Yes, thank you a lot! This is the error I had trouble finding! $\endgroup$
    – Sebastian Nielsen
    Commented Nov 28, 2018 at 8:40
  • $\begingroup$ question: I was supposed to end up with an Euler path, however, that is not the case, since not every edge of g is visited exactly once, there is a lot of edges that is not visited at all! Can I still call it an Euler path, or why didn't I end up with an Euler path? $\endgroup$
    – Sebastian Nielsen
    Commented Dec 2, 2018 at 12:32
  • 1
    $\begingroup$ The Christofides algorithm is an algorithm for finding approximate solutions to the travelling salesman problem (TSP). It uses Euler path of a temporary graph to find a hamiltonian circuit of the original graph that approximates the optimal solution to TSP. So you are not supposed to end up with a Euler path. You should end up with a hamiltonian circuit, a cycle that visits every vertex of the original graph exactly once. $\endgroup$
    – John L.
    Commented Dec 2, 2018 at 12:43
2
$\begingroup$
  1. It's an approximation algorithm, so the answer can be suboptimal.
  2. The answer of a given TSP is a Hamiltonian cycle, NOT Eulerian path.

But the above doesn't justify that you have a wrong result, because simply:

  1. You forgot the last step, which is short-cutting -- removal of repeated vertices.

So because you have two paths ($A \alpha B$ and $G \alpha H$) with repeated $\alpha$, you should modify one of those. For example -- make a short-cut (and skip $\alpha$) when travelling from $G$ to $H$ and go directly with your upper red edge. Then you'll have a valid solution to this problem.

EDIT: Jack has pointed out (correctly) that you didn't create a minimum spanning tree. However, if we suppose that the tree is correct (for example the cost of $GH$ edge is 56) and you get the result as seen above, then my rules still apply.

Improve this answer
$\endgroup$

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.