Introduction aux arbres
Définition : Première définition des arbres
Un arbre est un graphe connexe sans cycle.
Remarques
Lorsque l'on travaille sur les arbres, l'orientation n'a aucun intérêt, c'est pourquoi dans ce chapitre, nous ne travaillerons que sur des graphes non orientés ou "symétriques" constitués d'un ensemble de points X et de l'ensemble E des arêtes qui lient certains de ces points entre eux.
Un graphe est connexe s'il existe une chaîne entre tout couple de points, c'est-à-dire si l'on peut en utilisant les arêtes passer de tout point x à tout point y.
Un graphe est sans cycle s'il n'existe pas de chaîne allant de x à x en passant par un ou plusieurs autres points.
Animation donnant des exemples d'arbres
Cliquez sur précédent et suivant pour observer des représentations graphiques d'arbres.
Propriété des arbres
Un arbre de n points comporte exactement n-1 arêtes.
Un arbre est donc un graphe connexe sans cycle possédant n-1 arêtes. Deux de ces propriétés suffisent pour définir des arbres. D'où deux nouvelles défnintions des arbres.
Intérêt concret de la notion d'arbre
Si on considère un ensemble de points et que l'on cherche à les connecter (de manière directe ou indirecte en utilisant d'autres points) en utilisant le moins possible d'arêtes, on obtient obligatoirement un arbre.
Dans un réseau, par exemple un réseau d'ordinateurs, on utilise donc des arbres pour effectuer des connexions si on veut minimiser le nombre de lignes de connexion.
Par contre, comme le nombre d'arêtes est minimal, dès l'instant où une des liaisons est rompue, alors le graphe n'est plus connexe. Le critère de minimisation du nombre de liaisons dans un réseau est donc antagoniste avec la recherche d'un maximum de fiabilité.
Pour la fiabilité, on pourra s'intéresser, par exemple, aux graphes 2-connexes (qui restent connexes quelques soient l'arête que l'on supprime, lorsque l'on supprime au plus une arête), mais ces graphes ne sont pas des arbres.
Définition : Deuxième définition des arbres
Un arbre est un graphe connexe comportant n-1 arêtes (où n est son nombre de points).
Définition : Troisième définition des arbres
Un arbre est un graphe sans cycle comportant n-1 arêtes (où n est son nombre de points).
Autre propriété des arbres
Les arbres sont des graphes planaires. C'est-à-dire que l'on peut toujours trouver une représentation graphique d'un arbre où les arêtes ne se coupent pas.
L'animation ci-dessous reprend les graphes de l'animation précédente en changeant la position des points de telle sorte que les arcs ne se coupent pas.
