ـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ

Les types de graphes

L'arbre
Le graphe valué
Le graphe orienté
Le graphe coloré

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