1
GATE CSE 2020
MCQ (Single Correct Answer)
+2
-0.67
Let G = (V, E) be a directed, weighted graph with weight function w: E $$\to$$ R. For some function f: V $$\to$$ R, for each edge (u, v) $$\in$$ E, define w'(u, v) as w(u, v) + f(u) - f(v).

Which one of the options completes the following sentence so that it is TRUE?
βThe shortest paths in G under w are shortest paths under wβ too, _______β.
A
for every f : V $$\to$$ R
B
if and only if $$\forall u \in V$$, f(u) is positive
C
if and only if $$\forall u \in V$$, f(u) is negative
D
f and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G
2
GATE CSE 2018
MCQ (Single Correct Answer)
+2
-0.6
Let $$G$$ be a simple undirected graph. Let $${T_D}$$ be a depth first search tree of $$G.$$ Let $${T_B}$$ be a breadth first search tree of $$G.$$ Consider the following statements.

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

Which of the statements above must necessarily be true?

A
$$I$$ only
B
$$II$$ only
C
Both $$I$$ and $$II$$ only
D
Neither $$I$$ nor $$II$$
3
GATE CSE 2018
Numerical
+2
-0
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 $$π¦$$ denote the degree of a vertex in $$G,$$ and $$π§$$ denote the number of connected components in $$G.$$ Then, $$π¦ + 10π§ =$$ _____.
4
GATE CSE 2016 Set 2
MCQ (Single Correct Answer)
+2
-0.6
In an adjacency list representation of an undirected simple graph $$G = (V,E),$$ each edge $$(u, v)$$ has two adjacency list entries: $$[v]$$ in the adjacency list of $$u,$$ and $$[u]$$ in the adjacency list of $$v.$$ These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If $$|E| = m$$ and $$|V| = n,$$ and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?
A
$$\Theta \left( {{n^2}} \right)$$
B
$$\Theta \left( {n + m} \right)$$
C
$$\Theta \left( {{m^2}} \right)$$
D
$$\Theta \left( {{n^4}} \right)$$
GATE CSE Subjects
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
CBSE
Class 12