###### Algorithms

October 12, 2023###### Algorithms

October 12, 2023# Algorithms

Question 8 |

Consider a graph G = (V, E), where V = {v_{1}, v_{2}, …, v_{100}}, E = {(v_{i}, v_{j}) | 1 ≤ i < j ≤ 100}, and weight of the edge (v_{i}, v_{j}) is |i – j|. The weight of the minimum spanning tree of G is ______.

99 |

Question 8 Explanation:

• If there are n vertices in the graph, then each spanning tree has n − 1 edges.

• N =100

• Edge weight is |i-j| for Edge (vi,vj) {1<=i<=100}

• The weight of edge(v1,v2) is 1 , edge(v5,v6) is 1.

• So, 99 edges of weight is 99.

• N =100

• Edge weight is |i-j| for Edge (vi,vj) {1<=i<=100}

• The weight of edge(v1,v2) is 1 , edge(v5,v6) is 1.

• So, 99 edges of weight is 99.

Correct Answer: A

Question 8 Explanation:

• If there are n vertices in the graph, then each spanning tree has n − 1 edges.

• N =100

• Edge weight is |i-j| for Edge (vi,vj) {1<=i<=100}

• The weight of edge(v1,v2) is 1 , edge(v5,v6) is 1.

• So, 99 edges of weight is 99.

• N =100

• Edge weight is |i-j| for Edge (vi,vj) {1<=i<=100}

• The weight of edge(v1,v2) is 1 , edge(v5,v6) is 1.

• So, 99 edges of weight is 99.

Subscribe

Login

0 Comments