GATE CSE 2026 Set 1 | Greedy Method Question 1 | Algorithms

GATE CSE 2026 Set 1

MCQ (More than One Correct Answer)

-0

Let $G(V, E)$ be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the minimum spanning trees (MST) of $G$ is/are true?

In every cycle $C$ of $G$, the edge with the largest weight in $C$ is not in any MST

In every cycle $C$ of $G$, the edge with the smallest weight in $C$ is in every MST

For every vertex $v \in V$, the edge with the largest weight incident on $v$ is not in any MST

For every vertex $v \in V$, the edge with the smallest weight incident on $v$ is in every MST

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