Mathématique m1418

Les types de graphes

L'arbre

Les arbres sont des graphes connexes sans cycle simple, c’est-à-dire qu’on ne peut établir une chaîne dans ces graphes qui parte et se termine au même point sans passer deux fois par la même arête. 

  

On peut entre autres se servir des arbres pour déterminer le plus petit commun dénominateur de deux nombres.

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é

 

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 chaîne (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 chaînes 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.

Les vidéos
Les exercices
Les références