GATE 2015 CS (CS3) – Question 55

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Numerical answer

A connected undirected graph has 100 vertices and 300 edges. Its minimum spanning-tree weight is 500. Every edge weight is increased by five. Find the new MST weight.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 995

Explanation

Every spanning tree on one hundred vertices has ninety-nine edges. Increasing each edge by five increases every spanning tree’s weight by the same 99×5=495, so the identity of an optimum remains valid. The new MST weight is 500+495=995.

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

GATE 2021 CS (CS2) Q11 – G is connected, undirected and weighted. S1: Some minimum-weight edge of G is present in…
GATE 2021 CS (CS2) Q56 – For the directed graph shown, which statements hold?
GATE 2021 CS (CS2) Q65 – In the DAG shown with source s, a path’s quality is the product of its edge weights. A…
GATE 2026 CS (CS1) Q41 – Let G(V, E) be an undirected, edge-weighted graph with integer weights. The weight of a…
GATE 2026 CS (CS1) Q49 – Let G(V, E) be a simple, undirected, edge-weighted graph with unique edge weights. Which…
GATE 2026 CS (CS1) Q50 – Consider the standard depth-first search (DFS) algorithm which takes a directed acyclic…

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →