UGC NET Graph Theory Questions with explanation

Q:: An undirected graph G(V,E) contains n (n>2) nodes named V1, V2, V3, ...Vn, Two nodes Vi and Vj are connected if and only if 0< |i-j| <=2. Each edge (Vi,Vj) is assigned weight i+j. What will be the cost of Minimum Spanning Tree (MST) of such graph with 'n' nodes?

(A) 1/12 (11 n^2 - 5 n )                                                     (B) n^2 - n + 1

(C) 6n - 11                                                                       (D) 2n + 1


Answer:: (B)

Explanation::

Given below the graphs of such kind with n=3,4,5,6 

In first graph with n=3 the MST is formed by edges (V1,V2) and (V1,V3)

i.e. cost of MST is 3 + 4 = 7 

In second graph with n=4 the MST is formed by edges (V1,V2) , (V1,V3), (V2,V4)

i.e. cost of MST is 3 + 4 + 6 = 13

In third graph with n=5 it will be 3 + 4 + 6 + 8 = 21

In fourth graph with n=6 it will be 3 + 4 + 6 + 8 + 10 = 31

For graph with 'n' nodes it will be 3 + 4 + 6 + 8 + 10 + ... + 2n-2

it can be re written as

                                    =1 + 2 + 4 + 6 + 8 + 10 + ... + 2n-2
                                    =1 +    2 * (1+2+3+4+5+...n-1)
                                    = 1 + 2 * ( n * ( n - 1 ) / 2)

                                    = n^2 - n + 1

 

Hence correct answer is (B).

graph theory,cbse net graph theory questions,ugc net graph theory questions,graph theory minimum spanning tree,minimum spanning tree