Les types de graphes
Secondaire 5
L'arbre
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.
Attention!
Voici des exemples qui ne sont PAS des arbres.
Il n'est pas connexe!
BCDB est un cycle simple!
Le graphe valué
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.
Le graphe orienté
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.
Important!
L’appellation d’une arête tient compte de son sens. AB ≠ BA
En savoir plus
À 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.
Dans cette page
