retagged by
1,608 views
0 votes
0 votes
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..???
retagged by

1 Answer

1 votes
1 votes

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

 

Answer:

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
3
atulcse asked Jan 13, 2022
476 views
How many minimum spanning trees are possible in this graph?
1 votes
1 votes
1 answer
4
Ram Swaroop asked Jan 30, 2019
1,561 views
Consider a simple undirected weighted graph G(V, E) with 10 vertices and 45 edge, assume (u, v) are two vertices weight of a edge is =4lu- vl then the minimum cost of the...