Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
180
**4.7 Méthode matricielle
La matrice 1 ci- dessous donne les valuations d’un graphe.
Appli quer la méthode matricielle, c’est- à-dire l’adap ta tion de l’algo rithme de
Roy- Warshall, pour déter mi ner les « plus courts » che mins (c’est- à-dire les che mins
de valeur mini male) entre tous les couples de som mets du graphe ; il est conseillé de
l’implé
men ter, ce qui est aisé. Vous pour rez véri fier les résul
tats en tra
çant le graphe
(qui est sans cir cuit).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
4
4
4
4
4
4
2
2
2
1
1
3
3
3
3
3
9
7
7
9
9
9
6
6
5
5
5
5
10
iii orDon nan cE MEnTs
*4.8 Graphes PErT et MPM, che min cri tique et marges
La mise en exploi ta tion d’un nou veau gise ment minier néces site la réa li sa tion des
opé ra tions ci- dessous :
Durée
a) Obten tion d’un per mis d’exploi ta tion ..................................... 8 mois*
b) Construc tion d’une piste entre route et site ............................. 3 mois
180
**4.7 Méthode matricielle
La matrice 1 ci- dessous donne les valuations d’un graphe.
Appli quer la méthode matricielle, c’est- à-dire l’adap ta tion de l’algo rithme de
Roy- Warshall, pour déter mi ner les « plus courts » che mins (c’est- à-dire les che mins
de valeur mini male) entre tous les couples de som mets du graphe ; il est conseillé de
l’implé
men ter, ce qui est aisé. Vous pour rez véri fier les résul
tats en tra
çant le graphe
(qui est sans cir cuit).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
4
4
4
4
4
4
2
2
2
1
1
3
3
3
3
3
9
7
7
9
9
9
6
6
5
5
5
5
10
iii orDon nan cE MEnTs
*4.8 Graphes PErT et MPM, che min cri tique et marges
La mise en exploi ta tion d’un nou veau gise ment minier néces site la réa li sa tion des
opé ra tions ci- dessous :
Durée
a) Obten tion d’un per mis d’exploi ta tion ..................................... 8 mois*
b) Construc tion d’une piste entre route et site ............................. 3 mois