Kruskal, à la main

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.

Énoncé

Corrigé

Exercices semblables