Les arbres sont des graphes connexes sans cycle simple, c’est-à-dire qu’on ne peut établir une chaine dans ces graphes qui parte et se termine au même point sans passer deux fois par la même arête.
De façon générale, les arbres sont aussi utilisés en probabilités dans les problèmes de dénombrement.
Exemple d'arbre dans une situation problème en probabilité
De plus, on peut se servir des arbres pour déterminer le plus petit commun multiple (PPCM) d'un groupe de nombres.
Voici des exemples qui ne sont PAS des arbres.
Il n'est pas connexe!
BCDB est un cycle simple!
Un graphe valué est un graphe dans lequel chacune des arêtes présente une valeur. Le graphe valué peut être orienté ou non.
On calcule la valeur d’une chaine (ou d'un cycle) en faisant la somme des valeurs des arêtes qui la composent.
Un graphe orienté est un graphe dans lequel les arêtes ont un sens ( → ). Les chaines et les cycles doivent respecter le sens des flèches.
L’appellation d’une arête tient compte de son sens. AB ≠ BA
À l'occasion, on peut parler de graphe coloré. Un exemple de situation où ce concept est utilisé dans la résolution de problèmes par le nombre chromatique.