Graph optimisation

Vocabulaire

English	Sens
cuts	Partitions of a graph's vertex set into two groups.
Kruskal	A minimum-spanning-tree algorithm adding edges in increasing weight order while avoiding cycles.

English

Light edges across cuts

A cut partitions the vertices; the lightest edge crossing it is safe to accept — the property behind Kruskal (sort, accept, reject cycles) and Dijkstra's settle step.

{exercise:uni-cs1005-cut}

Pratique

The light edge crossing a cut is —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui

English

Sorted: C–B 1, A–C 2, D–E 2, E–F 3, A–B 4, B–D 5, D–F 6, C–D 8, C–E 10. Accept C–B, A–C, D–E, E–F, B–D; reject the rest (cycles).
The MST weight is $1+2+2+3+5 = 13$, suite-verified. The proof: any tree plus a light crossing edge, minus the cycle's other crossing edge, keeps or lowers the weight.

{exercise:uni-cs1005-kruskal}

Pratique

Kruskal on the course graph yields MST weight —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui

English

Dijkstra settles a node and never reconsiders: on A→B (5), A→C (1), C→B (1), settling B at 5 misses the path of 2.
The light-edge guarantee needs non-negative weights; with negatives, Bellman-Ford's $\Theta(VE)$ relaxation rounds are the honest tool — and they detect negative cycles.

{exercise:uni-cs1005-negative}

Pratique

With edges A-B 5, A-C 1, C-B 1, settling-nearest Dijkstra fixes B at —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui