Question

#4. TSP b) Solve with Christofides approx. algorithm. Note: you can assume weights of edges: w(C,E) = 36 and w(CA)=33 1) Find MST A B 2) Find min-cost perfect matching 24 3) Find Eulerian cycle 9 4) Do shortcuts (show steps here) lol 25 с 30 8 28 Report the resulting Hamiltonian cycle and its length:

Answer 1

MST 1. 24 A Prim's Algo 10 8 E from MST odd degree Vertices with A-2 E = 1 B 2 D = 1 с - 2 matching E 28 perfect MIN cost B A 24 9 •C 10 8 E 28

3. Eulerian Cycle visit each edge once B E No 4. short cuts Hamiltonian Cycle : cbaedc 49 Length B A 24 10 E 28
1. MST

It's found by using Prim's/Kruskal's Algorithm here I used Kruskal's which goes as follows, and it avoids cycles.

The edge with lowest weight is taken first and vice verse

CD - 8

CB - 9

AE - 10

Here BD is 11 but forms a cycle hence next least is taken

BA - 24

Now we've our MST

2. Odd degree vertices are taken and joined to form the min-cost perfect matching. This edge is added to the MST.

3. Eulerian Cycle suggests that we should take a cycle which visits each edge exactly once. Here, if we start from A, all the edges can be visited. Starting from C as well gives the same result.

4. Shortcuts are done when there is a repetition of a vertex in Eulerian cycle. We don't have any hence no shortcurts.

Hamiltonian cycle is formed where starting from C visits every vertex exactly once and comes back to starting point which is the end now. The length is 79.

Comment for any clarifications!

​​​​