21. A connected graph T without any cycles is called ........
a. free graph
b. no cycle graph
c. non cycle graph
d. circular graph
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
Answer: (d).both b and c

23. Let G = (V, E) be any connected undirected edge-weighted 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
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.
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. (2n-1)/2
c. 2e
d. 4n
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 (e-n)
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(n-1)/2
Answer: (d).more than n(n-1)/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
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
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
Answer: (b).Queue

Page 3 of 17