4.5 Nombre chromatique

Le nombre chromatique est le nombre minimale que l'on peut colorier un dessin, par exemple une carte du monde, sans que la même couleur soit utilisée pour 2 région limitrophes.

4.4 Chemin critique, Arbre de valeur minimale

4.3 Arbre et graphe valué

Un arbre est un graphe qui n'a pas de cycle simple. Si l'arête A-E était présente, cela créerait un cycle simple et le graphe ne serait plus un arbre.

 

Quelque définition d'un graphe valué.

Voici un exemple d'un graphe valué.