31.  For an undirected graph G with n vertices and e edges, the sum of the degrees of each vertex is 
a.  ne 
b.  2n 
c.  2e 
d.  e^n 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).2e

32.  A complete graph can have ............... 
a.  n^2 spanning trees 
b.  n^(n2) spanning trees 
c.  n^(n+1) spanning trees 
d.  n^n spanning trees 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b). n^(n2) spanning trees

33.  Graph traversal is different from a tree traversal, because: 
a.  trees are not connected 
b.  graphs may have loops 
c.  trees have root 
d.  None of these 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).trees have root

34.  The number of edges in a simple, nvertex, complete graph is 
a.  n*(n2) 
b.  n*(n1) 
c.  n*(n1)/2 
d.  n*(n1)*(n2) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).n*(n1)/2

35.  Graphs are represented using ............ 
a.  Adjacency tree 
b.  Adjacency linked list 
c.  Adjacency graph 
d.  Adjacency queue 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).Adjacency linked list

36.  The spanning tree of connected graph with 10 vertices contains .............. 
a.  9 edges 
b.  11 edges 
c.  10 edges 
d.  9 vertices 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).9 edges

37.  If locality is a concern, you can use ................ to traverse the graph. 
a.  Breadth First Search 
b.  Depth First Search 
c.  Either BFS or DFS 
d.  None of these 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).Depth First Search

38.  Which of the following algorithms solves the allpair shortest path problem? 
a.  Floyd's algorithm 
b.  Prim's algorithm 
c.  Dijkstra's algorithm 
d.  Warshall's algorithm 
View Answer Report Discuss Too Difficult! 
Answer: (a).Floyd's algorithm

39.  The minimum number of colors needed to color a graph having n (>3) vertices and 2 edges is 
a.  1 
b.  2 
c.  3 
d.  4 
View Answer Report Discuss Too Difficult! 
Answer: (b).2

40.  Which of the following is useful in traversing a given graph by breadth first search? 
a.  set 
b.  List 
c.  stacks 
d.  Queue 
View Answer Report Discuss Too Difficult! 
Answer: (d).Queue
