GATE CSE 2025 Set 2 | Greedy Method Question 1 | Algorithms

GATE CSE 2025 Set 2

MCQ (Single Correct Answer)

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

Every MST remains an MST, and every SP remains an SP.

MSTs need not remain MSTs, and every SP remains an SP.

Every MST remains an MST, and SPs need not remain SPs.

MSTs need not remain MSTs, and SPs need not remain SPs.

GATE CSE 2025 Set 1

Numerical

-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 2 English

Your input ____

GATE CSE 2024 Set 2

MCQ (More than One Correct Answer)

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

All edges in $G$ have even weight

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

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

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

GATE CSE 2024 Set 2

Numerical

-0

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

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