U.S.T.H.B.

,
Faculté d’Informatique 21 Janvier 2024
L3 (S5) Informatique

Corrigé de
l’Examen Final de
Théorie des Graphes
Durée 1h30’

Exercice 1. (08 pts.)

Huit (08) départements sont représentés ci-dessous avec leurs frontières. Deux départements avec une
frontière composée d’un nombre fini de points ne sont pas considérés comme voisins (Par exemple, le 2 et 3
sont voisins mais le 3 et 7 ne sont pas voisins).

1. Modéliser les relations de frontières entre les départements par un graphe G. (1)
On modélise par un graphe non orienté G=(X, E) comme suit :
− Chaque sommet xX représente un département.
− Chaque arête {x, y}E représente la relation : les départements x et y « sont voisins ». En d’autres
termes, ils ont une frontière constituée d’une infinité de points.
Ceci donne le dessin suivant :
5 4
2

6 3 8

7 1

2. G est-il complet ? G est-il connexe ? (0.5+0.75)

G n’est pas complet. Contre-exemple : 3 et 6 ne sont pas adjacents. C’est-à-dire {3, 6} E.
G est connexe. Il existe une chaîne qui passe par tous les sommets du graphe :  = 1 2 8 3 4 5 6 7.
On peut aussi appliquer l’algorithme de connexité (utilisant les marquage) ou l’algorithme d’exploration
(en profondeur ou en largeur) afin de prouver que G est connexe.

3. Calculer les degrés des sommets de G. Déduire le nombre d’arêtes. (0.5+0.75)

A partir du dessin, nous calculons les degrés de chaque sommet de G. Les résultats sont résumés par le
tableau ci-dessous :
Sommet xX 1 2 3 4 5 6 7 8
dG(x) 4 4 4 4 2 3 2 3
On peut déduire le nombre d’arêtes dans le graphe en utilisant la formule des degrés :
xX dG(x)=2|E|  2|E|=4+4+4+4+2+3+2+3=26  |E|= 13.

Page 1/2
USTHB, FI Corrigé de l’Examen de Théorie des Graphes 21/01/2024

4. Est-il possible d’aller d’un département donné, de franchir toutes les frontières une seule et unique fois
et d’y revenir ? (1)
Dans notre graphe, le problème revient à faire un parcours en démarrant d’un sommet, parcourir toutes les
arêtes une seule et unique fois et revenir au sommet de départ. Ains, le problème revient à vérifier si G
admet un cycle Eulérien.
Pour admettre un cycle Eulérien, le graphe doit être connexe et les degrés de tous les sommets doivent
être pairs. On a dG(6)=3 impair  Pas de cycle Eulérien  Impossible.

5. Est-il possible de parcourir tous les départements une seule et unique fois et revenir ? (1)
Dans notre graphe, le problème revient à faire un parcours en démarrant d’un sommet, parcourir tous les
sommets une seule unique fois (en utilisant les arêtes intermédiaires) et revenir au sommet de départ.
Ainsi, le problème revient à vérifier si G admet un cycle Hamiltonien.
Soit ’=6 5 4 2 8 3 1 7 6 est un cycle Hamiltonien  Possible.

6. Y a-t-il un département qui, s'il ferme ses frontières, d’autres départements ne seront plus reliés ? (1)
Un département qui ferme ses frontières correspond à déconnecter un sommet. En d’autres termes, revient à
vérifier si le graphe admet ou non un point d’articulation. C’est-à-dire si xX tel que G-{x} est non connexe.
G admet un cycle Hamiltonien (Question 5), la suppression d’un sommet quelconque x rend ce cycle chaine et
donc G-{x} reste connexe. Donc, si un département ferme ses frontières, les autres départements restent reliés.

7. Quel est le nombre maximal de départements qui n’ont pas de frontières communes mutuellement ? (1.5)
Le problème revient à chercher le plus grand stable possible dans le graphe G. La cardinalité (nombre
d’élément) de ce stable correspond au nombre maximal de départements n’ayant pas de frontières
communes.
Soit S={2, 5, 7} un stable d’ordre 3 dans G. S est le plus grand stable dans G. Car il n’y a aucun stable
d’ordre 4 dans G. En effet, les sommets de degrés 4 (1, 2, 3 et 4) ne peuvent pas faire partie d’un stable à
4. Les 4 sommets restant (5, 6, 7 et 8) ne forment pas un stable car au moins deux sont reliés entre eux
(par exemple 5 et 6).
|S|=3  3 départements au maximum.

Exercice 2. (05 pts.)

Un projet requiert la réalisation de six (06) tâches, le tableau suivant donne pour chaque tâche, le temps (en
jours) requis et les contraintes liées au début d’exécution des tâches.

Tâche i Durée de i Contraintes liées au début d’exécution de la tâche i

1 8 -
2 6 -
3 4 Tâche 1 terminée.
4 3 Tâche 1 terminée.
5 2 Tâches 1, 3 et 4 terminées
6 5 Tâches 1 et 2 terminées.

1. Donner la représentation du problème en graphe MPM (Potentiel-tâches). (1)

D’abord, on formule les contraintes du problème sous forme d’inéquations :
t3 − t1  8
t4 − t1  8
t5 − t1  8
t5 − t3  4
t5 − t4  3

Page 2/5
USTHB, FI Corrigé de l’Examen de Théorie des Graphes 21/01/2024

t6 − t1  8
t6 − t2  6
Où ti correspond à la date de début de la tâche i.
On introduit deux tâches fictives qu’on note :
0 : début du projet.
7 : Fin du projet.
Nous obtenons les contraintes supplémentaires suivantes :
t1 − t0  0
t2 − t0  0
t7 − ti  duréei i de 1 à 6.
Nous obtenons le graphe potentiel tâches (MPM) suivant :
8
3
1 4

0 8
8

0 8 2
4 5 7
3
0
5
2 6
6

2. Calculer les dates de début au plus tôt de chaque tâche et la durée optimale du projet. (0.75+0.25)
8 8
0 0 8
3
1 4
0 8
8
0 0 12 12 14 14
0 8 2
4 5 7
3
8 9
0
0 3
5
2 6
6
8 9
Les dates au plus tôt sont récapitulées sur le tableau ci-dessous :
Tâche i : 1 2 3 4 5 6
Date au plus tôt de i : 0 0 8 8 12 8
La durée optimale du projet correspond à la date au plus tôt de la tâche fictive de fin de projet (tâche 7) =
14 jours.

3. Calculer les dates au plus tard et déduire les tâches critiques. (0.75+0.25)
Les dates au plus tard sont récapitulées sur le tableau ci-dessous :
Tâche i : 1 2 3 4 5 6
Date au plus tôt de i : 0 3 8 9 12 9
Les tâches critiques sont celles qui ont la date au plus tôt et la date au plus tard identiques. Il s’agit des
tâches : 1, 3 et 5.

4. On veut réduire la durée de la tâche 5 d’une (01) journée à un coût C. Quel est l’impact sur la durée
optimale du projet ? (1)
La tâche 5 est une tâche critique qui est liée directement à la tâche fictive de fin de projet. Si on la réduit de
1 journée, la durée optimale du projet sera réduite d’une journée. La nouvelle durée du projet est 13 jours.

Page 3/5
USTHB, FI Corrigé de l’Examen de Théorie des Graphes 21/01/2024

5. Est-il intéressant de réduire encore la durée de la tâche 5 ? Justifier. (1)

La tâche 5 est une tâche critique qui est liée directement à la tâche fictive de fin de projet. Après avoir réduit
sa durée d’une journée, la tâche 6 (qui est liée directement à la tâche fictive de fin de projet) devient une
tâche critique. Toute réduction sur la tâche 5, n’aura aucun effet sur la durée du projet car la tâche 6
maintiendra sa durée à 13.

Exercice 3. (04 pts.)

Soit le réseau de transport ci-dessous (donné sous forme de tableau) ayant comme entrée (source) le
sommet E et comme sortie (puits) le sommet S. Pour chaque arc, le tableau ci-dessous donne sa capacité
ainsi que le flux initial.

Sommet de départ E E E A A A B B C C D

Sommet d’arrivée A B C B C D D S D S S

Capacité de l’arc 7 4 10 2 2 10 2 10 2 6 7

Flux initial de l’arc 7 4 6 0 0 7 0 4 0 6 7

1. Le flot initial est-il réalisable ? (1)

B
4/4 4/10
0/2 0/2

E 7/7
7/7 A 7/10 D S
0/2
0/2
6/10 6/6

C
Nous pouvons vérifier sur le réseau de transport et le flot donné les trois points suivants :
uU, 0≤(u)≤c(u) (Le flux d’un arc ne dépasse jamais sa capacité).
xX− {E, S},  flux entrant =  flux sortant ( Loi de Kirchhoff respectée)
 flux sortant de E =  flux entrant à S
Donc ce flot est réalisable.

2. Le flot initial est-il complet ? (1)

Le flot est complet car tout chemin de E vers S possède un arc saturé.

3. Le flot initial est-il optimal ? Si oui, prouver-le, sinon, trouver le flot optimal. (0.5+1.5)
Cherchons un chemin d’augmentation dans le graphe des résidus :
B
6
4
2 4
2
3 7
E 7 A D S
7
4 2
2
6 6

C
= E C D A B S est un chemin d’augmentation de capacité c()=2  Le flot n’est pas optimal (n’est pas
maximal)

Page 4/5
USTHB, FI Corrigé de l’Examen de Théorie des Graphes 21/01/2024

Calculons le flot maximal en appliquons l’algorithme de Ford-Fulkerson

On augmente le flot de 2 le long du chemin d’augmentation (= E C D A B S) et on obtient le flot suivant :
B
4/4 6/10
2/2 0/2

E 7/7
7/7 A 5/10 D S
0/2
2/2
8/10 6/6

Soit le graphe des résidus correspondant suivant :

B
4
4
2 6
2
5 7
E 7 A D S
5
2 2
2
8 6

C
Aucun chemin d’augmentation.
Donc le flot est maximal. C={(E, B), (A, B), (D, S), (C, S)} est une coupe.
La valeur du flot est 19.

Exercice 4. (03 pts.)

Montrer que tout graphe arbre est un graphe biparti. (3)
On veut montrer : G est un arbre  G est biparti.
On démontre par la contraposée : G n’est pas biparti  G n’est pas un arbre.
Un graphe G qui n’est pas biparti  son nombre chromatique (G)≠2
 Un des deux cas est possible :
(1) Soit (G)=1  G est un graphe discret (constitué uniquement de sommets isolés) G n’est pas
connexe  G n’est pas un arbre
(2) Soit (G)>2  G admet un cycle de longueur impaire  G n’est pas un arbre

Bon Courage

Page 5/5