Université de Boumerdes
Faculté des Sciences.s Département de Mathématiques
3ème LMA .
Test N°1 Durée 25 minutes
Exercice n°1 : Une entreprise de commercialisation des aquariums possède huit espèces de
poissons notés : A, B, C, D, E, F, G et H, dans le tableau ci-dessous, une croix signifie que les
poissons ne peuvent cohabiter dans un même aquarium, l’objectif de l’entreprise est de déterminer
le minimum d’aquarium.
A B C D E F G H
A × × × × ×
B × × × ×
C × × × × ×
D × × × ×
E × × × ×
F × × ×
G × × × ×
H × × ×
Répondez aux questions suivantes :
a) Modélisez le problème en utilisant un graphe. Déterminez les sommets et les arêtes du graphe
pour représenter la situation.
b) Déterminez une partition en 4 sous-ensembles stables. Quelle est l’interprétation d’un en-
semble stable maximum dans le contexte de ce problème ?
c) Trouvez le plus grand sous-graphe complet (clique) dans le graphe modélisé précédemment.
d) Proposez une coloration du graphe en utilisant l’algorithme de coloration. Assurez-vous que
deux sommets adjacents n’ont jamais la même couleur.
e) Proposez un double encadrement pour le nombre chromatique χ(G) du graphe G.
f) Quel est le nombre minimum d’aquariums nécessaires pour que tous les poissons puissent
cohabiter sans problème ?(justifier)
==============================
Corrigé du test N°2
a)(2 Points) Modélisation du problème en utilisant un graphe. Déterminez les sommets et les arêtes du
graphe pour représenter la situation.
L’esemble de sommets : représenter chaque espèce de poisson.
Les arêtes du graphe seront déterminées par les paires d’espèces de poissons qui ne peuvent
pas cohabiter dans le même aquarium.
1
graphe.png
[h !]
b)(1 Point) Déterminez une partition en 4 sous-ensembles stables. Quelle est l’interprétation d’un en-
semble stable maximum dans le contexte de ce problème ?
Une partition en 4 sous-ensembles stables de ce graphe est la suivante :
Sous-ensemble 1 : B,C
Sous-ensemble 2 : A,E
Sous-ensemble 3 : H,G
Sous-ensemble 4 : G,F
c)(1 Point) Le plus grand sous-graphe complet (clique) dans ce graphe est formé par les sommets A,C,
D,H.
d)(2 Points) Une coloration du graphe peut être réalisée de la manière suivante :
Sommet A : Couleur 1
Sommet C : Couleur 2
Sommet B : Couleur 2
Sommet D : Couleur 3
Sommet E : Couleur 1
Sommet F : Couleur 3
Sommet G : Couleur 3
Sommet H : Couleur 4
e)(1 Point) Le double encadrement suivant pour le nombre chromatique χ(G) : 4 ≤ χ(G) ≤ 6.
f)(1 Point) le nombre minimum d’aquariums nécessaires pour que tous les poissons puissent cohabiter
sans problème est de 4. Nombre de coleures est de 4 (Algorithme)= la borne inferiere de
χ(G)
