Kruskal, à la main

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 23 — Unir & trouver, arbres couvrants

Énoncé

Sur le graphe à sept sommets $a, \dots, g$ dont les arêtes sont

$ab : 7, a d : 5, b c : 8, b d : 9, b e : 7, ce : 5, d e : 15, df : 6, e f : 8, e g : 9, f g : 11,$

dérouler Kruskal : donner l'ordre de tri, les arêtes prises, les arêtes écartées et le poids total.

Corrigé

Ordre de tri (poids croissant ; les ex æquo se départagent comme on veut) :


ad(5) ce(5) df(6) ab(7) be(7) bc(8) ef(8) bd(9) eg(9) fg(11) de(15)

Le déroulé, en suivant les classes :

Arête	Classes avant	Décision	Classes après
$a d (5)$	$a ∣ d$	prise	$a d$
$ce (5)$	$c ∣ e$	prise	$a d ∣ ce$
$df (6)$	$a d ∣ f$	prise	$a df ∣ ce$
$ab (7)$	$a df ∣ b$	prise	$ab df ∣ ce$
$b e (7)$	$ab df ∣ ce$	prise	$ab c d e f$
$b c (8)$	$b$ et $c$ ensemble	écartée	---
$e f (8)$	$e$ et $f$ ensemble	écartée	---
$b d (9)$	ensemble	écartée	---
$e g (9)$	$ab c d e f ∣ g$	prise	tout
$f g (11)$	ensemble	écartée	---
$d e (15)$	ensemble	écartée	---

Six arêtes prises — soit $n - 1 = 6$ , comme annoncé —, cinq écartées, et un poids total de

$5 + 5 + 6 + 7 + 7 + 9 = 39.$

Une force brute sur les $2^{11}$ sous-ensembles confirme : ce graphe possède $141$ arbres couvrants, le plus léger pèse $39$ , et c'est le seul de ce poids.

Deux remarques de méthode. L'algorithme s'arrête quand il a $n - 1$ arêtes : les quatre dernières lignes du tableau sont du travail inutile, et une mise en œuvre soignée sort de la boucle dès que le compteur atteint $n - 1$ . Et si, en fin de parcours, on n'en a pas $n - 1$ , c'est que le graphe n'est pas connexe — Kruskal le détecte sans effort supplémentaire.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.