FACULTE DES
SCIENCES DE Département d’informatique
MONASTIR Année Universitaire : 2019-2020
Travaux dirigés n° 2
(Correction)
Matière : Théorie des graphes
Filière : LFI2
Exercice n° 1
Un lycée doit organiser les horaires des examens. On suppose qu’il y a 7 épreuves à planifier,
correspondant aux cours numérotés de 1 à 7 et que les paires de cours suivantes ont des
étudiants communs : 1 et 2, 1 et 3, 1 et 4, 1 et 7, 2 et 3, 2 et 4, 2 et 5, 2 et 7, 3 et 4, 3 et 6, 3 et
7, 4 et 5, 4 et 6, 5 et 6, 5 et 7 et enfin 6 et 7.
Comment organiser ces épreuves de façon qu’aucun étudiant n’ait à passer deux épreuves en
même temps et cela sur une durée minimale ?
1ère Solution:
Construisons le graphe G dont les sommets sont les épreuves numérotées de 1 à 7, une arête
reliant deux sommets lorsque les deux cours correspondant possèdent des étudiants communs.
Planifier les examens en un temps minimal consiste à déterminer une k-coloration de G avec k
= γ(G) : G possède une clique d’ordre 4 (de sommets 1, 2, 3, 4), donc γ(G) ≥ 4. Déterminons
une partition des sommets de G en sous-ensembles stables : S1 = {1,5}, S2 = {2,6},S3 =
{3},S4 = {4,7}, d’où γ(G) ≤ 4. On en déduit que γ(G) = 4.
Les examens peuvent être répartis en 4 périodes, de la manière suivante :
1ère période (rouge) : épreuves des cours 1 et 5.
2ème période (vert) : épreuves des cours 2 et 6.
3ème période (jaune) : épreuve du cours 3.
4ème période (bleu) : épreuves des cours 4 et 7.
2ème Solution:
En appliquant l’algorithme de coloration on obtient :
deg sommet couleur
5 2 C1
5 3 C2
5 4 C3
5 7 C3
4 1 C4
4 5 C2
4 6 C1
1
Les examens peuvent être répartis en 4 périodes, de la manière suivante :
1ère période (rouge) : épreuves des cours 2 et 6.
2ème période (vert) : épreuves des cours 3 et 5.
3ème période (bleu) : épreuves des cours 4 et 7.
4ème période (jaune) : épreuve du cours 1.
Exercice n° 2
Une entremetteuse essaie de former le plus de couples possible avec 6 filles et 6 garçons en
fonction de critères esthétiques et de compatibilité d’humeur. Elle a dressé le tableau
d’incompatibilités ci-après, où une croix indique que deux personnes sont incompatibles.
Combien de couples pourra-t-elle former au maximum ?
Solution :
On cherche un couplage maximal dans le graphe biparti ci-dessous (qui représente les couples
possibles) :
Il existe un couplage parfait. Donc, on peut donc former six couples.
Exercice n° 3
Décrivez le graphe G ci-dessous par une matrice d’adjacences et des listes d’adjacences.
2
Matrice d’adjacences Liste d’adjacences
Exercice n° 4
Modéliser les différents arbres avec 1, 2, 3, 4, 5, 6, et 7 sommets ?
Exercice n° 5
Dessiner l’arbre correspondant à la suite S = {2,3,3,3} ou I = {1,2,3,4,5,6}
