forêt - graphe -

Imaginez plusieurs réseaux de points reliés par des traits. Dans chacun, il existe un chemin entre certains points, mais aucun trajet ne revient à son point de départ sans reprendre une liaison. L'ensemble forme une forêt.

Chaque morceau connecté est un arbre. Ajouter une liaison entre deux points déjà reliés créerait un cycle ; relier deux arbres distincts les réunirait au contraire en un arbre plus grand.

Une forêt est un graphe non orienté sans cycle. Elle peut être connexe ou comporter plusieurs composantes connexes. Chacune de ces composantes est un arbre, puisque ses sommets sont reliés entre eux et qu'elle ne contient aucun cycle. Un arbre est donc exactement une forêt connexe.

Appelons n le nombre total de sommets et k le nombre de composantes connexes. Une forêt finie possède alors exactement $n-kn-k$ arêtes. Cette identité fournit aussi un contrôle : dans un graphe non orienté acyclique, chaque nouvelle arête reliant deux composantes diminue leur nombre d'une unité.

Un sommet de degré 1 est une feuille ; un sommet de degré au moins 2 est interne. Il faut aussi prévoir les sommets isolés, de degré 0 : chacun constitue à lui seul une composante-arbre. Enfin, toute forêt est bipartie, car l'absence de cycle exclut notamment les cycles de longueur impaire.

Une forêt se décrit par ses sommets, ses arêtes non orientées et ses composantes connexes. Les arêtes relient les sommets deux à deux. Les composantes regroupent les sommets entre lesquels un chemin existe ; chacune doit rester sans cycle.

Le degré d'un sommet compte ses arêtes incidentes : il repère les feuilles, les sommets internes et les éventuels sommets isolés. Le choix des arêtes détermine à la fois les degrés et le découpage en composantes. En revanche, la position des points, la longueur des traits et leur couleur ne définissent pas la forêt. En notant n le nombre de sommets, k celui des composantes et m celui des arêtes, ces données permettent de vérifier l'identité $m=n-km=n-k$.

Considérons une forêt de sept sommets répartis en deux composantes. La première contient quatre sommets et trois arêtes ; la seconde contient trois sommets et deux arêtes. Dans chaque composante, tous les sommets sont reliés sans qu'un cycle apparaisse. La figure matérialise ces données et permet de refaire les comptages.

Données.
Nombre de sommets : n = 7.
Nombre de composantes : k = 2.
Arêtes de la première composante : 3.
Arêtes de la seconde composante : 2.

1. Le comptage direct donne 3 + 2 = 5 arêtes.
2. La formule d'une forêt donne $n-k=7-2=5n-k=7-2=5$.
3. Les deux résultats coïncident : la forêt possède exactement 5 arêtes.

Pour contrôler l'absence de cycle, retirez mentalement une arête quelconque : la composante concernée se sépare en deux morceaux. À l'inverse, une arête supplémentaire placée entre deux sommets déjà reliés dans la même composante fermerait un cycle.

Dans une structure de données hiérarchique, plusieurs arbres indépendants forment une forêt. On parcourt alors chaque composante séparément ; un arbre unique convient seulement si tous les éléments partagent la même racine ou restent connectés.

Dans un algorithme de recherche, conserver des arêtes sans fermer de cycle produit progressivement une forêt. Une arête reliant deux composantes peut être ajoutée ; une arête reliant des sommets déjà connectés doit être écartée si l'on veut préserver l'acyclicité.

Pour contrôler un graphe fini non orienté, on note m son nombre d'arêtes, n son nombre de sommets et k son nombre réel de composantes. L'égalité $m=n-km=n-k$ caractérise alors une forêt ; tout écart révèle qu'au moins un cycle est présent.

Forêt et arbre. Une forêt peut avoir plusieurs composantes connexes, tandis qu'un arbre est connexe. Dans l'exemple à deux composantes, l'ensemble est une forêt, mais chacune des deux composantes est un arbre.

Forêt et graphe biparti. Toute forêt est bipartie, mais un graphe biparti peut contenir un cycle de longueur paire. Un carré formé de quatre sommets et quatre arêtes est biparti ; comme il contient un cycle, ce n'est pas une forêt.

Sommet isolé. Son degré vaut 0, et non 1 : ce n'est ni une feuille au sens donné ici ni un sommet interne. Il constitue pourtant un arbre à un sommet et doit compter comme une composante de la forêt.

Composantes mal comptées. Deux groupes éloignés sur un dessin ne forment pas forcément deux composantes, et le croisement de deux traits n'est un sommet que s'il est déclaré comme tel. Il faut suivre les chemins du graphe avant d'utiliser $m=n-km=n-k$.

Arête ajoutée. Entre deux composantes distinctes, elle réduit le nombre de composantes de 1 sans créer de cycle. À l'intérieur d'une même composante, ses extrémités sont déjà reliées par un chemin : l'ajout ferme alors un cycle et détruit la propriété de forêt.

L'article arbre - graphe - approfondit le cas où la forêt ne possède qu'une seule composante connexe.

La fiche graphe connexe précise la relation de chemin qui découpe une forêt en arbres indépendants.

La notion de graphe biparti prolonge la propriété de coloration en deux groupes, tout en montrant que la réciproque est fausse.