Graphes : Travaux Dirigés

3 MIC

MJ. HUGUET
homepages.laas.fr/huguet

Consignes générales
Les TD Graphes durent 7 séances. Lors de ces séances vous travaillerez en groupe de 4 à 5 personnes (le groupe
doit rester identique sur l’ensemble des séances). Les exercices notés (*) seront traités en séance, les exercices
complentaires peuvent être traités en travail personnel.
Il est vivement conseillé de travailler entre les séances de cours et de TD (relire les notions abordées, reprendre
les exercices ayant posé des difficultés).

Remerciements
Ce support a bénéficié des contributions de collègues de l’INSA ou du LAAS (Colette Mercé, Patrick Esqui-
rol, Pierre Lopez, Nicolas Jozefowiez, Mikael Capelle, Pierre-François Gimenez 1 ). Il s’est également inspiré
d’exercices posés par des collègues d’autres établissements d’enseignement supérieur.

Ce document a été rédigé avec LATEX. Les graphes sont générés avec TikZ.

1. si oubli, ils sont involontaires !

1 Définitions et Modélisations 1.2 Lemme des poignées de mains
Le lemme des poignées de main dit que dans tout
1.1 Championnat (*) graphe non orienté (ayant un nombre fini de som-
Cinq équipes, notées A, B, C, D, E, font partie d’un mets) le nombre de sommets de degré impair est soit
même championnat. Chaque équipe doit rencontrer nul soit pair. De manière imagée, dans une réunion
deux fois les 4 autres équipes (à domicile et à l’exté- de plusieurs personnes dont certaines se serrent la
rieur). Certaines rencontres ont déjà eu lieu et sont main, un nombre pair de personnes devra serrer un
résumées dans le tableau 1. nombre impair de fois la main d’autres personnes.
Demontrez ce lemme.
Equipe est allé rencontrer
A C, D, E
B A, D 1.3 Graphe inversé (*)
C A, B, E On considère le graphe orienté G1 de la figure 1
D A, B, C
E B, C, D Question 1. Construisez le schéma du graphe in-
versé G−1 (il s’agit juste de renverser le sens des
Table 1 – Rencontres passées 1
arcs). Le graphe G−1 1 fournit-il plus ou moins d’in-
formation que le graphe G1 ?
Question 1. Représentez le graphe des rencontres.
Question 2.
Question 2. Donnez la matrice d’adjacence du graphe.
a Soit M (G1 ) la matrice d’adjacence du graphe
G1 , par quelle opération matricielle peut-on ob-
Proposez une interprétation de : tenir la matrice M (G−1 1 ) ? Quelle est la com-
Question 3.
plexité de cette méthode ?
a la somme de chaque ligne de la matrice
b Soit T ab(G1 ) la liste d’adjacence du graphe G1 ,
b la somme de chaque colonne de la matrice
proposez une méthode (ie. un algorithme) pour
c la somme de tous les termes de la matrice obtenir T ab(G−11 ) et donnez sa complexité.

Question 4. Comment déterminer (via la matrice

Question 3. Pour un graphe orienté donné, peut-il
d’adjacence) le nombre de rencontres jouées par chaque
être intéressant de mémoriser la liste des successeurs
équipe. Quelle est la complexité ?
et la liste des prédécesseurs de chacun des sommets ?
Question 5. Avec une liste d’adjacence, quelle est Justifiez vos réponses.
la complexité pour calculer :
a b
a pour une équipe X donnée : le nombre de ren-
contres à l’extérieur et le nombre de rencontres
à domicile ?
b pour toutes les équipes du championnat : le c g
d
nombre de rencontres à l’extérieur et à domi-
cile ?
c le nombre total de rencontres ?
e f h
Question 6. Quelle est la représentation ayant la
meilleure complexité pour chacun de ces calculs ?
Figure 1 – Graphe G1

2
1.4 Recupérer du liquide (*)
On doit récupérer 4 litres d’un liquide contenu dans
un tonneau (de grande contenance). Nous disposons
pour cela de deux récipients contenant respective-
ment 5 litres et 3 litres. Ces deux récipients ne sont
pas gradués, nous ne connaissons que leur contenance
totale.

a Modélisez ce problème par un graphe : définis-

sez les sommets et les arcs
b Quelles sont les caractéristiques de ce graphe ?
c Proposez une solution sur ce graphe permet-
tant d’obtenir la quantité attendue

3
2 Parcours de Graphes supérieur ou égal à 2 alors G possède au moins un
cycle.
Travail personnel préparatoire Nous n’allons pas chercher à montrer cette propriété
(voir les livres ou sites internet sur le sujet).
2.1 Applications des algo (*) Remarque : une conséquence de cette propriété est
qu’un graphe non orienté sans cycle possède au moins
On considère le graphe non orienté G2 de la figure 2
un sommet de degré 0 ou 1.
d
Question 1. Graphe acyclique et nombre d’arêtes.
a Montrez, par induction sur le nombre de sommets,
qu’un graphe acyclique d’ordre n (ie. ayant n som-
mets) possède au plus n − 1 arêtes.
e h

g Question 2. Recherche d’un cycle. La propriété

s b
précédente ne permet pas d’obtenir un cycle dans le
graphe non orienté. Vous allez déterminer une mé-
f
thode pour cela.

c i a Proposez une méthode, basée sur un algorithme

de parcours en profondeur, pour obtenir un
cycle.
Figure 2 – Graphe G2
b Appliquez votre méthode sur le graphe de la
figure 2, puis sur le même graphe dans lequel
vous supprimez les arêtes (a, e) et (a, i).
Question 1. Parcours en profondeur. Appli-
quez l’algorithme de parcours en profondeur sur le
graphe G2 à partir du sommet s. Lorsque plusieurs 2.3 Tri topologique (*)
sommets peuvent être sélectionnés, choisissez l’ordre L’ensemble des composants (ie. chapitres) d’une for-
alphabétique. Représentez l’arborescence obtenue et mation peut être représenté par le graphe orienté de
la numérotation des sommets (marqués comme visi- la figure 3. Dans ce graphe, les sommets représentent
tés). les enseignement et il y a un arc du sommet x vers
le sommet y si le chapitre x est un pré-requis du
Question 2. Parcours en largeur. Appliquez l’al- chapitre y.
gorithme de parcours en largeur sur le graphe G2
à partir du sommet s. Lorsque plusieurs sommets i
peuvent être sélectionnés, choisissez l’ordre alphabé-
tique. Représentez l’arborescence obtenue et la nu-
mérotation des sommets (marqués comme visités).
h e

Question 3 (optionnelle). Parcours dans des d

graphes orientés. Reprenez le graphe G1 de la
section 1 pour appliquer un parcours en profondeur j f k
et un parcours en largeur à partir du sommet a. g

b c
2.2 Cycle - Graphe non orienté
Soit un graphe non orienté G, il existe une propriété a
aussurant l’existence d’un cycle dans un tel graphe.
Cette propriété est : si tout sommet de G est de dégré
Figure 3 – Maquette d’une formation

4
Pour une meilleure lisibilité on souhaite ré-organiser 3. et ainsi de suite : classez dans chaque niveau
la représentation du graphe de telle sorte que tous les sommets dont les prédécesseurs sont dans
les arcs soient orientés de la gauche vers la droite. les niveaux antérieurs.

Question 1. Schéma. Question 1. Appliquez cette méthode au graphe

de la figure 3 et donnez le graphe obtenu
a Proposez un schéma avec cette ré-organisation
b Est-ce toujours possible ? Question 2. Que se passe-t-il si le graphe com-
porte un cycle ?
Définition. Une telle représentation peut s’appuyer
sur une relation d’ordre entre les sommets, appelée Question 3. Comment feriez-vous (au niveau im-
ordre topologique. Avec cette relation d’ordre, un nu- plémentation) pour déterminer si tous les prédéces-
méro est associé à chaque sommet, tel que le numéro seurs d’un sommet sont classés dans un niveau ?
du sommet x est inférieur au numéro du sommet y
s’il y a un arc de x vers y.

Question 2.

a Proposez une adaptation d’un parcours en pro-

fondeur pour obtenir un ordre topologique des
sommets
b Appliquez votre méthode à l’exemple et don-
nez l’ordre topologique obtenu (représentez la
solution dans le tableau ci-dessous).
c Pour un graphe donné, l’ordre topologique des
sommets est-il unique ? Justifiez.
d Peut-on obtenir un ordre topologique des som-
mets lorsque le graphe comporte un cycle ?
e Pourriez-vous adapter un parcours en largeur ?

1 2 3 4 5 6 7 8 9 10 11

2.4 Décomposition en niveaux (*)

La représentation basée sur l’ordre topologique ne
permet pas de connaitre les composants pouvant être
enseignés en « parallèle ». Pour cela, nous allons re-
prendre le graphe de la figure 3 et considérer une
décomposition en niveaux du graphe. Le principe de
la méthode de décomposition est le suivant :

1. le premier niveau est composé de tous les som-

mets sans prédécesseurs
2. le second niveau est composé de tous les som-
mets dont les précédesseurs sont déjà classés
dans le premier niveau

5
3 Exercices complémentaires temps de prendre connaissance de ce que vous avez
fait ....).
Les exercices proposés sont liés aux notions abordées
dans les sections 1 et 2. x19 x1

3.1 Parcourir un labyrinthe x7 x4 x2 x9

Nous disposons d’une carte, donnée en figure 4 re- x5
présentant un labyrinthe dans lequel il y a plusieurs x3
entrées et un trésor.
x6 x13
x8 x11

x12 x14 x16

x10
x17
x15
x18

Figure 5 – Réseau social (extrait)

Figure 4 – Carte du labyrinthe
A partir de votre réseau social (vous êtes le sommet
x1 ), vous souhaitez connaitre la liste des personne
Question 1. Modélisation. ayant vu votre travail en fonction de l’heure.

a Modélisez ce labyrinthe par un graphe Détermination de la diffusion de cette contri-

b Donnez les caractéristiques de ce graphe bution.

a Proposez une adaptation d’un parcours en lar-

Question 2. Chasse au trésor.
geur pour répondre à cette question.
a Proposez une adaptation d’un parcours en pro- b Appliquez votre méthode pour connaitre les
fondeur permettant de découvrir le trésor contacts ayant eu connaissance de votre contri-
b Votre adaptation donne-t-elle le trajet à suivre ? bution géniale en 2 heures, puis en 3 heures.
Si ce n’est pas le cas, ajoutez une nouvelle ad- c Pourriez-vous proposez une adaptation d’un par-
patation pour mémoriser le trajet. cours en profondeur ? Justifiez.

3.2 Faire le buzz 3.3 Composantes fortement connexes

Votre réseau social est représenté par le graphe de la Question 1. Application de l’algorithme Soit
figure 5. Vous venez de réaliser une contribution gé- G3 le graphe orienté de la figure 6. Appliquez l’algo-
niale (article, vidéo, démonstration de P 6= NP 2 ) que rithme de calcul des composantes fortement connexes
vous diffusez immédiatement à vos contacts. Ceux-ci et donnez l’ensemble des composantes obtenues.
la re-diffusent dans l’heure qui suit à leurs propres
contacts. Votre contribution est tellement exception-
Question 2. Application de la définition. Soit
nelle qu’elle se propage de manière virale aux contacts
G un graphe orienté a n sommets. Combien de com-
de vos contacts. On supposera que la diffusion entre
posantes fortement connexes comporte un tel graphe
deux personnes en contact se fait dans l’heure (le
lorsque :
2. rayez la mention inutile

6
 x13 x14 x15 x16

x9 x10 x11 x12

x5 x6 x7 x8

x1 x2 x3 x4

Figure 6 – Graphe G3

a le graphe G est sans circuit.

b le graphe G comporte un circuit élémentaire de
longueur n.

Question 3. Graphe réduit Soit un graphe orienté

G ayant m composantes fortement connexes, notées
C1 , . . . , Cm . On appelle graphe réduit de G, le graphe
G0 comportant m sommets x01 , . . . , x0m tels que chaque
sommet de G0 corresponde à une composante forte-
ment connexe de G. Dans le graphe réduit, il existe
un arc de x0i vers x0j s’il existe un sommet x appar-
tenant à Ci et un sommet Y appartenant à Cj et un
arc de x vers y dans G.

a Donnez le graphe réduit de l’exemple de la fi-

gure 6.
b Montrez pour tout graphe orienté G, son graphe
réduit G0 est sans circuit.

7
4 Plus court chemin c, faut-il re-lancer l’algorithme ? Justifiez la ré-
ponse.
4.1 Application des algo (*) c Dans le cas général que faut-il faire ? Justifiez
Algorithme de Dijkstra. Soit le graphe non orienté la réponse.
valué G4 de la figure 7. d Pouvez-vous utiliser d’autres algorithmes à la
place de l’algorithme de Dijkstra ? Pourquoi
10 utiliser celui de Dijkstra plutôt qu’un autre ?
b c
1
1 10 2 2 Algorithme de Bellman-Ford. Soit le graphe orienté
4 valué G5 de la figure 8.
d e 5
11 1
a 5 5 8 j d
-3
6 3 5
f g
6 -4
3 2 3 5
4 b 1
h i a 2 -2 e
8
c
1 8
Figure 7 – Graphe non orienté valué G4
3
Utilisez l’algorithme de Dijkstra pour calculer le plus f
court chemin entre le sommet a et le sommet j. Pour
cela, utilisez le tableau de calcul ci-dessous. La pre-
Figure 8 – Graphe non orienté valué G5
mière ligne de ce tableau correspond à l’étape d’ini-
tialisation de l’algorithme. Chaque itération de l’al-
Utilisez l’algorithme de Bellman-Ford pour calculer
gorithme est représentée par une nouvelle ligne dans
le plus court chemin depuis le sommet a vers le som-
le tableau de calcul : sélection du sommet devant être
met b. Pour cela, utilisez le tableau de calcul ci-
marqué puis actualisation des sommets adjacents.
dessous. La première ligne de ce tableau correspond
S’il y a plusieurs choix possibles pour sélectionner
à l’étape d’initialisation de l’algorithme. Chaque ité-
le sommet à marquer, utilisez l’ordre alphabétique.
ration de l’algorithme correspond à une ligne dans le
a b c d e f g h i j tableau de calcul : actualisation de tous les sommets
init du graphe pris dans l’ordre alphabétique.
1
a b c d e f
2
init
3
1
4
2
5
3
6
4
7
5
8
6
9
10
Donnez le chemin obtenu et son coût.

a Donnez le chemin obtenu de a vers j et son 4.2 Centre d’un graphe

coût.
Pour lutter contre les incendies, la ville de Maximim-
b Si on cherche le plus court chemin de f vers les-Pins cherche à déterminer où installer un poste de

8
secours, de telle façon que chaque secteur à surveiller
ne soit pas trop loin du poste. Pour l’aider dans sa 1
tâche, on va s’appuyer sur des méthodes de graphes
8
et utiliser la notion de centre d’un graphe, définie x1 x2
ci-dessous. 3 5
Soit un graphe G = (X, U ) où X représente l’en-
semble des sommets et U l’ensemble des arcs (ou 4
x6 1 3 x3
arêtes). Pour 2 sommets x et y, on appelle sp(x, y) la
longueur du plus court chemin/chaîne allant de x à
1 1
y (cette longueur vaut ∞ si de tels chemins/chaînes
x5 x4
n’existent pas). 2
L’écartement d’un sommet x, noté E(x), repré-
sente la distance maximum à parcourir pour aller
d’un sommet x vers tous les autres sommets du graphe. Figure 9 – Réseau à surveiller
Il est défini par : E(x) = maxy∈X,y6=x (sp(x, y)).
Un véhicule de secours situé en un point x du graphe x1 x2 x3 x4 x5 x6 E(x)
pourra atteindre chaque point y (y 6= x) en au plus x1
E(x) étapes. x2
Le centre d’un graphe, noté c, est un sommet x3
d’écartement minimum : c = argminx∈X (E(x)). Pour x4
être le moins éloigné de l’ensemble des points qu’il a x5
sous sa surveillance, un poste de secours devra être x6
installé au centre du graphe.
Table 2 – Résultats : sp(x, y) et E(x)
Question 1. Choix d’une méthode.
2
x1 x2
a Quelles sont les méthodes de résolution pos-
4 4
sibles.
b Quelle méthode choisissez-vous ? Justifiez et faites 1
x6 2 x3
valider votre choix.
1 1
Question 2. Application.
x5 x4
3
a Appliquez la méthode au graphe de la figure 9
(partagez-vous le travail !). Utilisez le tableau 2
fourni pour noter vos résultats.

• Donnez les valeurs sp(x, y) pour toutes les

paires de sommets du graphe. Figure 10 – Nouveau réseau à surveiller
• Donnez les valeurs E(x) pour tous les som-
mets du graphe. 4.3 Isochrones (*)
• Quel est le centre du graphe ?
Lors de l’implantation de nouveaux services (trans-
Les définitions d’écartement d’un sommet et de centre port, aménagement, magasin), on peut être amené à
d’un graphe données précédemment restent valables réaliser des études d’accessibilité. Ces études visent
dans le cas de graphes orientés. Sans faire de cal- à établir les parties d’un graphe accessibles à partir
cul, déterminez le centre du graphe de la figure 10. d’un point donné tout en se fixant une limite dans
Justifiez votre réponse. le parcours de ce graphe. Par exemple : évaluer dans
un graphe routier les zones accessibles (ie. les nœuds
et les arcs) en 10 minutes, 20 minutes à partir d’un

9
nœud donné. La zone accessible est aussi appelé iso- 5
9 x5 x8 11
chrone.
x2 x11
7
4 2
3 7 5
4
x1 2 3 x7 x12
11 3
x4 8 x10
4 3
4 5
9 5
4
x9
9
x3 x6 8
2

Figure 12 – Application isochrones

Activités Durées Contraintes

Figure 11 – Exemple d’isochrones à partir de Time
Square en transport en commun (par pas de 10 mi- A 4 après fin de H ; après fin de D
nutes) B 6 8j après fin de J
C 2 14j après fin de J
Pour calculer un isochrone, il est possible d’adapter D 12 4j après fin de G ; après fin de
l’algorithme de Dijkstra en remplaçant la condition F
« arrêt quand tous les sommets sont marqués »par E 4 après fin de C
« arrêt quand le cout du sommet marqué est supé- F 2 après fin de G ; 2j après fin de
rieur à la valeur de l’isochrone ». C
G 4 4j après fin de J
a Testez cette méthode sur le graphe de la fi- H 20 après fin de E ; 8j après fin de
gure 12 : à partir du sommet x4 , recherchez les F
sommets appartenant à l’isochrone de valeur 8. I 10 4j après fin de J ; après fin de
H ; 10j après fin de B
b Donnez la liste des sommets composant l’iso-
chrone avec le cout de chacun d’eux. J 2

c Peut-on remplacer la condition de l’algorithme Table 3 – Données du projet

de Dijkstra par « arrêt quand le cout du som-
met marqué est EGAL à la valeur de l’iso-
chrone » ? Justifiez votre réponse (en raison- par l, représente la contrainte : le début de l’activité
nant dans un cas général et pas uniquement j peut commencer au moins l jours après le début de
sur l’exemple). i (cela prend en compte la durée de l’activité i).

Remarque. On ne peut pas réaliser le projet s’il y

a des dépendances mutuelles entre les activités. On
4.4 Gestion de projet - PERT (*) ne trouve pas de telles dépendances dans l’exercice.
Pour réaliser un projet informatique, le travail à ef- Le graphe est donc sans circuit.
fectuer a été découpé en 10 activités notées A, B, C, Pour les questions ci-dessous, vous pouvez utiliser les
D, E, F, G, H, I et J. Pour chacune de ces activités, graphes de la page suivante.
les durées (en jours) et les contraintes de séquence-
ment sont fournies dans le tableau 3. Question 1. Décomposition en niveaux.
On représente le problème par le graphe de la fi-
gure 13. Les sommets représentent le début des a Calculez et représentez les niveaux sur ce graphe.
activités, et un arc entre les sommets i et j, pondéré

10
 2 E Question 4. Réduction. On souhaite réaliser le
C
4 projet en 52 jours. On a la possibilité de réduire la
10 H
20
A durée des activités D, H et I. Proposez la réduction
4
F 4
la plus simple. Précisez votre raisonnement.
2
4 12
16 D 20 F in
Deb G 8
0 6
10
6
J I

10 16
B

Figure 13 – Graphe associé au projet

Question 2. Durée minimale du projet et dates

de début au plus tôt des activités. Utilisez les
schémas fournis page suivante.

a Calculez la durée minimale de réalisation du

projet ainsi que les dates de début au plus tôt
des différentes activités. Quelle méthode utilisez-
vous ?
b Donnez le chemin qui conduit à cette durée mi-
nimale.

Question 3. Dates de début au plus tard des

activités. On se fixe comme durée du projet, la
valeur minimale trouvée à la question précédente.

a Calculez les dates de début au plus tard des

différentes activités. Quelle méthode utilisez-
vous ?
b Donnez les marges (Mg) des différentes activi-
tés.
c Donnez le chemin critique.

A B C D E F G H I J
Deb
plus
tôt
Deb
plus
tard
Mg

Table 4 – Résultats obtenus

11
 E
2
4
C

20
H A
4 10

F
4
2 12
4

16 D F in
20
8
Deb G

0 6 10

6
J I

10 16

E
2
4
C

20
H A
4 10

F
4
2 12
4

16 D F in
20
8
Deb G

0 6 10

6
J I

10 16

12
5 Graphes de Flot A
2/5
2/4
Définitions (*)
S1 0/1 D
Application du cours. Soit le graphe de flot de 6/6
4/4
la figure 14 dans lequel les arcs sont valués par la 4/4
quantité de flot circulant et par la capacité maximale. B 0/4 P

2/2
20/25 2/3 5/8
x2 x5
S2 0/2 E

25/40 5/5 5/5 0/10 25/25 3/5

3/3
20/25 10/20 10/20 C
x1 x3 x6 x8

15/15 5/10 5/5 0/10 25/25 Figure 15 – Réseau de circulation

20/20
x4 x7

Figure 14 – Exemple de graphe de flot Question 2. Calcul du flot maximal. Appli-

quez l’agorithme de Ford Fulkerson en utilisant les
schémas fournis et en donnant à chaque étape :

a Donnez le débit de flot circulant sur ce graphe. • Le graphe d’écart

b Le graphe de flot est-il admissible ? • L’arborescence du parcours (parcours en lar-

geur en sélectionnant les sommets dans l’ordre
c Soit la coupe K1 = ({x1 }, {x2 , x3 , x4 , x5 , x6 , x7 , x8 }), alphabétique)
donnez sa capacité.
• Le chemin augmentant
d Soit la coupe K2 = ({x1 , x3 , x4 }, {x2 , x5 , x6 , x7 , x8 }),
donnez sa capacité. • La variation de flot

e Proposez une borne supérieure pour le débit

maximal de flot.
Résultats obtenus :
5.1 Circulation (*) • Valeur du débit maximal de flot =
Une centrale située en P reçoit de l’eau de 2 sources • Coupe minimale et capacité de cette coupe =
situées en S1 et S2 par un réseau représenté par le
schéma de la figure 15. Sur chaque arc on a noté la
Question 3. Arcs inverses. A partir de cet exemple,
quantité circulant et la capacité maximale possible.
quel intérêt avez-vous identifié pour l’utilisation des
arcs inverses dans le graphe d’écart.
Question 1. Modélisation et compréhension.

a Ajoutez un sommet source S à ce graphe (avec

des valeurs de flot et de capacité admissible)
afin d’obtenir un graphe de flot.
b La centrale peut-elle recevoir la quantité maxi-
male que les deux sources peuvent fournir ?
c Quelle est la quantité de flot (débit) circulant
actuellement dans ce graphe de flot ?
d Quelle est la capacité de la coupe X = {S, S1, S2, }
et X 0 = {A, B, C, D, E, P } ?

13
 Ces schémas servent pour les questions 1 et 2 de l’exercice.

Itération 1
Graphe de flot (initial) Graphe d’écart Parcours

A A
2/5
2/4

S1 0/1 D S1 D
6/6
../.. 4/4
4/4
S B 0/4 P S B P

../.. 2/2
2/3 5/8
S2 0/2 E S2 E

3/5
3/3
C C

Flot = Chemin d’incrémentation = Valeur d’incrémentation =

14
Itération ...
Graphe de flot Graphe d’écart Parcours

A A
../5
../4

S1 ../1 D S1 D
../6
../.. ../4
../4
S B ../4 P S B P

../.. ../2
../3 ../8
S2 ../2 E S2 E

../5
../3
C C

Flot = Chemin d’incrémentation = Valeur d’incrémentation =

 Itération ...
Graphe de flot Graphe d’écart Parcours

A A
../5
../4

S1 ../1 D S1 D
../6
../.. ../4
../4
S B ../4 P S B P

../.. ../2
../3 ../8
S2 ../2 E S2 E

../5
../3
C C

Flot = Chemin d’incrémentation = Valeur d’incrémentation =

15
Itération ...
Graphe de flot Graphe d’écart Parcours

A A
../5
../4

S1 ../1 D S1 D
../6
../.. ../4
../4
S B ../4 P S B P

../.. ../2
../3 ../8
S2 ../2 E S2 E

../5
../3
C C

Flot = Chemin d’incrémentation = Valeur d’incrémentation =

5.2 Transport (*) a Explicitez ce plan de transport sur le graphe
de flot (schémas page suivante).
Trois dépôts A, B et C disposent respectivement de
30, 20 et 35 tonnes de marchandises. Ces dépôts des- b Quelle est la valeur du débit de flot ainsi ob-
servent quatre zones de consommation D, E, F et G tenu ?
demandant respectivement 10, 25, 20 et 25 tonnes. c Ce débit permet-il de satisfaire les demandes ?
Les caractéristiques et les capacités du réseau de trans- Justifiez votre réponse.
port des points de dépôt aux points de consommation
sont résumées dans le tableau ci-dessous. Question 4. Compréhension.
D E F G a Votre schéma contient-il des arcs de capacité
A 5 5 - 20 nulle ?
B - 20 10 5
b Votre schéma contient-il des arcs de flot nul ?
C 10 10 10 10
c Quelle différence y-a-t-il entre un arc de capa-
cité nulle et un arc de flot nul ?
Question 1. Graphe de flot. Donnez le graphe
de flots modélisant ce problème de transport : identi- Question 5. Amélioration du plan de trans-
fiez les sommets source et puit et notez les capacités port. Nous allons chercher à améliorer la valeur
des arcs. du débit. Pour cela, vous allez appliquer l’algorithme
de Ford Fulkerson avec comme flot initial le plan de
D transport proposé (utilisez les schémas fournis).
Donnez le nouveau plan de transport obtenu :
A

E • depuis A :
B • depuis B :
F
• depuis C :
C

Figure 20 – Graphe de flot du problème de trans-

port

Question 2. Borne supérieure du flot. Compte

tenu des offres disponibles aux dépôts et des de-
mandes aux zones de consommation, donnez une borne
supérieure du flot maximal.

Question 3. Plan de transport. Une société de

transport propose le plan d’acheminement suivant :

• Depuis A : acheminer 5 tonnes vers D, 5 tonnes

vers E et 20 tonnes vers G

• Depuis B : acheminer 20 tonnes vers E

• Depuis C : acheminer 5 tonnes vers D, 10 tonnes

vers F et 5 tonnes vers G

16
 Itération 1
Figure 21 – Graphe de flot (initial)

S B P

Figure 22 – Graphe d’écart

S B P

Figure 23 – Parcours

Flot : Chemin d’incrémentation : Valeur d’incrémentation :

17
 Itération ...
Figure 24 – Graphe de flot

S B P

Figure 25 – Graphe d’écart

S B P

Figure 26 – Parcours

Flot : Chemin d’incrémentation : Valeur d’incrémentation :

18
5.3 Affectation (*) Question 5. Pour savoir s’il est possible d’amé-
liorer l’affectation obtenue à la question 4, appliquez
Un magasin souhaite affecter des vendeurs à ses n
l’algorithme de Ford Fulkerson. Quelle est la nouvelle
rayons en respectant les contraintes suivantes :
solution ?
• chaque vendeur est affecté à un rayon et un
seul ; 5.4 Points de contrôle (*)
• dans chaque rayon, il y a exactement deux ven- Le graphe de flot de la figure 27 représente la cir-
deurs ; culation de produits entre une source s et une des-
• chaque vendeur a des compétences spécifiques tination p. Ces produits doivent être contrôlés lors
exprimant le fait qu’il peut travailler dans un de leur acheminement. On supposera que le coût de
rayon donné ; mise en place d’une inspection est proportionnelle à
la capacité de l’arc sur lequel elle a lieu.
• chaque vendeur est compétent dans le rayon où
il est affecté. 3/4
A C
On suppose que le nombre de vendeurs (m) est su-
périeur ou égal à 2n. 3/3 0/2 4/4

s p
Question 1. Proposez une modélisation de ce pro-
blème en termes de recherche de flot maximal (expli- 4/8 1/6 3/9
citez les sommets, les arcs, les capacités du graphe
de flot). B
3/3
D

Question 2. Que représente la valeur du flot maxi- Figure 27 – Exemple de graphe de flot
mal par rapport au problème que vous devez ré-
soudre ?

Question 3. Appliquez votre modélisation sur un Question 1. En vous appuyant sur un calcul de
exemple dans lequel il y a 3 rayons notés r1, r2, r3, flot maximal, déterminez où positionner les points
et 6 vendeurs notés de v1 à v6. Les compétences des de contrôle à coût minimal.
vendeurs sur les rayons sont les suivantes :
Question 2. Proposez une application de ce pro-
v1 v2 v3 v4 v5 v6 blème.
r1 1 1 1 1
r2 1 1 1
r3 1 1 1

Question 4. Déterminez une affectation initiale des

vendeurs aux rayons en utilisant l’heuristique triviale
suivante : (a) prendre les vendeurs dans l’ordre de
leur numéro et (b) placer chaque vendeur sur le pre-
mier rayon pour lequel il est compétent, si cela est
possible, sinon le vendeur n’est pas affecté.

a Donnez le graphe de flot correspondant

b Donnez la valeur de flot maximal obtenu
c Tous les vendeurs sont-ils affectés à un rayon ?

19
 Itération 1
Graphe de flot (initial) Graphe d’écart Parcours
3/4 A C
A C

3/3 0/2 4/4

s p
s p

4/8 1/6 3/9

B D
B D
3/3

Flot = Chemin d’incrémentation = Valeur d’incrémentation =

Itération ...

20
Graphe de flot Graphe d’écart Parcours
../4 A C
A C

../3 ../2 ../4

s p
s p

../8 ../6 ../9

B D
B D
../3

Flot = Chemin d’incrémentation = Valeur d’incrémentation =