| 1. | Which of the following statements for a simple graph is correct? |
| A. | Every path is a trail |
| B. | Every trail is a path |
| C. | Every trail is a path as well as every path is a trail |
| D. | Path and trail have no relation |
| Answer» A. Every path is a trail | |
| 2. | For the given graph(G), which of the following statements is true? |
| A. | G is a complete graph |
| B. | G is not a connected graph |
| C. | The vertex connectivity of the graph is 2 |
| D. | none |
| Answer» C. The vertex connectivity of the graph is 2 | |
| 3. | What is the number of edges present in a complete graph having n vertices? |
| A. | (n*(n+1))/2 |
| B. | (n*(n-1))/2 |
| C. | n |
| D. | Information given is insufficient |
| Answer» B. (n*(n-1))/2 | |
| 4. | The given Graph is regular. |
| A. | True |
| B. | False |
| C. | none |
| D. | none |
| Answer» A. True | |
| 5. | A connected planar graph having 6 vertices, 7 edges contains regions. |
| A. | 15 |
| B. | 3 |
| C. | 1 |
| D. | 11 |
| Answer» B. 3 | |
| 6. | If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of G) is |
| A. | (n*n-n-2*m)/2 |
| B. | (n*n+n+2*m)/2 |
| C. | (n*n-n-2*m)/2 |
| D. | (n*n-n+2*m)/2 |
| Answer» A. (n*n-n-2*m)/2 | |
| 7. | Which of the following properties does a simple graph not hold? |
| A. | Must be connected |
| B. | Must be unweighted |
| C. | Must have no loops or multiple edges |
| D. | Must have no multiple edges |
| Answer» A. Must be connected | |
| 8. | What is the maximum number of edges in a bipartite graph having 10 vertices? |
| A. | 24 |
| B. | 21 |
| C. | 25 |
| D. | 16 |
| Answer» C. 25 | |
| 9. | Which of the following is true? |
| A. | A graph may contain no edges and many vertices |
| B. | A graph may contain many edges and no vertices |
| C. | A graph may contain no edges and no vertices |
| D. | A graph may contain no vertices and many edges |
| Answer» B. A graph may contain many edges and no vertices | |
| 10. | For a given graph G having v vertices and e edges which is connected and has no cycles, which of the following statements is true? |
| A. | v=e |
| B. | v = e+1 |
| C. | v + 1 = e |
| D. | v = e-1 |
| Answer» B. v = e+1 | |
| 11. | For which of the following combinations of the degrees of vertices would the connected graph be eulerian? |
| A. | 1,2,3 |
| B. | 2,3,4 |
| C. | 2,4,5 |
| D. | 1,3,5 |
| Answer» A. 1,2,3 | |
| 12. | A graph with all vertices having equal degree is known as a |
| A. | Multi Graph |
| B. | Regular Graph |
| C. | Simple Graph |
| D. | Complete Graph |
| Answer» B. Regular Graph | |
| 13. | Which of the following ways can be used to represent a graph? |
| A. | Adjacency List and Adjacency Matrix |
| B. | Incidence Matrix |
| C. | Adjacency List, Adjacency Matrix as well as Incidence Matrix |
| D. | No way to represent |
| Answer» C. Adjacency List, Adjacency Matrix as well as Incidence Matrix | |
| 14. | The number of possible undirected graphs which may have self loops but no multiple edges and have n vertices is |
| A. | 2((n*(n-1))/2) |
| B. | 2((n*(n+1))/2) |
| C. | 2((n-1)*(n-1))/2) |
| D. | 2((n*n)/2) |
| Answer» D. 2((n*n)/2) | |
| 15. | Given a plane graph, G having 2 connected component, having 6 vertices, 7 edges and 4 regions. What will be the number of connected components? |
| A. | 1 |
| B. | 2 |
| C. | 3 |
| D. | 4 |
| Answer» B. 2 | |
| 16. | Number of vertices with odd degrees in a graph having a eulerian walk is |
| A. | 0 |
| B. | Can’t be predicted |
| C. | 2 |
| D. | either 0 or 2 |
| Answer» D. either 0 or 2 | |
| 17. | How many of the following statements are correct? |
| A. | All cyclic graphs are complete graphs. |
| B. | All complete graphs are cyclic graphs. |
| C. | All paths are bipartite. |
| D. | All cyclic graphs are bipartite. |
| Answer» B. All complete graphs are cyclic graphs. | |
| 18. | What is the number of vertices of degree 2 in a path graph having n vertices,here n>2. |
| A. | n-2 |
| B. | n |
| C. | 2 |
| D. | 0 |
| Answer» A. n-2 | |
| 19. | What would the time complexity to check if an undirected graph with V vertices and E edges is Bipartite or not given its adjacency matrix? |
| A. | O(E*E) |
| B. | O(V*V) |
| C. | O(E) |
| D. | O(V) |
| Answer» B. O(V*V) | |
| 20. | With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess? |
| A. | (V*(V-1))/2 |
| B. | (V*(V+1))/2 |
| C. | (V+1)C2 |
| D. | (V-1)C2 |
| Answer» A. (V*(V-1))/2 | |
| 21. | The topological sorting of any DAG can be done in time. |
| A. | cubic |
| B. | quadratic |
| C. | linear |
| D. | logarithmic |
| Answer» C. linear | |
| 22. | If there are more than 1 topological sorting of a DAG is possible, which of the following is true. |
| A. | Many Hamiltonian paths are possible |
| B. | No Hamiltonian path is possible |
| C. | Exactly 1 Hamiltonian path is possible |
| D. | Given information is insufficient to comment anything |
| Answer» B. No Hamiltonian path is possible | |
| 23. | Which of the given statement is true? |
| A. | All the Cyclic Directed Graphs have topological sortings |
| B. | All the Acyclic Directed Graphs have topological sortings |
| C. | All Directed Graphs have topological sortings |
| D. | All the cyclic directed graphs have non topological sortings |
| Answer» D. All the cyclic directed graphs have non topological sortings | |
| 24. | What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph? |
| A. | Depends on a Graph |
| B. | Will always be zero |
| C. | Will always be greater than zero |
| D. | May be zero or greater than zero |
| Answer» B. Will always be zero | |
Tags
Question and answers in Non Linear Data Structures – Graphs,Non Linear Data Structures – Graphs Multiple choice questions and answers,Non Linear Data Structures – Graphs Important MCQs,Solved MCQs for Non Linear Data Structures – Graphs,Non Linear Data Structures – Graphs MCQs with answers PDF download