Made easy test series

Question

What we do if graph is complete with 5 vertices and weight are

1,2,3,4,5,6,7,8,9 and 10.

than find maximum possible weight that a minimum weight spanning tree of G have..???

Comments

Why can't we take first weights 1 2 3 4 from one vertex to other vertices then 4 will the max weight that an edge will have and total cost will be 10.?

---

Consider the above graph.

---

1--2--4--7 --> total 14 by Kruskal's algorithm.

Answer 1

Given: A complete graph with 5 vertices and weights are 1,2,3,4,...,9,10.

Key point is: maximum possible weight that a minimum weight spanning tree of G

now, try to understand the meaning of above line, we have to find a MST but possible max weight(w).

So first consider below graph with 3 vertices, one edge with w=1 second w=2.

Now important point is, we have to consider max weight so we will take edge with w=3 in cycle.

Now, we have to add anyhow next to any vertex from 3 and it'll be consider to MST

Now, Similarly, edge with w=5 and w=6 can add to above graph to make a cycle

So, we will go for w=7

Finally, maximum possible weight that a minimum weight spanning tree of G= 1+2+4+7= 14