Arbres et arbres couvrants

Relier dix sites par de la fibre, au moindre coût total, sans laisser personne isolé : c'est le problème de l'arbre couvrant minimal, et deux algorithmes le résolvent exactement, en quelques lignes, sans jamais se tromper. Les commutateurs d'un réseau local calculent eux aussi un arbre couvrant, pour la raison inverse : l'arbre couvrant d'un réseau local bloque juste assez de liens pour qu'aucune boucle ne subsiste. Ce n'est pourtant pas l'arbre de poids minimal : chaque commutateur y garde son chemin le moins cher vers un commutateur racine, et la fin du chapitre montre que les deux arbres diffèrent en général. Avant d'y arriver il faut comprendre l'objet lui-même, l'arbre, dont les propriétés sont si contraintes qu'elles se déduisent les unes des autres.

L'arbre, quatre définitions pour un seul objet

Définition

Un arbre est un graphe connexe et sans cycle.

Cette définition en cache trois autres, toutes équivalentes pour un graphe à $n$ sommets. C'est le genre de théorème qui sert constamment, parce qu'il permet de vérifier la propriété la plus commode.

Formulation	Ce qu'elle permet de vérifier vite
connexe et sans cycle	la définition
connexe avec exactement $n - 1$ arêtes	compter les arêtes suffit
sans cycle avec exactement $n - 1$ arêtes	compter les arêtes suffit
un unique chemin élémentaire entre chaque paire	l'unicité du trajet

Graphe non orienté6 sommets, 5 arêtes

Six sommets, cinq arêtes, d'un seul tenant : un arbre. Ses feuilles sont D, E et F.

Six sommets, cinq arêtes, connexe : c'est un arbre. Ajouter n'importe quelle arête crée un cycle ; en retirer une coupe le graphe en deux.

Un arbre est exactement à la limite. Un arbre est maximalement sans cycle : toute arête ajoutée crée un cycle.
Il est en même temps minimalement connexe : toute arête retirée le déconnecte.
Ces deux phrases disent la même chose et expliquent pourquoi $n - 1$ est à la fois le minimum d'arêtes pour être connexe et le maximum pour rester sans cycle.

Conclure sans dessiner

« Un graphe a 12 sommets et 11 arêtes. Est-ce un arbre ? »
On ne peut pas conclure :

m = n - 1

est nécessaire, pas suffisant. Le graphe pourrait être un triangle plus une composante à part, ce qui donne bien 11 arêtes sans être un arbre.
Il faut une information de plus : connexe, ou sans cycle. Avec l'une des deux, c'est un arbre.

Feuilles et racine

Un sommet de degré 1 s'appelle une feuille. Tout arbre ayant au moins deux sommets en possède au moins deux. Aucun sommet n'y est de degré 0, puisque l'arbre est connexe ; si au plus un sommet était de degré 1, tous les autres seraient de degré au moins 2, et la somme des degrés vaudrait au moins $1 + 2(n-1) = 2n - 1$ , alors qu'elle vaut $2(n-1) = 2n - 2$ .

Un arbre n'a pas de racine en soi. Enraciner un arbre, c'est choisir un sommet comme origine, ce qui oriente implicitement toutes les arêtes et donne les notions de père, de fils, de profondeur. C'est un choix de lecture, pas une propriété du graphe.

Vérification rapideon peut se reprendre

Un réseau connexe relie 12 sites par 14 liaisons. Combien de liaisons faut-il couper, au minimum, pour qu'il ne reste aucune boucle sans isoler aucun site ?

Arbre couvrant

Définition

Un arbre couvrant d'un graphe connexe $G$ est un sous-graphe qui contient tous les sommets de $G$ , et qui est un arbre.

Si $G$ est pondéré, un arbre couvrant minimal est un arbre couvrant dont la somme des poids est la plus petite possible.

Tout parcours en produit un gratuitement : l'arbre de parcours du chapitre précédent, formé des arêtes par lesquelles chaque sommet a été découvert, est un arbre couvrant. Mais rien ne garantit qu'il soit de poids minimal, puisque le parcours ignore les poids.

Les liaisons redondantes d'un réseau

Un graphe connexe qui n'est pas un arbre a des arêtes en trop. Si l'on en garde un arbre couvrant, chaque arête restée hors de l'arbre y referme exactement un cycle. Un graphe connexe à $n$ sommets et $m$ arêtes porte donc $m - n + 1$ cycles indépendants : c'est le nombre de liaisons redondantes d'un réseau, celles qu'on peut perdre une à une sans isoler personne. Un réseau de 12 sites et 18 liaisons en a $18 - 12 + 1 = 7$  ; un arbre n'en a aucune, et la moindre coupure le sépare en deux morceaux.

L'exemple du chapitre

Voici le graphe qui servira d'exemple : huit liaisons possibles entre six sites, avec leur coût. Les coûts sont tous différents, ce qui aura son importance.

Graphe non orienté et pondéré6 sommets, 8 arêtes

Huit liaisons possibles entre six sites, avec leur coût.

Kruskal, arête par arête

Principe

Trier les arêtes par poids croissant, puis les examiner une par une : on garde une arête si elle ne crée pas de cycle avec celles déjà retenues, sinon on la jette.

On s'arrête quand on a $n - 1$ arêtes.

Kruskal est un algorithme glouton : à chaque étape, il fait le choix qui paraît le meilleur sur le moment, ici l'arête la moins chère encore disponible, et ne revient jamais sur ce choix.

Sur l'exemple, les arêtes triées par poids croissant valent 1, 2, 3, 4, 5, 8, 10 et 11 : la figure les liste dans cet ordre sous le dessin, chacune avec son état. Kruskal ne part d'aucun sommet : il prend E -- D, la moins chère de tout le graphe, puis A -- C, qui ne la touche pas. Deux morceaux séparés coexistent alors, chacun de sa couleur, jusqu'à ce que C -- E les recolle.

Arbre couvrant minimal, Kruskal6 sommets, 8 arêtes

0 / 6

Voir

Algorithme

Cliquer un poids pour le modifier.

En gras : les arêtes retenues ; tiretées en rouge : les rejetées ; en pointillé : celles qui ne seront pas examinées. Chaque morceau de plus d'un sommet a sa couleur et son numéro ; ★ marque son représentant, ce que rend trouver.

Arêtes triées par poids

E-D1à examiner
A-C2à examiner
C-E3à examiner
A-B4à examiner
B-C5à examiner
E-F8à examiner
B-D10à examiner
D-F11à examiner

Groupes (union-trouve) {A} · {B} · {D} · {F} · {E} · {C}

Poids des arêtes retenues : 0

Kruskal examine les arêtes de la plus légère à la plus lourde, sans partir d'aucun sommet. Au départ, chaque sommet est seul dans son groupe, et en est le représentant.

Kruskal prend les arêtes de la moins chère à la plus chère, et deux morceaux séparés coexistent jusqu'à ce que C-E les recolle. Seules les arêtes comptent : Kruskal ne part d'aucun sommet.

À manipuler

Dérouler pas à pas. Après A -- C, compter les morceaux : deux, de deux couleurs, chacun avec un sommet marqué d'une étoile, qui le représente. Au pas de B -- C, lire le récit : les deux extrémités ont le même représentant, A, et c'est pour cela que l'arête est rejetée, pas pour son poids.
Cliquer ensuite le poids de B -- C, le passer à 3 et dérouler de nouveau : c'est maintenant A -- B, de poids 4 seulement, qui est rejetée, et l'arbre pèse 17. À 4, les deux arêtes pèsent autant : la figure signale alors un second arbre minimal, de même poids.

L'arbre obtenu pèse $1 + 2 + 3 + 4 + 8 = 18$ . L'arête B -- C de poids 5 a été rejetée : ses deux extrémités étaient déjà reliées par A -- C et A -- B, donc la retenir aurait fermé un triangle. Les arêtes de poids 10 et 11 ne sont même pas examinées : l'arbre a ses $n - 1 = 5$ arêtes dès E -- F.

Pourquoi un glouton donne ici l'optimum exact

Un glouton ne revient jamais sur un choix, et rien ne garantit en général qu'il trouve l'optimum : le chapitre sur la coloration en montrera un qui se trompe selon l'ordre dans lequel il traite les sommets, et le chapitre sur les gloutons du parcours Algorithmique en donne d'autres exemples. Ici, il est exact, et la raison porte un nom : la propriété de coupe.
Couper les sommets en deux groupes, de n'importe quelle façon. L'arête de poids minimal qui traverse la coupe appartient à un arbre couvrant minimal. Chaque arête retenue par Kruskal est exactement de cette forme : la plus légère qui relie un morceau au reste du graphe, puisque toute arête plus légère a déjà été examinée.
C'est ce théorème qui transforme une heuristique en algorithme exact, et il vaut la peine d'être su : il justifie aussi Prim.

Détecter le cycle : union-trouve

Le seul point délicat de Kruskal est le test « cette arête crée-t-elle un cycle ? ». Le refaire par un parcours à chaque arête coûterait $O(m \times n)$ . La bonne structure répond en temps quasi constant.

Union-trouve

Une structure union-trouve maintient une partition d'un ensemble en groupes disjoints, avec deux opérations : trouver(x) donne le représentant du groupe de x, et unir(x, y) fusionne deux groupes.

Une arête crée un cycle si et seulement si ses deux extrémités ont déjà le même représentant.

Ce sont les morceaux colorés de la figure de Kruskal, et l'étoile y marque le représentant de chacun ; le récit de chaque pas écrit les deux appels à trouver, et c'est leur comparaison, et elle seule, qui rejette B -- C. Concrètement, chaque groupe est rangé comme un petit arbre. Chaque sommet note son père, et le représentant est la racine, le seul sommet qui est son propre père. trouver(x) remonte de père en père jusqu'à elle. Pour unir deux groupes, on accroche la racine de l'un sous la racine de l'autre, jamais un sommet quelconque : réécrire le père d'un sommet qui n'est pas une racine le détacherait de son groupe, et le test de cycle se mettrait à mentir. Les deux raffinements du code ci-dessous, l'union par rang et la compression de chemin, ne changent rien au résultat : ils gardent ces petits arbres plats, et c'est ce qui rend chaque test quasi instantané.

main.py

Sortie

>_ Prêt à exécuter…

Vérification rapideon peut se reprendre

Kruskal examine une arête dont les deux extrémités sont déjà dans le même groupe. Il…

Prim, sommet par sommet

Principe

Partir d'un sommet quelconque et faire grossir un seul arbre : à chaque étape, ajouter l'arête de poids minimal qui relie l'arbre à un sommet encore extérieur.

La différence avec Kruskal se résume en une phrase : Kruskal fait grandir plusieurs morceaux qui finissent par se rejoindre, Prim fait grandir un seul morceau depuis le départ.

Arbre couvrant minimal, Prim depuis A6 sommets, 8 arêtes

0 / 6

Voir

Algorithme

Cliquer un poids pour le modifier, un sommet pour en faire le départ.

Plein : les sommets de l'arbre. En gras : ses arêtes ; tiretées : les arêtes au bord de l'arbre, entre lesquelles Prim choisit la plus légère ; en pointillé : les arêtes devenues intérieures.

Tas, la plus légère d'abord

(2, A, C)
(4, A, B)

Arbre : aucune arête encore · poids 0

Prim part de A : l'arbre ne contient que lui. Le tas reçoit les arêtes qui en partent.

Prim fait grossir un seul arbre depuis A. Il obtient le même arbre que Kruskal, de poids 18, mais dans un autre ordre.

À manipuler

Dérouler en regardant le tas sous le dessin : les arêtes tiretées sont celles du bord de l'arbre, et le tas les tient rangées de la plus légère à la plus lourde, sous la forme (poids, u, v) du code plus bas. Au cinquième pas, l'entrée (5, C, B) ressort alors que B est déjà dans l'arbre : elle est jetée.
Cliquer ensuite un autre sommet pour en faire le départ : l'ordre d'ajout change, l'arbre reste le même. Enfin, passer à la vue « comparer » : depuis B, l'arbre des plus courts chemins garde B -- C et pèse 21 au lieu de 18, mais chaque site y est au plus près de B.

Le résultat est le même arbre, de poids 18, mais l'ordre d'ajout diffère : Kruskal a pris E -- D en premier, parce qu'elle est la moins chère de tout le graphe ; Prim ne l'a prise qu'en troisième, une fois E entré dans son arbre. Que l'arbre soit le même n'est pas un hasard : les poids sont ici tous distincts, et dans ce cas l'arbre couvrant minimal est unique (la fin du chapitre dit pourquoi), donc les deux algorithmes ne peuvent que tomber dessus.

	Kruskal	Prim
Fait grandir	plusieurs morceaux	un seul arbre
Structure clé	union-trouve	file de priorité
Complexité	$O(m \log m)$ , dominée par le tri	$O(m \log n)$ avec un tas, $O(n^2)$ avec un simple tableau
Meilleur sur	graphe creux	graphe dense, dans sa version à tableau

À chaque étape, Prim doit retrouver la plus légère des arêtes qui bordent l'arbre. Le code les range dans une structure faite pour cela.

File de priorité

Une file de priorité est une réserve dont on retire toujours l'élément de plus petite valeur, et non le plus ancien comme dans une file ordinaire. En Python, le module heapq la réalise sur une simple liste, rangée en tas : heapify(liste) range d'un coup une liste existante, heappush(tas, x) ajoute un élément, heappop(tas) retire le plus petit, ces deux dernières en $O(\log n)$ . Un triplet (poids, u, v) se compare d'abord par son poids, ce qui suffit à ranger des arêtes.

Le mot « tas » désigne ici cette structure de données, sans rapport avec la zone de mémoire du même nom dans le parcours sur le langage C.

main.py

Sortie

>_ Prêt à exécuter…

Trois confusions classiques

Arbre couvrant minimal et plus court chemin ne sont pas la même chose. L'arbre minimise le poids total des arêtes ; il ne garantit rien sur le trajet entre deux sommets donnés, qui peut y être plus long que dans le graphe complet. Sur l'exemple, l'arbre relie B à C en passant par A, pour

4 + 2 = 6

, alors que la liaison directe B-C, rejetée, ne coûte que 5 : la vue « comparer » de la figure de Prim pose les deux arbres côte à côte.
Prim n'est pas l'algorithme de plus court chemin du chapitre suivant. Prim compare le poids de l'arête ; l'algorithme de Dijkstra comparera la distance cumulée depuis le départ. Une seule expression changera dans le code, et le résultat n'aura plus le même sens.
Des poids égaux ouvrent plusieurs solutions. Si deux arêtes ont le même poids, l'arbre minimal peut ne pas être unique : il y en a alors plusieurs, tous de même poids total.

Vérification rapideon peut se reprendre

L'arbre couvrant minimal donne-t-il le plus court chemin entre deux sommets ?

Mettre en pratique

Un graphe a 12 sommets et 11 arêtes. Est-ce un arbre ?

On ne peut pas conclure. La relation $m = n - 1$ est nécessaire mais pas suffisante.

Contre-exemple : un triangle sur trois sommets, plus un arbre à neuf sommets et huit arêtes, séparément. Total : 12 sommets, 11 arêtes, et ce n'est pas un arbre puisque le graphe n'est ni connexe ni sans cycle.

Avec une information de plus, connexe ou sans cycle, la conclusion devient immédiate : c'est un arbre.

Pourquoi tout arbre d'au moins deux sommets a-t-il au moins deux feuilles ?

Par le lemme des poignées de main. Un arbre a $n - 1$ arêtes, donc la somme des degrés vaut $2(n-1) = 2n - 2$ .

Si tous les sommets étaient de degré au moins 2, la somme vaudrait au moins $2n$ , ce qui est strictement plus grand. Il y a donc au moins un sommet de degré 1.

Pour en obtenir deux : aucun sommet n'est de degré 0, puisque l'arbre est connexe et a au moins deux sommets. S'il n'y avait qu'une seule feuille, tous les autres sommets seraient de degré au moins 2, et la somme vaudrait au moins $1 + 2(n-1) = 2n - 1 > 2n - 2$ . Contradiction.

Kruskal examine une arête dont les deux extrémités sont dans le même groupe. Que fait-il et pourquoi ?

Il la rejette.

Si les deux extrémités ont déjà le même représentant dans la structure union-trouve, c'est qu'un chemin les relie déjà parmi les arêtes retenues. Ajouter celle-ci fermerait donc un cycle, et un arbre n'en contient aucun.

Ce rejet est correct même si l'arête est légère : la propriété de coupe garantit que les arêtes déjà retenues, toutes plus légères ou de même poids, appartiennent bien à un arbre minimal.

Quelle différence entre l'arbre couvrant minimal et l'arbre des plus courts chemins ?

Ils optimisent deux choses différentes.

L'arbre couvrant minimal minimise la somme totale des poids des arêtes retenues. C'est le bon objet pour « poser le moins de câble possible ».

L'arbre des plus courts chemins depuis un sommet $s$ , que l'algorithme de Dijkstra construit au chapitre suivant, minimise, pour chaque sommet, la distance depuis $s$ . C'est le bon objet pour « aller vite depuis $s$  ».

Sur un même graphe, les deux diffèrent en général. Sur l'exemple du chapitre, l'arbre des plus courts chemins depuis B garde la liaison B-C (5) au lieu de A-C (2) : chaque site y est au plus près de B, mais l'arbre pèse $4 + 5 + 3 + 1 + 8 = 21$ , contre 18 pour l'arbre minimal. À l'inverse, dans l'arbre minimal, aller de B à C coûte 6 au lieu de 5.

C'est aussi ce qui sépare l'arbre des commutateurs de l'introduction de l'arbre minimal. Trois commutateurs, dont l'un est la racine : deux liaisons de coût 4 relient la racine aux deux autres, une liaison de coût 2 relie ces deux-là entre eux. Chaque commutateur garde son chemin le moins cher vers la racine, la liaison directe de coût 4, et l'arbre retenu pèse 8 ; l'arbre minimal garde la liaison de coût 2 et une seule des deux autres, pour un poids de 6.

Quand préférer Prim à Kruskal ?

Sur un graphe dense, où $m$ approche $n^2$ .

Kruskal commence par trier les $m$ arêtes, ce qui coûte $O(m \log m)$  : sur un graphe dense, cela fait de l'ordre de $n^2 \log n$ .

Prim avec un tas coûte $O(m \log n)$ , et avec une implémentation par tableau sur graphe dense, $O(n^2)$ , ce qui est meilleur.

Sur un graphe creux, où $m \approx n$ , les deux sont équivalents et Kruskal est souvent plus simple à écrire correctement.

L'arbre couvrant minimal est-il unique ?

Oui si tous les poids sont distincts. Non en général.

Avec des poids tous différents, la propriété de coupe devient plus forte : l'arête la plus légère qui traverse une coupe appartient à tout arbre couvrant minimal. Si un arbre minimal ne la contenait pas, on pourrait l'y ajouter : elle fermerait un cycle, qui traverse forcément la coupe une seconde fois, par une arête plus lourde. Retirer cette arête plus lourde donnerait un arbre couvrant plus léger, ce qui est impossible.

Or chaque arête retenue par Kruskal est la plus légère d'une coupe, celle qui sépare son morceau du reste du graphe. Les $n - 1$ arêtes retenues appartiennent donc à tous les arbres minimaux, qui n'ont eux-mêmes que $n - 1$ arêtes : il n'y en a qu'un.

Avec des poids répétés, plusieurs arbres peuvent atteindre le même poids total minimal. C'est pourquoi Kruskal et Prim peuvent renvoyer des arbres différents sur un tel graphe, sans qu'aucun ne soit faux.

L'arbre, quatre définitions pour un seul objet

Feuilles et racine

Arbre couvrant

Les liaisons redondantes d'un réseau

L'exemple du chapitre

Kruskal, arête par arête

Détecter le cycle : union-trouve

Prim, sommet par sommet

Mettre en pratique

Dans la bibliothèque d'exercices

Détecter le cycle : union-trouve