Christofides algorithm (by hand) (suboptimal solution - is it my fault?)

cs.stackexchange https://cs.stackexchange.com/questions/100618

Question

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

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top