Graphs — Part 2 MCQs with Explanations

Breadth-First Search (BFS) is the correct answer to “Which graph traversal method can be used to check if a graph is bipartite”. This question is standard in competitive examination syllabi for Graphs.

To efficiently manage and retrieve the minimum or maximum element. is the correct answer to “What is the primary use of a priority queue in graph algorithms”. This question is standard in competitive examination syllabi for Graphs.

A partition of the vertices into two disjoint subsets. is the correct answer to “In the context of graph algorithms, what is a "cut"”. This question is standard in competitive examination syllabi for Graphs.

Adjacency list is the correct answer to “Which graph representation method is more efficient for sparse graphs”. This question is standard in competitive examination syllabi for Graphs.

It can be drawn on a plane without any edges crossing. is the correct answer to “What is the characteristic of a graph if it is described as "planar"”. This question is standard in competitive examination syllabi for Graphs.

Representation of Boolean Functions is the correct answer to “In which of the following case does a Propositional Directed Acyclic Graph is used for”. This question is standard in competitive examination syllabi for Graphs.

Tautology Checking is the correct answer to “Which of the following logical operation can't be implemented by polynomial time graph manipulation algorithms using Binary Decision Diagrams”. This question is standard in competitive examination syllabi for Graphs.

6 is the correct answer to “What is the maximum number of edges present in a simple directed graph with 7 vertices if there exists no cycles in the graph”. This question is standard in competitive examination syllabi for Graphs.

4 is the correct answer to “What is the number of words that can be formed from the given Directed Acyclic Word Graph”. This question is standard in competitive examination syllabi for Graphs.

6 is the correct answer to “Given an adjacency matrix A = [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ], The total no. of ways in which every vertex can walk to itself using 2 edges is . . . . . . . .”. This question is standard in competitive examination syllabi for Graphs.

False is the correct answer to “All Graphs have unique representation on paper.”. This question is standard in competitive examination syllabi for Graphs.

All Empty Graphs is the correct answer to “For which type of graph, the given program won't run infinitely? The Input would be in the form of an adjacency Matrix and n is its dimension (1<n<10). #include <bits/stdc++.h> using namespace std; int G[10][10]; void fun(int n); int main() { int num=0; int n; cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>G[i][j]; fun(n); return 0; } void fun(int n) { for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(G[i][j]==1) j--; }”. This question is standard in competitive examination syllabi for Graphs.

All of the mentioned is the correct answer to “Which of the following is a HyperGraph, where V is the set of vertices, E is the set of edges”. This question is standard in competitive examination syllabi for Graphs.

(n*(n-1))/2 is the correct answer to “What is the number of edges present in a complete graph having n vertices”. This question is standard in competitive examination syllabi for Graphs.

Tomita's Algorithm is the correct answer to “Graph Structured Stack finds its application in . . . . . . . .”. This question is standard in competitive examination syllabi for Graphs.

Number of edges*number of vertices is the correct answer to “What are the dimensions of an incidence matrix”. This question is standard in competitive examination syllabi for Graphs.

4 is the correct answer to “What is the number of unlabeled simple directed graph that can be made with 1 or 2 vertices”. This question is standard in competitive examination syllabi for Graphs.

False is the correct answer to “Incidence matrix and Adjacency matrix of a graph will always have same dimensions”. This question is standard in competitive examination syllabi for Graphs.

Sparse graph is the correct answer to “In which case adjacency list is preferred in front of an adjacency matrix”. This question is standard in competitive examination syllabi for Graphs.

Representation of Boolean Functions is the correct answer to “In which of the following case does a Binary Decision Diagram is used for”. This question is standard in competitive examination syllabi for Graphs.

Directed Acyclic Graph is the correct answer to “A Graph Structured Stack is a . . . . . . . .”. This question is standard in competitive examination syllabi for Graphs.

dotted, bold is the correct answer to “In a Binary Decision Diagrams 0 values by a . . . . . . . . line and the 1 values are represented by a . . . . . . . . line.”. This question is standard in competitive examination syllabi for Graphs.

O(n1.25) is the correct answer to “What would be the time complexity of the BFS traversal of a graph with n vertices and n 1.25 edges”. This question is standard in competitive examination syllabi for Graphs.

Adjacency List, Adjacency Matrix as well as Incidence Matrix is the correct answer to “Which of the following ways can be used to represent a graph”. This question is standard in competitive examination syllabi for Graphs.

True is the correct answer to “All trees with n vertices consists of n-1 edges.”. This question is standard in competitive examination syllabi for Graphs.

Directed Acyclic Graph is the correct answer to “Binary Decision Diagram is a type of . . . . . . . .”. This question is standard in competitive examination syllabi for Graphs.

Regular Graph is the correct answer to “A graph with all vertices having equal degree is known as a . . . . . . . .”. This question is standard in competitive examination syllabi for Graphs.

True is the correct answer to “In a Propositional Directed Acyclic Graph Leaves maybe labelled with a boolean variable.”. This question is standard in competitive examination syllabi for Graphs.

O(V2) is the correct answer to “The time complexity to calculate the number of edges in a graph whose information in stored in form of an adjacency matrix is . . . . . . . .”. This question is standard in competitive examination syllabi for Graphs.

3,2,2,2,1,1 is the correct answer to “What is the degree sequence of the given HyperGraph, in non-increasing order. V = {v1,v2,v3,v4,v5,v6} E = {{v1,v4,v5} {v2,v3,v4,v5} {v2} {v1} {v1,v6}}”. This question is standard in competitive examination syllabi for Graphs.

i and iii is the correct answer to “Given Adjacency matrices determine which of them are PseudoGraphs? i. {{1,0} {0,1}} ii. {{0,1}{1,0}} iii. {{0,0,1}{0,1,0}{1,0,0}}”. This question is standard in competitive examination syllabi for Graphs.

O(V) is the correct answer to “Time complexity to find if there is an edge between 2 particular vertices is . . . . . . . .”. This question is standard in competitive examination syllabi for Graphs.

n-2 is the correct answer to “What is the number of vertices of degree 2 in a path graph having n vertices,here n>2.”. This question is standard in competitive examination syllabi for Graphs.

10 is the correct answer to “What would be the number of zeros in the adjacency matrix of the given graph”. This question is standard in competitive examination syllabi for Graphs.

1,2,3 is the correct answer to “For which of the following combinations of the degrees of vertices would the connected graph be eulerian”. This question is standard in competitive examination syllabi for Graphs.

ABCED is the correct answer to “What would be the DFS traversal of the given Graph”. This question is standard in competitive examination syllabi for Graphs.

All the cyclic directed graphs hace non topological sortings is the correct answer to “Which of the given statement is true”. This question is standard in competitive examination syllabi for Graphs.

String Matching is the correct answer to “In which of the following does a Directed Acyclic Word Graph finds its application in”. This question is standard in competitive examination syllabi for Graphs.

True is the correct answer to “The graphs G1 and G2 with their incidences matrices given are Isomorphic. e1 e2 e3 e4 e5 e6 v1 1 0 0 0 0 0 v2 1 1 0 0 0 1 v3 0 1 1 0 1 0 v4 0 0 1 1 0 0 v5 0 0 0 1 1 1 e1 e2 e3 e4 e5 e6 v1 0 0 1 0 0 0 v2 1 0 1 0 1 0 v3 1 1 0 1 0 0 v4 0 1 0 0 0 1 v5 0 0 0 1 1 1”. This question is standard in competitive examination syllabi for Graphs.

iv and v is the correct answer to “Which of the following symbols represent leaf nodes? i. Δ ii. ◊ iii. ∇ iv. T v. ⊥”. This question is standard in competitive examination syllabi for Graphs.