Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
104
des ensembles stables maximaux cor res pon dant aux sous- arborescences issues de
B (de racines Ε et F). La même pro cé dure que celle uti li sée pour le som met A peut
alors s’effec tuer pour les sous- graphes cor res pon dant aux arbo res cences de racines
Ε et F ; les arbo res cences de racines C puis D sont trai tées de manière ana logue à
l’arbo res cence de racine B. Il est laissé, pour exer cice au lec teur, le soin d’adap ter
l’algo rithme pré senté plus haut afin qu’il four nisse un ensemble stable maxi mal au
sens de l’inclusion.
Figure 4.3 Un deuxième ensemble stable de cardinalité maximale : a(G) = 10 = R
_
A
5B, H, I, K, L, M, N, O, P, Q6: on a cerclé en gras ses sommets.
Le lec teur pourra aisé ment véri fier que la com plexité de l’algo rithme est O(n).
L’uti li sation de la pro gram ma tion dyna mique pour ce pro blème se montre donc
par ti cu
liè re ment effi cace. Le lec teur est invité à se demander pour quoi ce même
schéma de pro gram ma tion dyna mique ne convient pas lorsque le graphe G n’est
plus un arbre…
4.2 Appli cA tions Aux che mins opti mAux
4.2.1 Pro blèmes de che mins de valeur opti male
Les pro blèmes de che mins de valeur mini male (ou, res pec ti ve ment, maximale) se
ren contrent très fré quem ment en recherche opé ra tion nelle. Nous consi dé rons ici des
graphes finis, connexes dont les arcs sont valués par des nombres réels.
On doit alors véri fier l’absence de cir cuit de valeur néga tive (resp. posi tive),
appelé « cir cuit absor bant ». En effet, s’il exis tait un tel cir cuit, la valeur mini male
des che mins de tout som met x vers tout som met de ce cir cuit (ou tout des cen dant
d’un som met de ce cir cuit) serait reje tée à 2` 1 resp. 1` 2 . Notons que si les arcs
du graphe sont valués par des nombres tous posi tifs, il ne sau rait exis ter de cir cuit
absor bant dans la recherche de che min de valeur mini male.
104
des ensembles stables maximaux cor res pon dant aux sous- arborescences issues de
B (de racines Ε et F). La même pro cé dure que celle uti li sée pour le som met A peut
alors s’effec tuer pour les sous- graphes cor res pon dant aux arbo res cences de racines
Ε et F ; les arbo res cences de racines C puis D sont trai tées de manière ana logue à
l’arbo res cence de racine B. Il est laissé, pour exer cice au lec teur, le soin d’adap ter
l’algo rithme pré senté plus haut afin qu’il four nisse un ensemble stable maxi mal au
sens de l’inclusion.
Figure 4.3 Un deuxième ensemble stable de cardinalité maximale : a(G) = 10 = R
_
A
5B, H, I, K, L, M, N, O, P, Q6: on a cerclé en gras ses sommets.
Le lec teur pourra aisé ment véri fier que la com plexité de l’algo rithme est O(n).
L’uti li sation de la pro gram ma tion dyna mique pour ce pro blème se montre donc
par ti cu
liè re ment effi cace. Le lec teur est invité à se demander pour quoi ce même
schéma de pro gram ma tion dyna mique ne convient pas lorsque le graphe G n’est
plus un arbre…
4.2 Appli cA tions Aux che mins opti mAux
4.2.1 Pro blèmes de che mins de valeur opti male
Les pro blèmes de che mins de valeur mini male (ou, res pec ti ve ment, maximale) se
ren contrent très fré quem ment en recherche opé ra tion nelle. Nous consi dé rons ici des
graphes finis, connexes dont les arcs sont valués par des nombres réels.
On doit alors véri fier l’absence de cir cuit de valeur néga tive (resp. posi tive),
appelé « cir cuit absor bant ». En effet, s’il exis tait un tel cir cuit, la valeur mini male
des che mins de tout som met x vers tout som met de ce cir cuit (ou tout des cen dant
d’un som met de ce cir cuit) serait reje tée à 2` 1 resp. 1` 2 . Notons que si les arcs
du graphe sont valués par des nombres tous posi tifs, il ne sau rait exis ter de cir cuit
absor bant dans la recherche de che min de valeur mini male.