1
GATE CSE 2025 Set 1
MCQ (Single Correct Answer)
+1
-0.33

Let $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$. For any two vertices, $u$ and $v$, let $d_1(u, v)$ and $d_2(u, v)$ be the shortest distances between $u$ and $v$ in $G$ and $T$, respectively. Which ONE of the options is CORRECT for all possible $G, T, u$ and $v$ ?

A
$d_1(u, v)=d_2(u, v)$
B
$d_1(u, v) \leq d_2(u, v)$
C
$d_1(u, v) \geq d_2(u, v)$
D
$d_1(u, v) \neq d_2(u, v)$
2
GATE CSE 2021 Set 2
MCQ (Single Correct Answer)
+1
-0.33

Let G be a connected undirected weighted graph. Consider the following two statements.

S1: There exists a minimum weight edge in G which is present in every minimum spanning tree of G.

S2: If every edge in G has distinct weight, then G has a unique minimum spanning tree. Which one of the following options is correct?

A
S1 is false and S2 is true.
B
S1 is true and S2 is false.
C
Both S1 and S2 are true.
D
Both S1 and S2 are false.
3
GATE CSE 2017 Set 1
MCQ (Single Correct Answer)
+1
-0.33

Consider the following table :

Algorithms Design Paradigms
(P) Kruskal (ii) Greedy
(Q) Quicksort (i) Divide and Conquer
(R) Floyd–Warshall (iii) Dynamic Programming

Match the algorithms to the design paradigms they are based on.

A
$(\mathrm{P}) \leftrightarrow$ (ii), $\quad(\mathrm{Q}) \leftrightarrow$ (iii), (R) $\leftrightarrow$ (i)
B
$(\mathrm{P}) \leftrightarrow$ (iii), (Q) $\leftrightarrow$ (i), $\quad$ (R) $\leftrightarrow$ (ii)
C
$(\mathrm{P}) \leftrightarrow$ (ii), $\quad(\mathrm{Q}) \leftrightarrow$ (i), $\quad(\mathrm{R}) \leftrightarrow$ (iii)
D
$(\mathrm{P}) \leftrightarrow$ (i),$\quad(\mathrm{Q}) \leftrightarrow$ (ii), $\quad(\mathrm{R}) \leftrightarrow$ (iii)
4
GATE CSE 2016 Set 1
MCQ (Single Correct Answer)
+1
-0.3
Let $$G$$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?

$$P:$$ Minimum spanning tree of $$G$$ does not change
$$Q:$$ Shortest path between any pair of vertices does not change

A
$$P$$ only
B
$$Q$$ only
C
Neither $$P$$ nor $$Q$$
D
Both $$P$$ and $$Q$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP