MCQ - Graph in Data Structure
11. What is the number of edges present in a complete graph having n vertices?
Explanation: Number of ways in which every vertex can be connected to each other is nC2.
12. In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices.
Explanation: The sum of the degrees of the vertices is equal to twice the number of edges.
13. If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of G) is ___________
Explanation: The union of G and G’ would be a complete graph so, the number of edges in G’= number of edges in the complete form of G(nC2)-edges in G(m).
14. Which of the following properties does a simple graph not hold?
Explanation: A simple graph maybe connected or disconnected.
15. Which of the following is true?
Explanation: A graph must contain at least one vertex.
16. 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?
Explanation: For any connected graph with no cycles the equation holds true.
17. for which of the following combinations of the degrees of vertices would the connected graph be eulerian?
Explanation: A graph is eulerian if either all of its vertices are even or if only two of its vertices are odd.
18. A graph with all vertices having equal degree is known as a __________
Explanation: The given statement is the definition of regular graphs.Explanation: The given statement is the definition of regular graphs.
19. Which of the following ways can be used to represent a graph?
Explanation: The 3 listed methods can be used, the choice depends on the ease of use.
20. The time complexity to calculate the number of edges in a graph whose information in stored in form of an adjacency matrix is ____________
Explanation: As V entries are 0, a total of V2-V entries are to be examined.
Also Check :