CHAPITRE 8 GRAPHES ET OPTIMISATION 61

Chapitre 8: Graphes et optimisation

8.1 Un exemple en guise d’introduction

Introduction : C'est l'histoire du livreur de pizza, contraint de livrer ses commandes en moins d'une
demi-heure avec pour seule arme un scooter faiblard et poussif. C'est aussi l'histoire
de monsieur Dupont qui, sa valise à la main, se rend à la gare de Lausanne, direc-
tion St-Moritz, sans bien savoir par où passer. C'est encore l'histoire d'Internet qui
permet le transfert de tous types de données dans le monde entier via... quelle route
au fait ?
Dans les trois cas, la question que se posent les protagonistes avant de foncer tête
baissée est la même : quel est le plus court chemin pour aller de mon point de départ
à mon point d'arrivée sachant que je ne peux emprunter que des lignes ferroviaires,
des routes, des réseaux ?
Qui dit trajet dit problème des plus courts chemins. Qui dit problème dit nécessité de
trouver une solution !
Le problème est donc posé : étant donné un ensemble de points (les gares, les ser-
veurs) et un ensemble de liaisons entre ces points (les lignes ferroviaires, les routes)
caractérisées par un certain poids (longueur en kilomètres ou, pourquoi pas, coût,
nombre de tournants, débit, ...), comment trouver le chemin le plus court, le moins
cher, le plus agréable entre deux points ?
Il est difficile de parler d'algorithme naïf lorsqu'on s'attaque au problème des plus
courts chemins, car quoi qu'il arrive, il faudra trouver un moyen de comparer diffé-
rents chemins entre eux, de ne pas en oublier, bref de définir une façon de parcourir
Edsger W. Dijkstra le graphe, ce qui, même à la main, est loin d'être instinctif. Nous en étudierons
(1930 – 2002) deux : l’algorithme de Dijkstra datant de 1959 et l’algorithme MPM.

Problème : Une entreprise de transport ROUTEXPRESS dont le siège est situé à

BERNE, doit effectuer de fréquentes livraisons à MILAN, en dehors
de la période hivernale.
Ses véhicules doivent donc traverser le massif des Alpes ; leur gabarit
interdit l’usage des tunnels ferroviaires (Simplon, Saint-Gothard, Löt-
schberg, …) qui, sinon, faciliteraient le voyage.
Vu la fréquence et le coût de ces livraisons, l’entreprise désire déter-
miner l’itinéraire le plus court de BERNE à MILAN.

Démarche : D’une carte routière, on a extrait le plan suivant, indiquant les diffé-
rents tracés possibles ainsi que les distances entre les villes (en km) :


WASSEAU 85
LUCERNE
56 15
57 ANDERMATT CADENAZZO
45 45 31
INNETT- 73 86 MILAN
90 KIRCHEN GLETSCH

STRESA 66

78 164
BERNE

Option spécifique – JtJ 2016

CHAPITRE 8 GRAPHES ET OPTIMISATION 62

Définitions • On appelle graphe pondéré, un graphe dont les arêtes ont été affec-
tées d’un nombre appelé poids.
Dans les exemples étudiés ici, les poids affectés à chaque arête seront toujours positifs.
Cette condition est assez banale lorsque les poids représentent par exemple des coûts, des
distances, ou des temps. Elle n’est pas toujours réalisée lorsque par exemple les poids repré-
sentent des flux.

• Poids d’un chemin : C’est la somme des poids des arêtes qui consti-
tuent le chemin. On parlera aussi, selon le contexte, de longueur du
chemin.

• Plus court chemin d’un sommet à un autre : C’est, de tous les

chemins qui relient deux sommets, celui de longueur minimale.

Remarques: • A priori, ce chemin n’est pas unique.

• On définirait de même le chemin le plus long (pour des graphes sans cycle).

Démarche générale : Notre problème s’énonce maintenant ainsi : dans le graphe de la figure suivante,
déterminer le plus court chemin reliant le sommet B à M.


L 56 W 15 A C
85
86
90 M
45 57 31 73
66
B
78
I 45 G 164 S
Le nombre de chemins reliant ces deux villes est limité, du moins si l’on élimine les
chemins contenant des cycles, qui ne peuvent être minimaux. On peut en dresser la
liste, calculer leur poids respectif, et déterminer la solution du problème :

Intuitivement, on ne procédera pas ainsi, mais "par étapes successives". Par

exemple, on constatera que le passage par Innettkirchen pour Wasseau, qu’il soit ou
non retenu finalement, est plus court que celui par Lucerne. Le chemin Berne–
Lucerne–Wasseau peut ainsi être éliminé rapidement.
La règle très simple appliquée ici est à la base de l’algorithme de recherche du plus
court chemin et peut être écrite ainsi :
Un plus court chemin [x0 ; xn] entre deux sommets x0 et xn d’un graphe est consti-
tué des plus courts chemins reliant deux sommets du chemin [x0 ; xn]. (En d’autres
termes : les sous-chemins des plus courts chemins sont des plus courts chemins.
Cette règle, appelée parfois « principe d’optimalité », se démontre sans difficulté
par l’absurde).

La recherche du plus court chemin entre deux sommets x0 et xn d’un graphe passe
alors par les recherches successives des plus courts chemins reliant x0 à tous les
sommets du graphe susceptibles de se trouver sur le trajet. Reste à choisir dans quel
ordre on liste les sommets intermédiaires.

Option spécifique – JtJ 2016

CHAPITRE 8 GRAPHES ET OPTIMISATION 63

1ère étape:
L (90 , B)
On part de Berne. On peut atteindre les deux villes L et I. On leur as-
90
socie, entre parenthèses, la distance depuis Berne et l’initiale du som-
45
met prédécesseur, ici B.
B
78
I (78 , B)
La distance la plus courte inscrite à cette étape est 78 km (si l’on ex-
cepte, bien entendu, 0 km pour Berne). Aucune autre ville n’étant ac-
L (90 , B)
cessible depuis Berne pour une distance plus courte, on peut assurer
90 qu’aucun autre trajet, passant par une autre ville, ne relie Berne à
45 Innettkirchen pour une distance plus courte : 78 km est la distance
minimum d’un trajet Berne-Innettkirchen. Cette distance est notée
B
78 L(I). Innettkirchen sera dite marquée (définitivement).
I (78 , B)

2ème étape:

Notre voyageur va alors considérer les villes accessibles depuis In-

nettkirchen. Pour chacune, trois cas peuvent se présenter :
• Cette ville X n’était pas provisoirement marquée : on la marquera provisoirement
de la distance (L(I) + poids de l’arête δ(I ; X)).
• Cette ville X était déjà provisoirement marquée, mais la distance (L(I) + poids de
l’arête δ(I ; X)) est inférieure à la distance du marquage provisoire : on la rem-
place.
• Cette ville X était déjà provisoirement marquée, et la distance (L(I) + poids de
l’arête δ(I ; X)) est supérieure à la distance du marquage provisoire : on garde la
distance provisoire.

Dans notre exemple :

L (90 , B) 56 W (135 , I)

90 La distance pour L reste inchangée (90 < 78 + 45),

45 57 W est marqué provisoirement d’une distance 135 (78 + 57),
B
78 G est marqué provisoirement d’une distance 123 (78 + 45).
45 G (123 , I)
I (78 , B)

L (90 , B) 56 W (135 , I)
À ce stade, parmi les villes provisoirement marquées, L admet la plus
90
45 57
petite distance. On marquera alors définitivement L(L) = 90.
B
78
45 G (123 , I)
I (78 , B)

3ème étape:

L (90 , B) 56 W (135 , I)
À présent, on marque la ville adjacente à L en constatant que l’on ne
90
modifie pas le marquage provisoire car 135 < 90 + 56. G admettant la
45 57 plus petite distance, on la marque définitivement.
B
78
45
I (78 , B) G (123 , I)

Option spécifique – JtJ 2016

CHAPITRE 8 GRAPHES ET OPTIMISATION 64

On réitère ainsi ce processus jusqu’à atteindre la ville de Milan. Nous

obtiendrons alors le graphe suivant :

L (90 , B) W (135 , I) A (150 , W) C (235 , A)

86
90 56 15 85 M (321 , C)
45 57 31 73
66
B
78
164
I (78 , B) 45 G (123 , I) S (287 , G)

On reconstitue le chemin voulu en partant de Milan et en remontant

étape par étape le chemin à l’envers à l’aide des sommets prédéces-
seurs: M-C-A-W-I-B.

Solution : Il s’agit donc du trajet de 321 km :

Berne – Innetkirchen – Wasseau – Andermatt – Cadenazzo – Milan.

Exercice 103 Reprendre la démarche complète de l’exemple Berne – Milan.

8.2 L’algorithme de DIJKSTRA

Formulons la méthode utilisée par l’algorithme suivant :

Algorithme du plus court chemin (Dijkstra)

Donnée : Un graphe simple, non orienté, pondéré, à n sommets

Résultat : Le plus court des chemins d’un sommet de départ à tous les
autres sommets.

1: *** Initialisation ***

2: S = Ø ; L(x1) = 0 et L(xi) = ∞ pour i ≠ 1
3: *** Itération ***
4: Répète
5: choisis un sommet xi ∈ V-S avec L(xi) minimal ;
6: si L(xi) = ∞, alors halte ;
7: ajoute le sommet xi à l’ensemble S ;
8: si S = V, alors halte ;
9: pour chaque voisin xj ∈ V-S du sommet xi,
10 : si L(xj) > L(xi) + ∂(xi , xj)
11 : remplace L(xj) par L(xi) + ∂(xi , xj)
12 : et remplace p(xj) par xi ;

On représentera les étapes de l’algorithme en complétant le graphe et à

l’aide d’un tableau mentionnant toutes les étapes :

Option spécifique – JtJ 2016

CHAPITRE 8 GRAPHES ET OPTIMISATION 65

Résolution type L 56 W 15 A
85
C
(à compléter ensemble) 86
90 M
45 57 31 73
66
B
78
I 45 G 164 S

B L I W G A S C M
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ B

Dans le cas des L’algorithme de DIJKSTRA peut facilement être adapté à un graphe
graphes orientés ? orienté, en indiquant un poids de ∞ si l’arc n’est pas orienté dans le
“bon sens”.

A 3 B Poids de [A ; B] = 3
Poids de [B ; A] =

Exercice 104 Appliquer l’algorithme de Dijkstra pour déterminer le plus court che-
min entre E et S et proposer la résolution à l’aide du tableau.
A 2 C
3 3
3 1
1
E S
1 1
B 5 D

Exercice 105 Trouver le plus court chemin du sommet A vers tous les sommets en
utilisant l’algorithme de Dijkstra.
D
9 3
B G
4
7 5 2 9
E
3 8
A I
6 8 6 3
8
C 9
H
7

F
Dans chaque cas, proposer un chemin minimum et indiquer le nombre
de chemins minimums possible.
Option spécifique – JtJ 2016
CHAPITRE 8 GRAPHES ET OPTIMISATION 66

Exercice 106 Les deux cartes suivantes représentent ; à gauche : le trajet en miles du
train Expressways in the Chicago area et à droite la durée des diffé-
rentes étapes.

Buffalo Buffalo
Grove 6 mi 5 mi Grove 8 min 10 min

6 mi 13 mi 10 min 24 min 18 min

8 mi
10 mi 20 min
7 mi 15 min

15 mi 8 mi 13 min 22 min
9 mi 15 min

15 mi 30 min
9 mi 2 mi 15 min 10 min
13 mi 18 min

9 mi 9 min
17 mi 10 mi 20 min 15 min
10 mi 22 min

5 mi South 12 min South

Holland Holland

a) Utiliser l’algorithme de Dijkstra pour déterminer le plus court tra-

jet de Buffalo Grove à South Holland.

b) Utiliser l’algorithme de Dijkstra pour déterminer le trajet le plus

rapide pour relier les deux mêmes villes.

Exercice 107 La matrice qui suit donne en heures les durées des vols entre certaines
villes v1, v2, …, v6 :

⎛ 0 3 ∞ 5 ∞ ∞⎞
⎜ 3 0 5 2 4 ∞⎟
⎜∞ 4 0 ∞ 4 3 ⎟
⎜ ⎟
⎜6 2 ∞ 0 4 4⎟
⎜⎜∞ 4 4 5 0 2 ⎟⎟
⎝∞ ∞ 5 4 3 0 ⎠

Le terme (i,j) de cette matrice est égal à ∞ lorsque le vol au départ de

la ville vi à destination de vj n’existe pas.
a) En ne tenant pas compte de la durée des escales, quel est
l’itinéraire le plus rapide de v1 à v6.

b) S’il y a une escale obligatoire de respectivement 2, 3, 1, 1, 4, 5

heures aux villes v1, …, v6, quel est alors l’itinéraire le plus rapide
de v1 à v6 ?

Option spécifique – JtJ 2016

CHAPITRE 8 GRAPHES ET OPTIMISATION 67

Exercice 108 Dans le graphe ci-dessous contenant un poids négatif, montrer que
l’algorithme de Dijkstra ne peut pas être appliqué.

B
2 1
C
A
4 -2

Exercice 109 Partant de Moscou, Michel Strogoff, courrier du tsar, devait rejoindre
Irkousk. Avant de partir, il avait reporté sur une carte pour chaque
liaison entre deux villes les « chances » de réussite. Ces chances
étaient exprimées par un entier de 1 à 10 (mesurant le nombre de
chances sur 10 de réussite). Ignorant le calcul de probabilités, il avait
choisi son itinéraire en maximisant la somme globale des chances.

A 7 C 3 F 1 G 2 J
9 6
7 5 9 4 5
Moscou Irkousk
8 1

B 8 D 6 E 1 H 9 K

a) Déterminer le trajet de Michel Strogoff.

b) Quel aurait été son trajet s’il avait connu le calcul des probabili-
tés ?

Exercice 110 Déterminer le plus court chemin de C à I

A
4
10 4 10 D
C
B 10 12
5 16
F
E 21
4 3
17 3
10 G
H
3
5

I 8 J

Exercice 111 L’un d’entre vous se sent-il prêt à démontrer que l’algorithme de Dijk-
stra fournit bien le plus court chemin d’un sommet initial à un sommet
final ?

Option spécifique – JtJ 2016

CHAPITRE 8 GRAPHES ET OPTIMISATION 68

8.3 Problèmes d’ordonnancement

De quoi s’agit-il ? Il s’agit de savoir planifier l’exécution de tâches qui ont une certaine
durée, et qui ont entre elles des relations d’antériorité (par exemple,
dans les révisions qu’il faut faire avant de passer le baccalauréat, il y a
des chapitres qu’il faut revoir avant d’autres).

Exemple : L’entreprise Oméga a procédé à la définition d’un certain nombre de

tâches à effectuer. On a rempli la colonne « antériorité » avec les
tâches qui doivent être exécutées avant celle considérée. Une évalua-
tion du temps de chaque tâche a également été proposée.

Tâche Durée en semaines Antériorité

A 3
B 4 A
C 5 A
D 2 A
E 2 B, C
F 3 D

Proposer un agenda des différentes tâches, en indiquant le nombre de

semaines minimum puis maximum à entrevoir avant la fin des diffé-
rentes tâches.

Il existe plusieurs algorithmes possibles pour résoudre les problèmes

d’ordonnancement. Les deux plus fréquemment utilisées sont la mé-
thode PERT (méthode américaine) et la méthode MPM (méthode
française datant de 1960). Concentrons-nous sur cette dernière.

Méthode française MPM 1) À partir du tableau, on réalise un premier graphe appelé graphe de
(Méthode Potentiel Métra)
niveau dont les sommets sont les tâches et qui permet de mettre en
évidence les antériorités :

niveau 1 niveau 2 niveau 3

B
E
A C
F
D

Option spécifique – JtJ 2016

CHAPITRE 8 GRAPHES ET OPTIMISATION 69

2) On crée un graphe orienté dont les sommets sont les tâches ; on

crée deux tâches fictives qui sont les tâches « début » et « fin »
(sous-entendu « du processus »).
.

Les arcs sont les relations d’antériorité immédiate ; ils sont valués
par la durée de la tâche source.
B
4
3 E
2
début A 3 C fin
5

F
3
3 2
D

Chaque sommet comporte 3 zones qui contiennent respective-

ment :

Nom de la tâche

Début au Début au
plus tôt plus tard

3) Dates « au plus tôt »

On traite les sommets par niveaux en partant du début.
Pour chaque sommet i on note la date ti qui est la longueur du plus
long chemin de la tâche initiale à la tâche i.

B
3 4
3 E
8 2
début A 3 C fin
5
0 0 3 10
F
3
3 2 5
D
3

Le travail ne pourra donc pas être terminé avant 10 semaines.

La tâche E ne pourra pas commencer avant 8 semaines, la tâche F
avant 5 semaines, etc.

Option spécifique – JtJ 2016

CHAPITRE 8 GRAPHES ET OPTIMISATION 70

4) Dates « au plus tard »

On traite les sommets en partant de la fin (en marquant 10 pour le
sommet « fin »).
Pour chaque sommet on note la date t i* qui est la longueur du plus
court chemin de la tâche i à la tâche « fin ».

B
3 4 4
3 E
8 8 2
début A 3 C fin
5
0 0 0 0 3 3 10 10
F
3
3 2 5 7
D
3 5

Pour effectuer l’ensemble des tâches en 10 semaines, il faudra

avoir commencé la tâche E au bout de 8 semaines, commencé la
tâche F au bout de 7 semaines, etc.

5) Exploitation de ce graphe
Il y a des tâches critiques, celles pour lesquelles on a t i = t i* : la
tâche E devra obligatoirement débuter durant la 8ème semaine (ni
plus ni moins) pour que le processus soit achevé au bout des 10
semaines. Les tâches critiques définissent un ou plusieurs chemins
critiques composés de tâches dont l’exécution ne doit connaître
aucun retard pour que le projet soit achevé au plus tôt.
Par contre, il y a de la latitude pour les tâches qui ne sont pas cri-
tiques : la tâche F pourra être démarrée entre la semaine 5 et la
semaine 7.
De même, il y a un chemin critique : A – C – E – fin (il y a tou-
jours un chemin critique dans un graphe MPM).

Définition : Marge totale : retard maximum que peut avoir une tâche sans retarder
la fin du projet (les tâches critiques n’ont pas de marge). On l’obtient
en calculant t i* − t i .

Dans notre exemple, on obtient le tableau suivant :

Tâche Marge totale

A 0
B 1
C 0
D 2
E 0
F 2

Option spécifique – JtJ 2016

CHAPITRE 8 GRAPHES ET OPTIMISATION 71

5) Diagramme de Gantt
Il s’agira de représenter graphiquement le déroulement du projet ;
les tâches à effectuer sur les plages à disposition durant les 10 se-
maines (numérotées de 0 à 9).
0 1 2 3 4 5 6 7 8 9 10

A
B
C
D
E
F

Exercice 112 Proposer le diagramme de Gantt de la planification suivante :

Tâche Durée en semaines Antériorité

A 3 B
B 8 -
C 2 A, B, F
D 6 -
E 5 B, D
F 4 B

Exercice 113 La mise en exploitation d’un nouveau gisement minier demande la

réalisation d’un certain nombre de tâches. Le tableau suivant repré-
sente ces différentes tâches avec leurs relations d’antériorité.

Durée Tâches
Tâche Description
(en jours) antérieures
A obtention d’un permis d’exploitation 120 -
B établissement d’une piste de 6 km 180 A
C transport et installation à pied d’œuvre de 2 sondeuses 3 B
création de bâtiments provisoires pour le bureau des
D 30 B
plans, le logement des ouvriers sondeurs
E goudronnage de la piste 60 B
F adduction d’eau 90 D
G campagne de sondage 240 C,D
H forage et équipement de trois puits 180 E,F,G
I transport et installation au fond du matériel d’exploitation 30 J,H
construction de bureaux et logements, ouvriers et ingé-
J 240 E,F,G
nieurs
K traçage et aménagement du fond 360 J,H
L construction d’une laverie 240 J,H

a) Déterminer les dates au plus tôt et les dates au plus tard de chaque
tâche.
b) Déterminer le temps minimum de réalisation de l’ensemble.
c) Proposer un chemin critique.
d) Préciser les marges totales de chaque tâche.

Option spécifique – JtJ 2016

CHAPITRE 8 GRAPHES ET OPTIMISATION 72

Exercice 114 Un producteur de cinéma est confronté au problème de planning de

son prochain film selon les tâches suivantes :

Tâche description durée (j) antériorités

A écriture du scénario 30 -
B choix et recrutement des comédiens 12 15 jours après le début de A
C choix du lieu de tournage 8 20 jours après le début de A
D découpage technique 4 A et C doivent être terminées
E préparation des décors 7 C et D doivent être terminées
A, B, C et D doivent être
F tournage des extérieurs 10
terminées
D, E et F doivent être termi-
G tournage des intérieurs 12
nées
H synchronisation 3 F et G doivent être terminées
I montage 14 H doit être terminée
ne peut commencer que 3
J accompagnement sonore 7 jours après le début de I et
après la fin de H
K mixage 6 I et J doivent être terminées
ne peut commencer que 2
L tirage de la copie zéro 1
jours après la fin de K

a) Déterminer les dates au plus tôt et les dates au plus tard de chaque
tâche.
b) Déterminer le temps minimum de réalisation de l’ensemble.
c) Proposer un chemin critique.
d) Préciser les marges totales de chaque tâche.

Option spécifique – JtJ 2016

CHAPITRE 8 GRAPHES ET OPTIMISATION 73

Conclusion et références
Nous voici au bout de notre voyage dans la théorie des graphes. Mais peut-être pas au bout du
vôtre… Cette théorie récente cache encore quelques résultats à découvrir, quelques algo-
rithmes à optimiser et quelques théorèmes à compléter. Que ce soit en informatique, en ma-
thématiques, en sciences économiques, …, les outils de la théorie des graphes sont encore en
pleine expansion.

Liens entre différentes pages html d’un site Internet

Quelques références et bibliographie :

Kenneth H. Rosen. (1998). Mathématiques discrètes, Chenelière/McGraw-Hill

Richard J. Trudeau. (1993). Introduction to graph theory, Dover

La revue Tangente pour les annexes 5 chapitre 5 & 1 et 2 chapitre 7

Eric Sigward. (2002). Introduction à la théorie des graphes

www.ac-nancy-metz.fr/enseign/maths/m2002/institut/ipr/graphes/Graphes.pdf

http://icosaweb.ac-reunion.fr/RsrcPeda/General/Lycee/TheorieDesGraphes/Graphespage01.htm

Didier Müller (2011). Introduction à la théorie des graphes

www.apprendre-en-ligne.net/graphes/graphes.pdf

Option spécifique – JtJ 2016

CHAPITRE 8 GRAPHES ET OPTIMISATION 74

Option spécifique – JtJ 2016