21.  A connected graph T without any cycles is called ........ 
a.  free graph 
b.  no cycle graph 
c.  non cycle graph 
d.  circular graph 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).free graph

22.  In a graph if E=(u,v) means ...... 
a.  u is adjacent to v but v is not adjacent to u 
b.  e begins at u and ends at v 
c.  u is processor and v is successor 
d.  both b and c 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).both b and c

23.  Let G = (V, E) be any connected undirected edgeweighted graph. The weights of the edges in E are positive any distinct. Consider the following statements: I. Minimum Spanning Tree of G is always unique. II. Shortest path between any two vertices of G is always unique. Which of the above statements is/are necessarily true? 
a.  I only 
b.  II only 
c.  both I and II 
d.  neither I and II 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).I only

24.  Let A be an adjacency matrix of a graph G. The ij th entry in the matrix Ak , gives 
a.  The number of paths of length K from vertex Vi to vertex Vj. 
b.  Shortest path of K edges from vertex Vi to vertex Vj. 
c.  Length of a Eulerian path from vertex Vi to vertex Vj. 
d.  Length of a Hamiltonian cycle from vertex Vi to vertex Vj. 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).Shortest path of K edges from vertex Vi to vertex Vj.

25.  For an undirected graph with n vertices and e edges, the sum of the degree of each vertex is equal to 
a.  2n 
b.  (2n1)/2 
c.  2e 
d.  4n 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).2e

26.  An undirected graph G with n vertices and e edges is represented by adjacency list. What is the time required to generate all the connected components? 
a.  O (n) 
b.  O (e) 
c.  O (e+n) 
d.  O (en) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).O (e+n)

27.  A graph with n vertices will definitely have a parallel edge or self loop if the total number of edges are 
a.  more than n 
b.  more than n 
c.  more than (n+1)/2 
d.  more than n(n1)/2 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).more than n(n1)/2

28.  The maximum degree of any vertex in a simple graph with n vertices is 
a.  n–1 
b.  n+1 
c.  2n–1 
d.  n 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).n–1

29.  The data structure required for Breadth First Traversal on a graph is 
a.  queue 
b.  stack 
c.  array 
d.  tree 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).queue

30.  In Breadth First Search of Graph, which of the following data structure is used? 
a.  Stack 
b.  Queue 
c.  Linked List 
d.  None of the above 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).Queue
