|
|
A, B, C, D, E, F, G, H désignent 8 espèces de poissons. Dans le tableau ci-dessous, le caractère ê signifie que les espèces ne peuvent cohabiter dans un même aquarium.
|
|
A |
B |
C |
D |
E |
F |
G |
H |
|
A |
|
ê |
ê |
ê |
|
|
ê |
ê |
|
B |
ê |
|
|
|
ê |
ê |
ê |
|
|
C |
ê |
|
|
ê |
|
ê |
ê |
ê |
|
D |
ê |
|
ê |
|
ê |
|
|
ê |
|
E |
|
ê |
|
ê |
|
ê |
ê |
|
|
F |
|
ê |
ê |
|
ê |
|
|
|
|
G |
ê |
ê |
ê |
|
ê |
|
|
|
|
H |
ê |
|
ê |
ê |
|
|
|
|
|
|
1. Compléter le graphe ci-dessous en reliant par une arête (c’est normal pour des poissons) les espèces non compatibles entre-elles. On obtient ainsi un graphe d’incompatibilité. 2. Colorier le graphe à l’aide de l’algorithme de coloriage proposé ci dessous . 3. En étudiant les sous-graphes complets, démontrer que 4 couleurs sont nécessaires et suffisent. 4. Répartir les espèces dans les aquariums.
|
|
|
Algorithme |
|||||||
|
Liste ordonnée des sommets |
|
|
|
|
|
|
|
|
|
Boucle N°1 |
|
|
|
|
|
|
|
|
|
Boucle N°2 |
|
|
|
|
|
|
|
|
|
Boucle N°3 |
|
|
|
|
|
|
|
|
|
Boucle N°4 |
|
|
|
|
|
|
|
|
|
Coloriage final |
|
|
|
|
|
|
|
|