Graph Theory

Question 1
In a directed acyclic graph with a source vertex s, the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex v other than s, the quality-score of v is defined to be the maximum among the quality-scores of all the paths from s to v. The quality-score of s is assumed to be 1.

The sum of the quality-scores of all vertices on the graph shown above is ______
A
929
B
254
C
639
D
879
GATE CSE 2021 SET-2   Discrete Mathematics
Question 2
Consider the following directed graph:

Which of the following is/are correct about the graph?
[MSQ]
A
The graph does not have a topological order
B
A depth-first traversal starting at vertex S classifies three directed edges as back edges
C
The graph does not have a strongly connected component
D
For each pair of vertices u and v, there is a directed path from u to v
GATE CSE 2021 SET-2   Discrete Mathematics
Question 3
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components.
Let T be a DFS tree obtained by doing DFS in a connected undirected graph G.
Which of the following options is/are correct?
A
Root of T can never be an articulation point in G.
B
Root of T is an articulation point in G if and only if it has 2 or more children.
C
A leaf of T can be an articulation point in G.
D
If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.
GATE CSE 2021 SET-1   Discrete Mathematics
Question 4
G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4 ,v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7 }. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?
A
v2v4
B
v1v4
C
v4v5
D
v3v4
ISRO CSE 2020   Discrete Mathematics
Question 5
Graph G is obtained by adding vertex s to K_{3,4} and making s adjacent to every vertex of K_{3,4}. The minimum number of colours required to edge-colour G is _______
A
4
B
5
C
6
D
7
GATE CSE 2020   Discrete Mathematics
Question 6
Let G be an undirected complete graph on n vertices, where n\gt2. Then, the number of different Hamiltonian cycles in G is equal to
A
n!
B
(n-1)!
C
1
D
\frac{(n-1)!}{2}
GATE CSE 2019   Discrete Mathematics
Question 7
The number of edges in a regular graph of degree: d and n vertices is:
A
maximum of n and d
B
n+d
C
nd
D
nd/2
ISRO CSE 2018   Discrete Mathematics
Question 8
Which of the following is application of Breath First Search on the graph?
A
Finding diameter of the graph
B
Finding bipartite graph
C
Both (A) and (B)
D
None of the above
ISRO CSE 2018   Discrete Mathematics
Question 9
Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2,...,100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G. Then, y+ 10z = _____.
A
83
B
45
C
201
D
109
GATE CSE 2018   Discrete Mathematics
Question 10
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements.

(I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.)
(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |i-j|=1.

Which of the statements above must necessarily be true?
A
I only
B
II only
C
Both I and II
D
Neither I nor II
GATE CSE 2018   Discrete Mathematics


There are 10 questions to complete.

4 thoughts on “Graph Theory”

Leave a Comment

Like this FREE website? Please share it among all your friends and join the campaign of FREE Education to ALL.