Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
154
ce qui signi fie que l’on va gagner 5 uni tés moné taires pour chaque unité tran spor tée
sur la rela tion (I, 3).
Sur com bien d’uni tés ce gain peut
il por ter ? On le voit, à la rela tion (I, 2) : on ne peut
sous traire que 9 uni tés tran spor tées (au lieu de 28 sur (II, 3)) ; le gain maximal résul tant
de cet échange por tera donc sur 9 uni tés et se mon tera à 9 3 5 5 45 uni tés moné taires.
Remar quons d’ailleurs que seul un échange libé rant l’une des rela tions aupa ra vant sélec -
tion nés conduit de nou veau à une solu tion de base (dans le cas présent, avec 15 zéros).
Mais à quelle modi fi ca tion le trans fert uni taire envi sagé ci dessus correspond il sur le graphe de la figure 4.42 ? Sim ple
ment à l'ajout d’un arc (I, 3), ce qui engendre un cycle et un seul
dans l’arbre repré sen ta tif de la solu tion, comme nous l’avons
sou li gné en 4.7.1. Ce cycle (I, 3), (3, II), (II, 2), (2, I) a deux
arêtes par cou rues dans le sens des flèches, deux autres par cou
rues en sens inverse (fig. 4.43). Du point de vue des quan ti tés,
la loi de Kirchhoff est respectée : il y a équi libre entre 11 et
21, en cha cun des quatre som mets I, 3, II et 2.
Monétairement, on ajoute les coûts d’une unité sur les arcs (I, 3) et (II, 2) et l’on
en retranche les coûts sur les arcs (I, 2) et (II, 3) : on retrouve exac te ment 25.
Mais la struc ture d’arbre va encore faci li ter les cal culs. En effet, un arbre consti tue
un graphe sur lequel on peut défi nir, fixant arbitrairement le poten tiel d’un sommet et
les dif fé rences de poten tiel entre les som mets adja cents, un ensemble unique de poten -
tiels (à une constante addi tive près). La prop riété est tri viale et résulte d’ailleurs du fait
que, dans un arbre, il existe une chaîne et une seule entre deux som mets quel conques.
Consi dé rons alors le réseau « élec trique » formé par
l’arbre de la figure 4.44 ; sur chaque arc, indi quons la
dif fé rence de poten tiel qui est égale au coût uni taire de
tran s port sur la rela tion cor res pon dante.
De plus, fixons arbitrairement à 0 le poten tiel du som
met II : U II 5 0. On peut ainsi, de proche en proche,
cal cu ler le poten tiel de tous les autres som mets, notés
U i pour les som mets du pre mier niveau et V j pour ceux
du second niveau ; pour tout arc (i, j) de l’arbre on aura :
V j 2 U i 5 c ij .
Mais alors, lorsque nous rajou tons la rela tion (I,3),
du coût 61, on peut écrire :
d I, 3 5 U I 1 c I, 3 2 V 3 5 12 1 61 2 78 5 25.
et plus pré ci sé ment :
d i, j 5 U i 1 c ij 2 V j 5 c ij 2 1 V j 2 U i 2
for mule qui per met tra de cal cu ler rapi de ment le coût mar gi nal d i,j de toute relation (i, j)
inutilisée c-à-d telle que x ij 5 0, sans avoir à rechercher le cycle de subs ti tution (ce qui
peut être long). Ainsi, pour la rela tion (I, 6) :
d I, 6 5 U I 1 c I, 6 2 V 6 5 12 1 35 2 66 5 219,
Figure 4.43
Figure 4.44
V j
U i i
j
154
ce qui signi fie que l’on va gagner 5 uni tés moné taires pour chaque unité tran spor tée
sur la rela tion (I, 3).
Sur com bien d’uni tés ce gain peut
il por ter ? On le voit, à la rela tion (I, 2) : on ne peut
sous traire que 9 uni tés tran spor tées (au lieu de 28 sur (II, 3)) ; le gain maximal résul tant
de cet échange por tera donc sur 9 uni tés et se mon tera à 9 3 5 5 45 uni tés moné taires.
Remar quons d’ailleurs que seul un échange libé rant l’une des rela tions aupa ra vant sélec -
tion nés conduit de nou veau à une solu tion de base (dans le cas présent, avec 15 zéros).
Mais à quelle modi fi ca tion le trans fert uni taire envi sagé ci dessus correspond il sur le graphe de la figure 4.42 ? Sim ple
ment à l'ajout d’un arc (I, 3), ce qui engendre un cycle et un seul
dans l’arbre repré sen ta tif de la solu tion, comme nous l’avons
sou li gné en 4.7.1. Ce cycle (I, 3), (3, II), (II, 2), (2, I) a deux
arêtes par cou rues dans le sens des flèches, deux autres par cou
rues en sens inverse (fig. 4.43). Du point de vue des quan ti tés,
la loi de Kirchhoff est respectée : il y a équi libre entre 11 et
21, en cha cun des quatre som mets I, 3, II et 2.
Monétairement, on ajoute les coûts d’une unité sur les arcs (I, 3) et (II, 2) et l’on
en retranche les coûts sur les arcs (I, 2) et (II, 3) : on retrouve exac te ment 25.
Mais la struc ture d’arbre va encore faci li ter les cal culs. En effet, un arbre consti tue
un graphe sur lequel on peut défi nir, fixant arbitrairement le poten tiel d’un sommet et
les dif fé rences de poten tiel entre les som mets adja cents, un ensemble unique de poten -
tiels (à une constante addi tive près). La prop riété est tri viale et résulte d’ailleurs du fait
que, dans un arbre, il existe une chaîne et une seule entre deux som mets quel conques.
Consi dé rons alors le réseau « élec trique » formé par
l’arbre de la figure 4.44 ; sur chaque arc, indi quons la
dif fé rence de poten tiel qui est égale au coût uni taire de
tran s port sur la rela tion cor res pon dante.
De plus, fixons arbitrairement à 0 le poten tiel du som
met II : U II 5 0. On peut ainsi, de proche en proche,
cal cu ler le poten tiel de tous les autres som mets, notés
U i pour les som mets du pre mier niveau et V j pour ceux
du second niveau ; pour tout arc (i, j) de l’arbre on aura :
V j 2 U i 5 c ij .
Mais alors, lorsque nous rajou tons la rela tion (I,3),
du coût 61, on peut écrire :
d I, 3 5 U I 1 c I, 3 2 V 3 5 12 1 61 2 78 5 25.
et plus pré ci sé ment :
d i, j 5 U i 1 c ij 2 V j 5 c ij 2 1 V j 2 U i 2
for mule qui per met tra de cal cu ler rapi de ment le coût mar gi nal d i,j de toute relation (i, j)
inutilisée c-à-d telle que x ij 5 0, sans avoir à rechercher le cycle de subs ti tution (ce qui
peut être long). Ainsi, pour la rela tion (I, 6) :
d I, 6 5 U I 1 c I, 6 2 V 6 5 12 1 35 2 66 5 219,
Figure 4.43
Figure 4.44
V j
U i i
j