Graphes sans cycle : arbres, forêts et arborescences
Définition : Forêts et éléments d'une forêt
Une forêt est un graphe sans circuit F=(X,E) tel que pour tout point x de X, on a di(x) ≤ 1 (où di(x) est le demi-degré intérieur de x) ;
c'est-à-dire que tout point x est l'extrémité d'au plus un arc ou tout point a au plus un prédécesseur.
Une racine d'une forêt est un point x tel que di(x) = 0. Une racine n'a pas de prédécesseur.
Une feuille d'une forêt est un point x tel que de(x) = 0. Une feuille n'a pas de successeur.
Fondamental : Propriété mathématique
La fermeture transitive d'une forêt est une relation d'ordre.
Dans cette relation d'ordre, x inférieur ou égal à y s'il existe un chemin de x à y. Ce n'est pas une relation d'ordre total car certains points ne sont pas comparables.
Définition : Minorants dans une forêt
x est dit minorant de y dans la forêt F=(X,E) s'il existe un chemin de x à y.
x est dit minorant d'un sous-ensemble X' de points d'une forêt F=(X,E) s'il existe un chemin de x à tout point y de X'.
Fondamental :
Pour tout point x d'une forêt, il existe un unique chemin entre une et une seule racine de la forêt et le point x.
Tout point x appartient à la composante connexe d'une des racines.
Une forêt a le même nombre de racines que de composantes connexes.
Une composante connexe d'une forêt peut donc être désignée par son unique racine.
Définition : Arborescence
On appelle arborescence une forêt à une seule racine.
Une arborescence est donc une forêt connexe.
Les forêts sont des graphes dont les composantes connexes sont des arborescences.
Exemples de forêt et arborescence
Cliquez sur les flèches devant Suivant ou derrière Précédent pour faire tourner les exemples.
On a volontairement représenté deux fois les mêmes exemples, mais en inversant l'axe des x et l'axe des y pour obtenir à peu près les mêmes dessins à une rotation de 90° près.
Fondamental : Borne inférieure
Dans une arborescence, deux points quelconques x et y ont une borne inférieure.
La borne inférieure z est un ascendant commun aux points x et y tel qu'il n'y a pas d'autres ascendants communs à x et y sur les chemins qui vont de z à x et de z à y.
Définition : Définition des arbres
Un arbre est un graphe connexe sans cycle.
Remarque :
Une arborescence est toujours un arbre, mais la réciproque est fausse.
En effet, dans un arbre, le sens des arcs peut ne pas être dans le bon sens et dans ce cas, un point peut avoir plusieurs prédécesseurs.
Remarque :
Si on travaille sur des graphes non orientés où on ne précise pas le sens des arcs, on peut choisir le sens des arcs d'un arbre de telle sorte que l'arbre soit effectivement une arborescence.
Pour orienter un arbre et en faire une arborescence, il faut choisir un point comme racine et orienter tous les arcs de telle sorte que tous les chemins partent de cette racine.
Comme on peut choisir n'importe quel point de manière arbitraire, à un arbre (graphe non orienté) on peut faire correspondre n arborescences différentes en orientant les arcs en fonction de la racine choisie.
Fondamental :
Les propriétés suivantes sont équivalentes :
Un arbre est un graphe connexe sans cycle.
Un arbre est un graphe dans lequel tout couple de points x et y sont reliés par une chaîne unique.
Un arbre est un graphe connexe où le nombre d'arêtes est égal au nombre de points diminués de 1.
Un arbre est un graphe sans cycle où le nombre d'arêtes est égal au nombre de points diminués de 1.
Un arbre est un graphe connexe où la suppression d'une seule arête quelconque le rend non connexe.
Un arbre est un graphe sans cycle où l'adjonction d'une nouvelle arête crée un cycle et un seul.
Représentations
Nous verrons dans le chapitre sur les représentations des graphes que plusieurs représentations spécifiques ont été proposées pour représenter les forêts et les arborescences, qui permettent de limiter la mémoire utilisée tout en permettant d'utiliser efficacement ces graphes particuliers.
