Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
146
contredit le fait qu’une arbo res cence soit, sans l’orien ta tion,
un arbre.
En recherche opé ra tion nelle on uti lise fré quem ment la
notion d’arbo res cence (d’ailleurs nous avons déjà dû nous en
ser vir plus haut). Nous en don nons plus loin (au para graphe
4.10), une autre appli ca tion : au fameux « pro blème du voya -
geur de com merce » (« Tra ve ling Salesman Problem », ou
« TSP »).
Notons un abus de lan gage : la plu part des « arbres » des
infor ma ticiens sont en fait des arborescences, au sens de la
théo rie des graphes.
4.8 Appli cA tions Aux Arbres opti mAux
En recherche opé ra tion nelle, on ren contre assez sou vent des pro blèmes fai sant appel
à la notion d’arbre de valeur mini male, par exemple en opti mi sation des réseaux.
Étant donné un graphe valué G 5 (X, V), de n som mets et connexe, on veut
construire, en uti li sant n 2 1 de ses arêtes, un arbre dont la somme des valeurs (ou
coûts) des arêtes sera mini male.
En 1956, J.B. Kruskal a donné un algo rithme simple pour résoudre ce pro blème.
Il consiste à :
a) éta blir une liste des arêtes par valeurs crois santes ;
b) choi sir une arête de valeur mini male puis, suc ces si ve ment, au fur et à mesure de la
construc tion de l’arbre, l’arête sui vante dans la liste ne for mant pas un cycle avec les
arêtes rete nues jusque- là. S’arrê ter lorsque tous les som mets du graphe sont connec -
tés (ou, ce qui revient au même, lorsque le nombre d’arêtes rete nues égale n 2 1).
Pour un exemple se repor ter à la Fig 4.37.
Il s’agit du pre mier exemple de « méthode gour mande » (ou « glou tonne » ; en
anglais : « greedy algorithm »), car à chaque pas on choi sit l’élé ment le plus inté res -
sant (comme si l’on pre nait le plus gros mor ceau dans le par tage d’un gâteau).
Un autre algo rithme a été pro posé en 1961, par G. Sollin, alors chef de tra vaux au
CNAM, pour opti mi ser des réseaux de cana li sa tion ; le voici :
Ini tia le ment aucun som met n’a été « retenu ».
a) Choi sir arbi trai re ment un som met x en dehors de ceux qui ont déjà été rete nus ;
relier, par l’arête de valeur la plus faible, ce som met x à l’un des som mets (déjà retenu
ou non) aux quels il est adja cent ; soit y ce der nier som met : y est alors « retenu », de
même que x.
b) Lorsque tous les som mets ont été rete nus :
– soit on a obtenu un arbre et le pro blème est résolu : cet arbre est de coût minimal.
– soit on a seule ment plu sieurs sous arbres. Contrac ter cha cun en un som met unique ;
créer le multi graphe
1
dont chaque som met est asso cié à l’un de ces sous arbres et dont
1. On appelle multi graphe un graphe dont deux som mets au moins sont reliés par plus d’un arête.
r
Figure 4.36
146
contredit le fait qu’une arbo res cence soit, sans l’orien ta tion,
un arbre.
En recherche opé ra tion nelle on uti lise fré quem ment la
notion d’arbo res cence (d’ailleurs nous avons déjà dû nous en
ser vir plus haut). Nous en don nons plus loin (au para graphe
4.10), une autre appli ca tion : au fameux « pro blème du voya -
geur de com merce » (« Tra ve ling Salesman Problem », ou
« TSP »).
Notons un abus de lan gage : la plu part des « arbres » des
infor ma ticiens sont en fait des arborescences, au sens de la
théo rie des graphes.
4.8 Appli cA tions Aux Arbres opti mAux
En recherche opé ra tion nelle, on ren contre assez sou vent des pro blèmes fai sant appel
à la notion d’arbre de valeur mini male, par exemple en opti mi sation des réseaux.
Étant donné un graphe valué G 5 (X, V), de n som mets et connexe, on veut
construire, en uti li sant n 2 1 de ses arêtes, un arbre dont la somme des valeurs (ou
coûts) des arêtes sera mini male.
En 1956, J.B. Kruskal a donné un algo rithme simple pour résoudre ce pro blème.
Il consiste à :
a) éta blir une liste des arêtes par valeurs crois santes ;
b) choi sir une arête de valeur mini male puis, suc ces si ve ment, au fur et à mesure de la
construc tion de l’arbre, l’arête sui vante dans la liste ne for mant pas un cycle avec les
arêtes rete nues jusque- là. S’arrê ter lorsque tous les som mets du graphe sont connec -
tés (ou, ce qui revient au même, lorsque le nombre d’arêtes rete nues égale n 2 1).
Pour un exemple se repor ter à la Fig 4.37.
Il s’agit du pre mier exemple de « méthode gour mande » (ou « glou tonne » ; en
anglais : « greedy algorithm »), car à chaque pas on choi sit l’élé ment le plus inté res -
sant (comme si l’on pre nait le plus gros mor ceau dans le par tage d’un gâteau).
Un autre algo rithme a été pro posé en 1961, par G. Sollin, alors chef de tra vaux au
CNAM, pour opti mi ser des réseaux de cana li sa tion ; le voici :
Ini tia le ment aucun som met n’a été « retenu ».
a) Choi sir arbi trai re ment un som met x en dehors de ceux qui ont déjà été rete nus ;
relier, par l’arête de valeur la plus faible, ce som met x à l’un des som mets (déjà retenu
ou non) aux quels il est adja cent ; soit y ce der nier som met : y est alors « retenu », de
même que x.
b) Lorsque tous les som mets ont été rete nus :
– soit on a obtenu un arbre et le pro blème est résolu : cet arbre est de coût minimal.
– soit on a seule ment plu sieurs sous arbres. Contrac ter cha cun en un som met unique ;
créer le multi graphe
1
dont chaque som met est asso cié à l’un de ces sous arbres et dont
1. On appelle multi graphe un graphe dont deux som mets au moins sont reliés par plus d’un arête.
r
Figure 4.36