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
[1]Lexique de la théorie des graphes. (2021, août 4). Wikipédia, l’encyclopédie libre. Page consultée le 16:55, août 4, 2021 à partir de http://fr.wikipedia.org/w/index.php?title=Lexique_de_la_th%C3%A9orie_des_graphes&oldid=185219024#P.