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

Let $G$ be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ is added to the weight of every edge. Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in G before and after the edge weight update?

A
Every MST remains an MST, and every SP remains an SP.
B
MSTs need not remain MSTs, and every SP remains an SP.
C
Every MST remains an MST, and SPs need not remain SPs.
D
MSTs need not remain MSTs, and SPs need not remain SPs.
2
GATE CSE 2025 Set 1
Numerical
+2
-0

The maximum value of $x$ such that the edge between the nodes $B$ and $C$ is included in every minimum spanning tree of the given graph is _______. (Answer in integer)

GATE CSE 2025 Set 1 Algorithms - Greedy Method Question 3 English

Your input ____
3
GATE CSE 2024 Set 2
MCQ (More than One Correct Answer)
+2
-0

Let $G$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $G$ has even weight. Which of the following statements is/are TRUE for every such graph $G$?

A

All edges in $G$ have even weight

B

All edges in $G$ have even weight OR all edges in $G$ have odd weight

C

In each cycle $C$ in $G$, all edges in $C$ have even weight

D

In each cycle $C$ in $G$, either all edges in $C$ have even weight OR all edges in $C$ have odd weight

4
GATE CSE 2024 Set 2
Numerical
+2
-0

The number of distinct minimum-weight spanning trees of the following graph is ________

GATE CSE 2024 Set 2 Algorithms - Greedy Method Question 5 English

Your input ____
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP