C.U.F.R. J-F.
Champollion Groupe ISM
Albi Dakar
L2 Semestre 4 2014-2015
Théorie et Algorithmique des Graphes
TD 7 Plus courts chemins dans un graphe valué
(2 séances de TD)
Exercice 1
Soit G le graphe orienté et valué ci-dessous. En justifiant précisément le choix de l'algorithme
utilisé, déterminer les longueurs des plus courts chemins issus de quelques sommets.
Exercice 2
Soit G le graphe orienté et valué ci-dessous. En justifiant précisément le choix de l'algorithme
utilisé, déterminer les longueurs des plus courts chemins issus du sommet 10.
3 1
9
5 2 6
-3
-8
8
4
1 -2
1 -1 6
-4 -6
2
5
8 4
10
1
33 -5
3
-5
7 -6
3 1
-3 1
1 2
-3
5 2 1 1
0 4
0
Exercice 3 Le problème du postier chinois.
Soit un graphe G = (X,E) non orienté, connexe et valué par une fonction de poids p à valeurs
positives. On note Ptot le poids total de G. On appelle tournée de G un circuit passant par chacune
des arêtes de G (mais une arêtes peut être parcourue plusieurs fois, donc une tournée n'est pas un
circuit eulérien). On cherche à déterminer le poids minimal Pmin d’une tournée de G.
Si le graphe représente les rues qu'un facteur doit parcourir pour distribuer le courrier et que la
fonction de poids est le nombre de kilomètres de chaque rue, on cherche donc à distribuer tout le
courrier en parcourant le moins de kilomètres possibles.
Dans toute la suite, on suppose que G admet exactement deux sommets a et b de degré
impair. On rappelle qu'il existe alors un chemin eulérien joignant a à b dans G.
1. Montrer qu’il existe bien une tournée de poids minimal.
2. Montrer que le poids d’une tournée de G ne dépend pas du sommet d’origine.
3. On note Pab le poids du plus court chemin de a vers b. Montrer qu'alors
Pmin = Ptot + Pab
4. Déterminer une tournée de poids minimal du graphe ci-dessous.
Exercice 4
On cherche à minimiser la durée de réalisation d’un chantier. Le graphe orienté et valué
ci-dessous représente les différentes étapes menant à la réalisation du projet.
Au cours de sa réalisation, le projet évolue suivant différents états qui sont représentés par les
sommets du graphe. Le projet débute à l’état A et s’achève lorsqu’on parvient à l’état L.
Un arc (S, T) indique que l’état S de réalisation du projet est antérieur à l’état T et le poids de l’arête
(S, T) représente la durée, exprimée en heures, nécessaire à la réalisation de la tâche qui va conduire
de l’état S à l’état T. Cette tâche ne peut être accomplie que si toutes les tâches conduisant à l’état S
sont elles-mêmes déjà accomplies.
Pour fixer les idées, on supposera que la réalisation du projet commence à minuit (0h).
1. Montrer que la durée minimale pour réaliser le projet est le poids d’un chemin de poids
maximal d’origine A et d’extrémité L.
2. Adapter l’algorithme de Bellman pour déterminer un plus long chemin (dit chemin critique).
3. Représenter en couleur ce chemin. Au plus tôt, à quelle heure le projet peut-il être réalisé ?
4. Vu les contraintes, certaines tâches ne peuvent commencer avant une certaine heure, par
exemple, la tâche (B,E) ne peut commencer avant 3h (l’heure au plus tôt). D’autre part,
certaines tâches disposent d’une marge de temps pour être réalisée tout en permettant au projet
d’être achevé dans le temps optimal. En revanche, d’autres tâches sont critiques en ce sens que
tout retard dans leur accomplissement entraîne un retard global dans l’achèvement du projet.
Par exemple, la tâche (A,E) est critique, si elle ne commence pas à 0h, le projet en sera retardé
mais la tâche (A,B) n’est pas critique, on dispose d’une marge de manœuvre de 2 heures pour
la réaliser ie elle peut commencer entre 0h et 2h (cette dernière est l’heure au plus tard). Pour
chaque tâche, préciser à quelle heure au plus tôt et à quelle heure au plus tard elle peut être
commencée pour que le projet soit réalisé dans la durée optimale.
