Introduction
Graph data structures are among the most essential and intriguing subjects to study in computer science because of their use in real-world applications such as google maps and circuit design.
Formally, a graph is a non-linear data structure consisting of nodes and the edges that connect them.
You can check out our top graph problems.
This blog covers the previous year's gate questions on graph with proper explanation.
Gate Questions on Graph
Let us now discuss the previously asked gate questions on Graph.
-
There are eight vertices and five faces in an undirected connected planar graph G. The number of edges in G is _________.
(A) 10
(B) 11
(C) 12
(D) 6
Answer: B. 11
Explanation: By using Euler’s theorem, the number of regions(R) = e – v + 2
R = e – v + 2
5 = e – 8 + 2 = e-6
e = 5 + 6 = 11
-
Let a simple graph G with 20 vertices and 8 components. If we delete a vertex in G, then the number of components in G should lie between ____.
(A) 8 and 20
(B) 8 and 19
(C) 7 and 19
(D) 7 and 20
Answer: C. 7 and 19
Explanation: If the vertex we are deleting from G is an isolated vertex, which is a component by itself, then the number of components in G becomes 7.
If G is a start Graph, then by deleting the cut vertex of G, we get 19 components.
-
Let a graph G with 100 vertices numbered from 1 to 100. Two vertices x and y are adjacent iff |x−y|=12 or |x−y|=8. The number of connected components in G is
(A) 4
(B) 8
(C) 25
(D) 12
Answer: B. 4
Explanation: When vertices are arranged with the difference of 8 there are 8 components, as shown by 8 columns in the image below
Source: https://edurev.gumlet.io/ApplicationImages/Temp/3954df8f-5d1b-410a-aaa3-ba1e3b0a15e5_lg.png?w=768&dpr=1.0
When vertices are arranged with the difference of 12, the number of components is reduced to 4 as the first column will be connected with the fifth column, the second column will be connected with the sixth column, the third column will be connected with the seventh column and fourth column will be connected with the 8 columns. No other form of connection is there, so a total of 4 connected components are there.
-
How many edges may an acyclic undirected graph with n vertices have?
(A) n + 1
(B) n - 1
(C) n
(D) 2n - 1
Answer: B. n - 1
Explanation: When cyclic, n * (n – 1) / 2. However, the acyclic graph with the most edges is actually a spanning tree. Hence the right answer is n-1 edges.
-
Let a weighted undirected graph G and e be an edge with the greatest weight in G. Assume G has a minimum weight spanning tree with the edge e. Which of the following propositions is consistently TRUE?
(A) Edge e cannot be contained in a cycle.
(B) In G, there is a cycle with all edges of maximal weight.
(C) A cutset in G has all edges of maximum weight.
(D) All edges in G have the same weight
Answer: C. There exists a cutset in G having all edges of maximum weight.
Explanation: Option C asserts that if e is in the minimum spanning tree, there must be a cut-set (minimum edge set whose removal disconnects the graph) in G with all edges of the greatest weight. And it is correct.
-
Which of the following properties apply to the adjacency matrix X of a simple undirected unweighted network with n nodes?
(A) If the sum of all the elements of X is at most 2(n−1), then the graph must be acyclic.
(B) If the graph is connected, none of the entries of Xn−1+In can be zero.
(C) If there is at least a 1 in each of X’s rows and columns, the graph must be connected.
(D) The diagonal entries of X2 are the degrees of the graph's vertices.
Answer: D. The diagonal entries of X2 are the degrees of the graph's vertices.
Explanation: X2 diagonal elements = (1.1 or 0.0)+(1.1 or 0.0) + ….. +(1.1 or 0.0) [ n times ]
let some specific node C, if C - A edge present, then 1.1 instead of 0.0 with respect to node A in above eqation
therefore for each edge between C and Vertex, there should be one 1 in the above equation
Therefore X2 diagonal elements = degree of the vertices of the graph.
-
In a bipartite graph on 12 vertices, what is the maximum number of edges present _________?
(A) 32
(B) 35
(C) 46
(D) 36
Answer: D. 36
Explanation: We know, Maximum possible number of edges in a bipartite graph on ‘n’ vertices = (1/4) x n2.
Substituting n = 12, we get the maximum number of edges in a bipartite graph on 12 vertices.
= (1/4) x (12)2
= (1/4) x 12 x 12
= 36
-
Which of the following claims about an undirected graph is/are TRUE?
P: The number of vertices with odd degrees is even.
Q: The sum of all vertices' degrees is even.
(A) Q
(B) P
(C) Both Q and P
(D) Neither Q and P
Answer: C. Both P and Q
Explanation: Q is correct because the graph is undirected, and each edge adds 2 to the sum of degrees.
P is correct: If we take the sum of all degrees and deduct all even degrees, we get an even number (because Q is true). As a result, the total number of
odd degree vertices must be even.
-
What is the time complexity of the Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
(A) Θ(n3)
(B) Θ(n2 Logn)
(C) Θ(n2)
(D) Θ(n3 Logn)
Answer: A. Θ(n3)
Explanation: The time complexity of the Bellman-Ford algorithm is Θ(VE), where V denotes the number of vertices and E denotes the number of edges. When the graph is finished, the value of E becomes Θ(V2). Hence, the overall time complexity becomes Θ(V3).
-
What is the number of an m-vertex simple connected graph which does not contain any odd-length cycle? Assume m >= 2.
(A) 3
(B) 2
(C) m-1
(D) m
Answer: B. 2
Explanation: The chromatic number of a graph is the smallest number of colors needed to color the vertices so that no two adjacent vertices share the same color.
Refer to Gate Questions on Graph: Part 1 for more questions. Also, check out the Gate Syllabus for CSE.
8+ registered 