minimum spanning trees and shortest paths notes

Chapter Journey: Minimum Spanning Trees and Shortest Paths

Chapter Roadmap Your journey through graph optimization algorithms. 1 MST Cut-Cycle Properties and Uniqueness The theoretical foundation. (You are here) 2 MST Construction and Counting Kruskal's, Prim's, and counting distinct trees. 3 Shortest-Path Properties and Algorithms Dijkstra, Bellman-Ford, and path relaxations. 4 Effects of Edge-Weight Transformations Adding constants, scaling, and structural impacts.

MST Cut-Cycle Properties and Uniqueness

Algorithms › Minimum Spanning Trees Cut-Cycle Properties & Uniqueness The theoretical engine behind every MST algorithm. What you will master: Defining cuts and cycles in graph theory. The Cut Property: identifying "safe" edges. The Cycle Property: identifying "unsafe" edges. Conditions that guarantee a unique Minimum Spanning Tree.

Graph Basics: Cuts and Cycles

.cut-line { stroke-dasharray: 4; animation: dash 2s linear infinite; } @keyframes dash { to { stroke-dashoffset: -20; } } .cycle-path { stroke-dasharray: 100; stroke-dashoffset: 100; animation: draw 3s ease-in-out infinite alternate; } @keyframes draw { to { stroke-dashoffset: 0; } } 1. A Cut (S, V - S) A partition of the graph's vertices into two disjoint sets, S and V - S . Crossing Edge: An edge (u, v) where one endpoint is in S and the other is in V - S . 2. A Cycle A sequence of edges starting and ending at the same vertex, with no repeated vertices or edges in between. Key Trait: Removing any single edge from a cycle does not disconnect the vertices involved.

36 more cards in this chapter

Minimum Spanning Trees and Shortest Paths Notes for GATE CS

Minimum Spanning Trees and Shortest Paths notes for GATE CS: 39 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Chapter Journey: Minimum Spanning Trees and Shortest Paths

Chapter Roadmap

Your journey through graph optimization algorithms.

MST Cut-Cycle Properties and Uniqueness

The theoretical foundation. (You are here)

MST Construction and Counting

Kruskal's, Prim's, and counting distinct trees.

Shortest-Path Properties and Algorithms

Dijkstra, Bellman-Ford, and path relaxations.

Effects of Edge-Weight Transformations

Adding constants, scaling, and structural impacts.

MST Cut-Cycle Properties and Uniqueness

Algorithms › Minimum Spanning Trees

Cut-Cycle Properties & Uniqueness

The theoretical engine behind every MST algorithm.

What you will master:

Defining cuts and cycles in graph theory.
The Cut Property: identifying "safe" edges.
The Cycle Property: identifying "unsafe" edges.
Conditions that guarantee a unique Minimum Spanning Tree.

Graph Basics: Cuts and Cycles

1. A Cut $(S, V - S)$

A partition of the graph's vertices into two disjoint sets, $S$ and $V - S$ .

Crossing Edge: An edge $(u, v)$ where one endpoint is in $S$ and the other is in $V - S$ .

2. A Cycle

A sequence of edges starting and ending at the same vertex, with no repeated vertices or edges in between.

Key Trait: Removing any single edge from a cycle does not disconnect the vertices involved.

The Cut Property: Finding Safe Edges

The Cut Property Theorem

Let $(S, V - S)$ be any cut of a connected graph $G$ . Let $e$ be the minimum-weight edge crossing this cut.

Then $e$ belongs to at least one Minimum Spanning Tree of $G$ .

Uniqueness Condition:

If edge weights are distinct (no two edges have the same weight), then $e$ is the strictly lightest edge crossing the cut. In this case, $e$ must be in every Minimum Spanning Tree.