Embed Size (px)
Citation preview
Quelques exemples de nombre chromatique d’un graphe.
Le nombre chromatique d’un graphe : c’est le nombre minimal de couleurs qu’il faut pour
colorier le graphe afin que deux sommets adjacents ne soient jamais de la même couleur
a
b
c
f
d
e
g
Le nombre chromatique d’un graphe : c’est le nombre minimal de couleurs qu’il faut pour
colorier le graphe afin que deux sommets adjacents ne soient jamais de la même couleur
b
c
f
d
e
g
Exemple de colorationd’un graphe avec 3 couleurs.
a
Quelques remarques simples :
• Puisqu’il y a un nombre fini de sommets, il existe toujours un plus petit nombre de couleurs. Le problème admet toujours une solution.
• Il n’y a pas forcément unicité du « coloriage minimum »
Il n’y a pas forcément unicité du « coloriage minimum »
a
b
c
d
e
a
b
c
d
e
Pour ce graphe, on peut trouver deux coloriages différents avec à chaque fois 3 couleurs.
Le problème ne dépend pas que du nombre de sommets.
• Sur cet exemple, 2 graphes ont le même nombre de sommets mais ils n’ont pas le même nombre chromatique
a
b
c
d
e
a
b
c
d
e
Par conséquent…
• On va étudier sur quelques exemples la recherche du nombre chromatique…
Nombre chromatique ?
a c
b
d
Nombre chromatique ?
a c
b
d
Réponse : 2
Nombre chromatique ?
a
e
c
b
d
Nombre chromatique ?
a
e
c
b
d
Réponse : 3
Nombre chromatique ?
a
e
c
b
d
f
Nombre chromatique ?
a
e
c
b
d
Réponse : 2
f
Nombre chromatique ?
a c
b
Nombre chromatique ?
a c
b
Réponse : 3
Nombre chromatique ?
a c
b
d
Nombre chromatique ?
a c
b
d
Réponse : 4
Nombre chromatique ?
a c
b
de
Nombre chromatique ?
a c
b
de
Réponse : 5
Conclusion :
Le nombre minimum de couleurs n’est pas tant lié au nombre de sommets qu’à la
complexité du graphe
