Arbres et arbres couvrants
Ce que ce chapitre apporte
- Reconnaître un arbre par n'importe laquelle de ses définitions équivalentes.
- Utiliser la relation m = n - 1 pour conclure sans dessiner.
- Distinguer arbre couvrant et arbre couvrant minimal.
- Dérouler Kruskal et Prim, et dire ce qui les distingue.
- Expliquer pourquoi un algorithme glouton donne ici l'optimum exact.
- Employer une structure union-trouve pour détecter les cycles en temps quasi constant.
L'arbre, quatre définitions pour un seul objet
Un arbre est un graphe connexe et sans cycle.
Cette définition en cache trois autres, toutes équivalentes pour un graphe à 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 arêtes | compter les arêtes suffit |
| sans cycle avec exactement arêtes | compter les arêtes suffit |
| une unique chaîne élémentaire entre chaque paire | l'unicité du trajet |
Six sommets, cinq arêtes, connexe : c'est un arbre. Ajoutez n'importe quelle arête et vous créez un cycle ; retirez-en une et le graphe se coupe en deux.
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.
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 : si tous les sommets étaient de degré au moins 2, la somme des degrés vaudrait au moins , alors qu'elle vaut .
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.
Arbre couvrant
Un arbre couvrant d'un graphe connexe est un sous-graphe qui contient tous les sommets de , et qui est un arbre.
Si 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.
Voici le graphe qui servira d'exemple. Sept liaisons possibles entre cinq sites, avec leur coût.
1.Un graphe a 12 sommets et 11 arêtes. Est-ce un arbre ?
2.Kruskal examine une arête dont les deux extrémités sont déjà dans le même groupe. Il…
3.L'arbre couvrant minimal donne-t-il le plus court chemin entre deux sommets ?
Kruskal, arête par arête
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 arêtes.
Déroulez : les arêtes retenues s'épaississent, et l'on voit la forêt se recoller morceau par morceau.
L'arbre obtenu pèse . 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.
Coupez 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 deux morceaux encore séparés.
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 . La bonne structure répond en temps quasi constant.
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.
Prim, sommet par sommet
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.
Le résultat est le même arbre, de poids 21, mais l'ordre d'ajout diffère. Ce n'est pas un hasard : quand tous les poids sont distincts, l'arbre couvrant minimal est unique, 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é | pour le tri | avec un tas |
| Meilleur sur | graphe creux | graphe dense |
Prim n'est pas Dijkstra. Prim compare le poids de l'arête, Dijkstra compare la distance cumulée depuis le départ. Une seule expression change dans le code, et le résultat n'a plus le même sens.
Les poids doivent être comparables. Si deux arêtes ont le même poids, l'arbre minimal peut ne pas être unique : il y en a plusieurs, tous de même poids total.
Exercices type
Un graphe a 12 sommets et 11 arêtes. Est-ce un arbre ?
On ne peut pas conclure. La relation 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 arêtes, donc la somme des degrés vaut .
Si tous les sommets étaient de degré au moins 2, la somme vaudrait au moins , ce qui est strictement plus grand. Il y a donc au moins un sommet de degré 1.
Pour en obtenir deux : s'il n'y en avait qu'un seul, la somme vaudrait au moins . 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, 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 minimise, pour chaque sommet, la distance depuis . C'est le bon objet pour « aller vite depuis ».
Sur un même graphe, les deux diffèrent en général : dans l'arbre couvrant minimal, le trajet de à peut être bien plus long que le plus court chemin réel.
Quand préférer Prim à Kruskal ?
Sur un graphe dense, où approche .
Kruskal commence par trier les arêtes, ce qui coûte : sur un graphe dense, cela fait de l'ordre de .
Prim avec un tas coûte , et avec une implémentation par tableau sur graphe dense, , ce qui est meilleur.
Sur un graphe creux, où , 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 désigne à chaque étape une arête sans ambiguïté, donc tous les algorithmes corrects aboutissent au même arbre.
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.
La méthode
- Compte les arêtes avant de dessiner : est le premier réflexe.
- Ne conclus jamais « arbre » sur le seul comptage : il faut connexe ou sans cycle en plus.
- Trie les arêtes pour Kruskal, prends un tas pour Prim.
- Teste le cycle par union-trouve, jamais par un parcours à chaque arête.
- Vérifie que tu as arêtes à la fin : sinon le graphe n'était pas connexe.
- Ne confonds pas poids total minimal et plus courts chemins.
- Méfie-toi des poids égaux si l'énoncé demande l'unicité.
En résumé
- Un arbre est connexe et sans cycle ; il a exactement arêtes.
- Quatre définitions équivalentes : on vérifie la plus commode.
- Un arbre est minimalement connexe et maximalement sans cycle.
- Tout arbre d'au moins deux sommets a au moins deux feuilles.
- Un arbre couvrant contient tous les sommets ; le minimal minimise le poids total.
- Kruskal trie les arêtes et recolle des morceaux ; Prim fait grossir un seul arbre.
- La propriété de coupe est ce qui rend ces gloutons exacts.
- Union-trouve répond « cycle ou non » en temps quasi constant.
- L'arbre minimal est unique si tous les poids sont distincts.
Et ensuite ? Minimiser le câble total n'est pas minimiser un trajet. Le chapitre suivant traite l'autre question, celle du plus court chemin, et l'algorithme qui la résout.