Nom et Prénom : …………………………………………………………

Université Alger 1, Dépt MI

2° année Mathématiques Groupe : ……………… Mat : ………………………………………
Mai 2017

EMD 1 – Théorie des Graphes

Exercice 1 (notions de base) 3 points
1. Qu’est-ce qu’une foret ? □ Un chemin qui passe par tous les sommets
0.5 pt □ Un ensemble d’arbres connectés. du graphe initial.
□ Un graphe non connexe, dont chaque
composante est un arbre. 5. Qu’est-ce qu’un graphe biparti ?
□ Un graphe partiel fortement connexe. 0.5 pt □Un graphe où le nombre de sommets est égal
au nombre d’arcs.
2. Qu’est-ce qu’un graphe connexe ? □ Un graphe ayant deux types de sommets, les
0.5 pt
□ Un graphe connecté arcs relient les sommets de mêmes types.
□ Un graphe orienté et valué □ Un graphe ayant deux groupes de sommets,
□ Un graphe sans boucle les arcs sortent d’un groupe pour aller vers
3. Qu’est-ce qu’un arbre ? l’autre.
0.5 pt □ Un sous graphe complet. 6. Qu’est-ce qu’un graphe eulérien ?
□ Un graphe fortement connexe et sans □ Un graphe possédant une chaine qui passe
boucle. 0.5 pt
par tous les sommets.
□ Un graphe connexe et sans circuit. □Un graphe possédant un circuit qui passe par
4. Qu’est-ce qu’un chemin simple ? tous les sommets.
□ Un chemin qui passe une seule fois par □ Un graphe possédant une chaine qui passe
0.5 pt chacun de ses arcs. par tous les arcs.
□ Un chemin qui passe une seule fois par
chacun de ses sommets.

Exercice 2 (modélisation) 2.5 points

Une cinémathèque, possédant plusieurs salles l’une à côté de l’autre, prévoit de projeter Groupe Films
6 nouveaux films : Titan (T), Rawski (R), Fordman (F), Bâtis (B), Dalton (D), Socrate (S). Le Souhaités
public attendu est réparti en plusieurs groupes, chaque groupe souhaite voir certains 1 T, R, F
films comme indiqué sur le tableau ci-opposé. 2 F, B
1. Modéliser cette problématique par un graphe. 3 D, S
2. Proposer un planning qui minimise le nombre de projections de films, et
4 B, S
permettant aux différents publics de voir les films qu’ils souhaitent.

Solution : Graphe Planning

1 pt
Plusieurs graphes peuvent R
modéliser cette situation. Le T F
graphe ci-contre à l’avantage de Séance 1 : T, B, D 0.4 pt
montrer directement le nombre S
B Séance 2 : R, S 0.4 pt
minimum de séances à prévoir et D
de construire ces séances. Séance 3 : F 0.4 pt

Une arête entre deux sommets x et y signifie qu’il y a un même

0.3 pt
public qui veut voir les films x et y.
Le sommet D n’est pas lié à T et B, on l’ajoute
Les sommets T, R et F sont liés, donc il faut les programmer donc à séance 1.
sur des séances différentes : 1, 2 et 3 resp.
Le sommet S est lié à D, donc pas possible de
Le sommet B n’est pas lié à T, donc on peut l’ajouter à séance 1. l’ajouter à séance 1, mais on peut l’ajouter à
séance 2 car il n’a pas de lien avec R.

EMD 1 – Théorie des Graphes Page 1

 Exercice 3 (arbre couvrant) 3 points 8
Soit le graphe valué et non orienté ci-opposé : b c
1. Retrouver un arbre couvrant de poids minimum à l’aide de 4 7
2
l’algorithme de Boruvka. 6
2. Calculer le poids de l’arbre. a e
5
3. Dessiner l’arbre. 1 12
d 9 g
Solution :
3 f 10
Initialisation :

0.25 pt F = { {a}, {b}, {c}, {d}, {e}, {f}, {g} }

0.75 pt
b c
0.25 pt Itération 1 : |F| = 7 >1
4 7 2
0.25 pt L = { ad, ab, ce, df, eg}
a e
0.25 pt F = { {ab, ad, df}, {ce, eg} }. 5
1
d g
0.25 pt Iteration 2 : |F| = 2 >1
3 f
0.25 pt L = {be}
0.25 pt F = { ab, ad, df, be, ce, eg }
0.25 pt Itération 3 : |F| = 1.

On arrête, on a obtenu un arbre couvrant.

0.25 pt Poids de l’arbre = 4 + 1 + 7 + 2 + 3 + 5 = 22.

Exercice 4 (plus courts chemins) 3 points

Soit le graphe suivant
1. Utiliser l’algorithme de Dijkstra pour retrouver les plus courts 1
a d 5
chemins entre le sommet 𝑎 et les autres sommets du graphe. 4
2. Produire les tableaux des distances D et des prédécesseurs P. f
9 c 7
3. Dessiner l’arborescence des plus courts chemins. 6
8 3
Solution : b e
2
a b c d e f
0 ∞ ∞ ∞ ∞ ∞ 0.25 pt pour
a 0 9a 4a 1a ∞ ∞ chaque ligne
0 1
1
a d
d 0 9a 4a 1a 8d 6d du tableau 5
6
4
c 0 9a 4a 1a 8d 6d 0. 75 pt
4 f
9 c 7
f 0 9a 4a 1a 8d 6d
e 0 9a 4a 1a 8d 6d b e
b 0 9a 4a 1a 8d 6d 9 8

a b c d e f

-a
D 0 9 4 1 8 6 0. 25 pt

P - a a a d d 0. 25 pt

EMD 1 – Théorie des Graphes Page 2

 Nom et Prénom : …………………………………………………………
Exercice 5 (flot maximum) 3 points
1. En utilisant la stratégie DFS, énumérer toutes les chaines Groupe : ……………… Mat : ………………………………………
qui relient le sommet 𝑠 au sommet 𝑡 du réseau suivant. 2
a b
2. Maximiser le flot dans ce réseau (en suivant les chaines 5 6
obtenues dans la question 1). s 4 t
3. Trouver une coupe minimale pour ce réseau. 1
Solution : 3 5
c d
1. Les chaines obtenues par DFS sont : 2
0. 10 pt pour C1 = s,a,b,d,t C2 = s,a,b,t C3 = s,a,d,b,t C4 = s,a,d,t
chaque chaine C5 = s,c,d,a,b,t C6 = s,c,d,b,t C7 = s,c,d,t -

2. Amélioration du flot le long des chaines :

Chaine Flot Maximal
Amélioration (𝜺) 0. 4 pt
C1 𝜀=0 a 2/2 b
3/5 5/6
0. 20 pt pour C2 𝜀=2
chaque chaine C3 𝜀=1 s 3/4 t
1/1
C4 𝜀=0
2/3 0/5
C5 𝜀=0 c d
C6 𝜀=2 2/2
C7 𝜀=0 La valeur du flot total 𝑓 = 5.
- -
0. 25 pt 3. Coupe minimale : 𝑌 = {𝑠, 𝑎, 𝑐} et 𝑌̅ = {𝑏, 𝑑, 𝑡}.
0. 25 pt Capacité de cette coupe : 𝑤(𝑌, 𝑌̅) = 2 + 1 + 2 = 5.

Exercice 6 (méthodes d’ordonnancement) 3 points

Les tâches d’un projet, ainsi que leurs durées et leurs
Tâches Antécédents Durées Successeurs
antécédents, sont donnés dans le tableau ci-opposé.
A - 6 B
0. 4 pt 1. Compléter la colonne des successeurs.
0. 8 pt 2. Ajouter les arcs, codes et durées des tâches sur le
B A 8 C, F
graphe PERT ci-dessous. C B 4 H
0. 8 pt 3. Calculer les dates au plutôt (𝑡1 ) et au plus tard (𝑡2 ). D - 3 E
0. 2 pt 4. Montrer le chemin critique. E D 2 H
0.8 pt 5. Calculer les marges de chacune des tâches. F B 7 G
G F 4 H
Solution :
H C, G, E 5 -

F7
4

21 21 G4
Chemin critique
1 B8 3

14 14 H5
A6 6 6 C4 5 F

D
25 25 30 30
0 0 D3 E2
2

3 23
Calcul des marges :

A : 6 – 6 – 0 = 0 ⟹ tâche critique E : 25 – 2 – 3 = 20 jours de marge libre

B : 14 – 8 – 6 = 0 ⟹ tâche critique F : 21 – 7 – 14 = 0 ⟹ tâche critique
C : 25 – 4 – 14 = 7 jours de marge libre G : 25 – 4 – 21 = 0 ⟹ tâche critique
D : 23 – 3 – 0 = 20 jours de marge libre H : 30 – 5 – 25 = 0 ⟹ tâche critique

EMD 1 – Théorie des Graphes Page 3

 Exercice 7 (théorie) 2.5 points
Démontrer le théorème suivant : Soit 𝐺 = (𝑋, 𝑈, 𝑊) un réseau. S’il existe une coupe (𝑌 ∗ , ̅̅̅
𝑌 ∗ ) de capacité
∗ ̅̅̅
∗ ∗
𝑤(𝑌 , 𝑌 ), et un flot de valeur 𝑓 tel que
𝑓 ∗ = 𝑤(𝑌 ∗ , ̅̅̅
𝑌∗)
alors 𝑓 ∗ est maximal et (Y ∗ , ̅̅̅
Y ∗ ) est une coupe minimale.

Solution :
Le flot qui passe de 𝑌 vers 𝑌̅ est
𝒀 𝒀
0.5 pt 𝑓= ∑ 𝑓(𝑥, 𝑦) − ∑ 𝑓(𝑦, 𝑥)
𝑥∈𝑌,𝑦∈𝑌̅ 𝑦∈𝑌̅,𝑥∈𝑌
Pour que ce flot soit maximal il faut que

0.5 pt ∑ 𝑓(𝑥, 𝑦) = 𝑚𝑎𝑥,

𝑥∈𝑌,𝑦∈𝑌̅
et

0.5 pt ∑ 𝑓(𝑦, 𝑥) = 0
𝑦∈𝑌̅,𝑥∈𝑌
Le terme ∑𝑥∈𝑌,𝑦∈𝑌̅ 𝑓(𝑥, 𝑦) prend sa valeur maximale 𝑓 ∗ lorsque 𝑓(𝑥, 𝑦) = 𝑤(𝑥, 𝑦) pour tout 𝑥 ∈ 𝑌 ∗ , 𝑦 ∈
̅̅̅
𝑌 ∗ . Dans ce cas on, aura

0.5 pt
𝑓∗ = ∑ 𝑓(𝑥, 𝑦) = ∑ 𝑤(𝑥, 𝑦) = 𝑤(𝑌 ∗ , ̅̅̅
𝑌∗)
̅̅̅̅∗
𝑥∈𝑌 ∗ ,𝑦∈𝑌 ̅̅̅̅∗
𝑥∈𝑌 ∗ ,𝑦∈𝑌

On sait aussi d’après le théorème de Ford-Fulkerson que toujours

0.5 pt
𝑓 ≤ 𝑤(𝑌, 𝑌̅)
Ceci confirme que 𝑓 est un flot maximum et 𝑤(𝑌 ∗ , ̅̅̅
∗
𝑌 ∗ ) une coupe minimale.

EMD 1 – Théorie des Graphes Page 4