Find the minimum spanning tree of the following graph Use th

Find the minimum spanning tree of the following graph: Use the method in section 12.4 to determine a lower bound for the traveling salesperson problem for the graph in #3. Find the exact solution to the Travelling salesperson problem for the graph in #3.

Solution

3]

To find the minimal spanning tree, we use Kruskal\'s algorithm

First list out minimum weight edges in the graph. then we should put the edges from this list until not forming a circuit.

[a,h]=1, [g,f]=1, [c,e]=1

[b,h]=2, [b,c]=2, [c,d]=2

[d,f]=3, [d,e]=5, [a,g]=6, [f,e]=6

[h,g]=7, [a,b]=8

MINIMUM SPANNING TREE [USING KRUSKAL’S ALGORITHM]

                          a              b                 c                       d

                        h                    g                f                e