5 – arbres et arborescence

arbre

arbre: Un arbre est un graphe acyclique et d’un seul tenant.

racine

racine: Sommet particulier d’une arborescence à partir duquel il existe un chemin unique vers tous les autres sommets du graphe. [1]

arborescence ou arbre enraciné

arborescence: Une arborescence est un graphe acyclique orienté contenant une racine.

Note

Aucune arête ne pointe donc vers la racine, tandis que tous les autres nœuds sont pointés par exactement une arête.

exemple

code

digraph mon_graphe {
   a -> b;
   a -> c;
   a -> d;
   c -> e;
   c -> f;

   a [label="racine"];
}

(voir en ligne)

représentation graphique

../../../_images/arborescence.svg