GATE CSE 2025 Set 1 | Graphs Question 3 | Data Structures

GATE CSE 2025 Set 1

MCQ (Single Correct Answer)

-0

Let $G(V, E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u, v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maximum value of $d(u, v), u, v \in V$ such that $u \neq v$, be 30 . Let $T$ be any breadth-first-search tree of $G$. Which ONE of the given options is CORRECT for every such graph $G$ ?

The height of $T$ is exactly 15.

The height of $T$ is exactly 30.

The height of $T$ is at least 15 .

The height of $T$ is at least 30 .

GATE CSE 2024 Set 1

MCQ (More than One Correct Answer)

-0

Let G be a directed graph and T a depth first search (DFS) spanning tree in G that is rooted at a vertex v. Suppose T is also a breadth first search (BFS) tree in G, rooted at v. Which of the following statements is/are TRUE for every such graph G and tree T?

There are no back-edges in G with respect to the tree T

There are no cross-edges in G with respect to the tree T

There are no forward-edges in G with respect to the tree T

The only edges in G are the edges in T

GATE CSE 2020

MCQ (Single Correct Answer)

-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, _______”.

for every f : V $$ \to $$ R

if and only if $$\forall u \in V$$, f(u) is positive

if and only if $$\forall u \in V$$, f(u) is negative

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

GATE CSE 2018

MCQ (Single Correct Answer)

-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?

$$I$$ only

$$II$$ only

Both $$I$$ and $$II$$ only

Neither $$I$$ nor $$II$$

PREVIOUS NEXT