Question

#4. TSP a) Solve with 2 MST approx. algorithm. Note: you can assume weights of edges: (CE) = 36 and w(C,A)=33 А B 24 1) Find MST 2) Double MST 3) Find Eulerian cycle 4) Do shortcuts (show steps here) 10 11 С. 30 25 8 E 28 Report the resulting Hamiltonian cycle and its length:

Answer 1

(1) MST using KRUSKAL's Algorithm :

Arrange all the edges in increasing order (in an array )according to their weight :

  8, 9, 10, 11, 24, 25, 28, 30, 33, 36

now, pick at each step pop the lowest weighted edge from the array.

next check whether nodes in the edge are traversed or not.

if not traversed then add the edge to the MST.

repeat until all nodes in the graph are traversed.

8, 9, 10, 11, 24, 25, 28, 30, 33,36 . 8 D 8,10,11, 24, 25, 28,30,33, 36 B 8 D 10, 11, 24, 25, 28, 30, 33, 36 A 10 E 8 Addition of Edge Bull forms a cycle

Addition of edge B-----D forms a cycle, so we pick next edge in the array

244, 25, 28, 30, 33, 36 B А. 9 с 8 D

Since all the nodes in the graph are traversed. Hence the above mentioned tree is our required MST.

(2) MST using Prim's Algorithm

Steps 0: Pick any node as a start node in the MST abitrary.

step 1: arrange all edges which are connected to the current MST in increasing order.

Choose the lowest weighted edge

if the node doesn't form a cycle then add it into the MST & mark the added node as traversed.

repeat from step 1 untill all the nodes are traversed.

initialize A 233 , 24 ,كمه 4,25, 26,30,33,36 10 2A 3324 ,10 5 2ر25 ,۱ رهر ۱۱, 2528, 30, 33,24 [۵ (A 24 ,0 3رو2رود راه 9 36ر33 ع) 24 (0. | 6 E 8

Since all the nodes in the graph are traversed. Hence the above mentioned tree is our required MST.

(3)

There is an Eulerian path exist if we traversed as follows :

A --- E --- B --- A --- D --- C --- B --- D --- E --- C --- A (each edge is traversed only once)

The above mentioned path is a Eulerian Cycle since the starting node and the end node are the same.

(4)

There is an Hamiltonian path exist if we traversed as follows :

A --- B --- C --- D --- E --- A (each node is traversed only once)

The above mentioned path is a Hamiltonian Cycle since the starting node and the end node are the same.

length of the hamiltonian cycle = 24 + 9 + 8 + 28 + 10 = 79