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𝑧 =$$ _____.
Your input ____
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
Software Engineering
Web Technologies
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