| 21. | A connected graph T without any cycles is called ........ |
|
Answer: (a).free graph
|
| 22. | In a graph if E=(u,v) means ...... |
|
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? |
|
Answer: (a).I only
|
| 24. | Let A be an adjacency matrix of a graph G. The ij th entry in the matrix Ak , gives |
|
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 |
|
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? |
|
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 |
|
Answer: (d).more than n(n-1)/2
|
| 28. | The maximum degree of any vertex in a simple graph with n vertices is |
|
Answer: (a).n–1
|
| 29. | The data structure required for Breadth First Traversal on a graph is |
|
Answer: (a).queue
|
| 30. | In Breadth First Search of Graph, which of the following data structure is used? |
|
Answer: (b).Queue
|
