Exercices
183
© Dunod – Toute reproduction non autorisée est un délit.
*4.12 Tracé d'un réseau de transport et flot maximal
I) Un graphe de n 5 5 sommets et m 5 8 arcs est décrit par la liste des successeurs:
1
2
2
3
4
5
1
0
3
2
i
d +
i
où d
1
i le demi-degré extérieur du sommet i, est le nombre d’arcs partant du sommet i.
1
2
5
3
4
5
6
7
8
4
5
2
1
5
1
2
j
ext(j)
Le tableau ext(j) liste, dans l’ordre lexicographique, les extrémités terminales des arcs
issus du sommet 1 puis celles du sommet 2, etc. Ainsi le sommet 1 a deux successeurs :
ce sont les 2 premiers éléments du tableau ext(j), donc les sommets 2 et 5.
1. Tracer ce graphe. Montrer, en détail, qu’il s’agit d’un réseau de transport
(la capacité de chaque arc étant donnée à la question suivante).
2. On associe à chaque arc u j une capacité et un flux :
1
3
4
5
6
7
8
2
1
2
5
5
3
4
12
3
1
2
2
2
3
4
9
3
flux(j)
capa(j)
j
Vérifier que les flux proposés forment bien un flot sur ce réseau de transport.
Déterminer, obligatoirement à l’aide de l’algorithme approprié, si ce flot est
maximal. Sinon, l’optimiser. Donner la valeur du flot maximal ; indiquer
une coupe minimale, et rappeler sa signification concrète.
*4.13 Pro blème d’affec ta tion
On a tiré au hasard les élé ments de la matrice ci- dessous à six lignes et six colonnes.
Affec ter un élé ment et un seul par ligne et par colonne, de manière à obte nir la
somme mini male “coût” minimal des affectations.
a
b
c
d
e
f
A
B
C
D
E
F
10 90 27 14 39 52
29 24 79 90 23 13
17 43 62 02 73 70
58 14 06 18 16 63
15 41 78 44 73 70
25 44 81 36 80 80