Université Mohamed Boudiaf de M’sila Resp.Module: Dr.
Said GADRI
Faculté des mathématiques et de l’informatique
Département : Informatique
Module : Théorie des Graphes/L2LMD
TRAVAUX DERIGES - Série N° 06
Exercice 01 (Problème d’emploi du temps)
Les cours sont numérotés de 1 à 7
Les cours suivants ont des étudiants communs : (1, 2), (1, 3), (1, 4), (1, 7), (2, 3), (2, 4), (2, 5), (2, 7),
(3, 4), (3, 6), (3, 7), (4, 5), (4, 6), (5, 6), (5, 7), (6, 7).
Le graphe ci-après représente les cours ayant des étudiants communs
Comment organiser les examens de façon
1
qu’aucun étudiant n’ait passé deux examens 2
pour deux cours différents en même temps 7
==> les épreuves de cours ayants des 3
étudiants en commun ne doivent pas
s’organiser en même temps. 6
==> un problème de coloriage de sommet
4
k-coloriage de G avec k = (G) 5
{1, 2, 3, 4} est un sous graphe complet de G,
==> une clique maximale ==> (G) 4
Les sous-ensembles stables de G :
S1 = {1, 6}
S2 = {2}
S3 = {3, 5}
S4 = {4, 7}
==> (G) 4 ==> (G) = 4
Les examens peuvent être répartis en 04 périodes de la manière suivante :
1ière période, épreuves des cours 1, 6
2ième période, épreuves du cours 2
3ième période, épreuves des cours 3, 5
4ième période, épreuves des cours 4, 7
Solution 2 :
Sommet Degré Couleur
2 5 C1
3 5 C2
4 5 C3
7 5 C3
1 4 C4
5 4 C2
6 4 C1
Les groupes de coloriage sont : {2, 6}, {3, 5}, {4, 7}, {1}
Exercice 02 (Un problème d’aquariophilie)
A, B, C, D, E, F, G et H désignent huit poissons ; dans le tableau ci-dessous, une croix signifie
que les poissons ne peuvent cohabiter dans un même aquarium :
A B C D E F G H
A X X X X H
B X X X X
C X X X X X
D X X X X
E X X X X
F X X X
G X X X X
H X X X
Quel nombre minimum d’aquariums faut-il ?
On dessine le graphe d’incompatibilité : H(3) A(5)
Sommet Degré Couleur G(4) B(4)
A 5 C1
C 5 C2
B 4 C2
D 4 C3
F(3) C(5)
E 4 C1
G 4 C3
F 3 C1
H 3 C4
E(4) D(4)
Le nombre minimum d’aquariums est 4 (= nb. Couleurs)
Aqua1 : {A, E}
Aqua2 : {C, B}
Aqua3 : {D, G, F}
Aqua4 : {H}
Exercice 03
1. Remplissage du tableau
D
N
Sommets B C D F N T
Degrés des sommets 2 4 4 5 3 4 C T
B f
Graphe G
1. L graphe G est-il connexe ?
Oui le graphe est connexe, car chaque paire de sommet (x, y) est reliée par une chaîne.
2. Oui, le groupe peut passer par les six sommets en passant une fois et une seule par chaque
chemin. Pour prouver ça, on doit chercher une chaîne eulérienne dans le graphe G.
Et puisque le nombre de sommet de degré impaire est 2 (f, N) ==> une chaîne eulérienne dans le
graphe G ==> par exemple : {F, B, C, F, N, T, F, D, C, T, D, N}
3. Le groupe souhaite associer chaque sommet à une couleur de sorte que les sommets reliés par un
chemin n’ont pas la même couleur. (n le nombre chromatique du graphe).
a) Démonstration que : 4 n 6
Le degré maximal d’un sommet dans le graphe G est d(f) = 5
Et selon les propriétés vues au cours de ce chapitre, n dmax +1 ==> n 6
De plus, le sous graphe {C, F, D, T} d’ordre 4, est la plus grande clique dans G (le plus
grand sous graphe complet dans G) ==> n 4 (on a besoin au moins 04 couleurs pour le
colorier)
Donc, on obtient le suivant: 4 n 6
b) Proposition d’un coloriage du graphe en appliquant l’algorithme de Welch Powell
C3 D C2
Sommet Degré Couleur
N
F 5 C1 C4
C2 C T
C 4 C2
D 4 C3 C4
T 4 C4 B f
N 3 C2
C1
Graphe G
B 2 C4
Bon Courage
