ArithmétiqueNotion · Glossaire
arbre couvrant
Un arbre couvrant d'un graphe non orienté et connexe est un sous-graphe qui est à la fois un arbre — c'est-à-dire un graphe connexe sans cycle — et qui inclut tous les sommets du graphe d'origine. Un arbre couvrant possède donc exactement n − 1 arêtes, n désignant le nombre de sommets du graphe. Un graphe connexe peut admettre plusieurs arbres couvrants distincts.
Sommaire
Ce que vous allez apprendre
- Reconnaître les conditions de connexité, de couverture et d'absence de cycle.
- Construire et contrôler un arbre couvrant sur un exemple à cinq sommets.
- Distinguer un arbre couvrant quelconque d'un arbre couvrant de poids minimal.
- Repérer les cas déconnectés, dégénérés et non uniques.
En clair
Imaginez cinq villes reliées par plusieurs routes. Pour garder toutes les villes accessibles tout en supprimant les détours qui forment des boucles, on conserve juste assez de routes pour relier l'ensemble. Le réseau obtenu est un arbre couvrant.
Chaque ville reste présente et il existe toujours un chemin entre deux villes. En revanche, retirer encore une route couperait le réseau, tandis qu'en ajouter une parmi les routes écartées recréerait un cycle.
Définition
Dans un graphe non orienté et connexe, un arbre couvrant est un sous-graphe qui conserve tous les sommets et une partie des arêtes. Les arêtes conservées doivent relier tous les sommets sans former aucun cycle. Ces deux conditions en font un arbre.
Si le graphe compte n sommets, tout arbre couvrant compte exactement n − 1 arêtes. Réciproquement, un sous-graphe qui conserve les n sommets et qui est connexe avec n − 1 arêtes est un arbre couvrant. Un graphe connexe possède au moins un arbre couvrant, mais celui-ci n'est généralement pas unique.
La notion ne choisit pas à elle seule le meilleur arbre. Lorsque les arêtes portent des poids, chercher un arbre couvrant de poids minimal ajoute un critère d'optimisation : on minimise la somme des poids parmi tous les arbres couvrants.
Un exemple, pas à pas
Considérons un graphe dont les sommets sont A, B, C, D et E. Ses sept arêtes sont AB, AC, BC, BD, CD, CE et DE. Nous cherchons un arbre couvrant parmi ces arêtes.
1. Conserver AB relie d'abord A à B.
2. Ajouter AC rattache C sans créer de cycle.
3. Ajouter BD rattache D sans créer de cycle.
4. Ajouter CE rattache E sans créer de cycle.
2. Ajouter AC rattache C sans créer de cycle.
3. Ajouter BD rattache D sans créer de cycle.
4. Ajouter CE rattache E sans créer de cycle.
Le sous-graphe obtenu contient les cinq sommets et les quatre arêtes AB, AC, BD et CE. Il est connexe et sans cycle : c'est donc un arbre couvrant. Le contrôle numérique donne bien 4 = 5 − 1. Retirer l'une des quatre arêtes déconnecte un sommet ou un groupe de sommets.
En pratique
Pour simplifier un réseau tout en gardant chaque point accessible, on retire successivement des arêtes appartenant à des cycles. On s'arrête dès que toute suppression supplémentaire déconnecterait le graphe.
Pour vérifier un candidat, on compte d'abord ses sommets et ses arêtes, puis on contrôle la connexité. Avec n sommets, la présence de n − 1 arêtes ne suffit pas si le sous-graphe est déconnecté.
Si les liaisons ont des coûts, un arbre couvrant quelconque assure seulement la connexion. Lorsque la somme des coûts doit être la plus faible, il faut rechercher un arbre couvrant de poids minimal, par exemple avec l'algorithme de Kruskal.
À ne pas confondre
Arbre couvrant et arbre couvrant de poids minimal. Le premier doit seulement couvrir tous les sommets sans cycle. Le second minimise en plus la somme des poids. Dans le graphe A–E, AB, AC, BD et CE forment un arbre couvrant, sans que l'absence de poids permette de le qualifier de minimal.
Arbre couvrant et sous-graphe. Un sous-graphe peut omettre des sommets, être déconnecté ou contenir un cycle. Un arbre couvrant doit au contraire conserver tous les sommets et rester connexe sans cycle. Les seules arêtes AB et AC donnent un sous-graphe du graphe A–E, mais pas un arbre couvrant.
Limites et pièges
Graphe déconnecté. Si deux groupes de sommets n'ont aucune liaison entre eux, aucun sous-graphe ne peut les rendre connexes. Il n'existe alors pas d'arbre couvrant du graphe entier ; on peut seulement construire un arbre dans chaque composante connexe.
Le compte n − 1 ne suffit pas. Un sous-graphe à n sommets et n − 1 arêtes peut encore être déconnecté et contenir un cycle dans l'une de ses composantes. Il faut contrôler la connexité, ou contrôler conjointement l'absence de cycle.
Cas d'un seul sommet. Pour n = 1, l'arbre couvrant conserve l'unique sommet et possède 0 arête. Ce cas satisfait bien n − 1 = 0 ; une arête n'est donc pas toujours nécessaire.
Unicité non garantie. Plusieurs choix d'arêtes peuvent relier tous les sommets sans cycle. Dans le graphe A–E, remplacer AC par BC dans l'arbre AB, AC, BD, CE fournit encore un arbre couvrant.
Pour aller plus loin
Le graphe connexe précise la condition qui garantit l'existence d'un arbre couvrant.
La fiche Sous-graphe éclaire l'opération de sélection des sommets et des arêtes dans un graphe.
L'algorithme de Kruskal montre comment obtenir un arbre couvrant de poids minimal dans un graphe pondéré.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres