Chapitre 4 • Appli ca tions des graphes à la recherche opé ra tion nelle
102
mi sation ne peuvent se faire que selon des ordres par ti cu liers ; dans les pro blèmes for te -
ment ordon nés, une seule décom po si tion et un seul ordre d’opti mi sation sont pos sibles.
Même en ave nir déter miné, les pro blèmes de carac tère éco no mique se posent dif fé -
rem ment lorsque l’hori zon est limité ou, au contraire, illi mité. Si, par exemple, le nombre
de phases aug mente indé fi ni ment, il se peut qu’on ait des dif fi cul tés à com pa rer des
fonc tions qui, elles aussi, aug mentent indé fi ni ment. Dans ce cas, on a sou
vent recours
à une pro cé dure d’actua li sa tion, qui est légi time à la fois du point de vue mathéma -
tique et du point de vue éco no mique, lorsque les phases se suc cèdent dans le temps.
Dans le cas contraire, on essaie par fois d’obte nir la conver gence « en moyenne » :
lim
NS 1`
F1 x 0 , c , x N 2
N
.
4.1.2 Exemple d’appli ca tion : déter mi na tion d’un ensemble
stable de car di nal maximal dans un arbre
Voici un exemple par
ti cu liè re ment effi cace d’uti li sation de la pro
gram ma tion dyna
mique. Nous consi dé rons G 5 1 X, E 2 un arbre pour lequel nous dési rons cal cu ler le
nombre de sta bi lité a1 G2 . Nous dirons qu’un ensemble de som mets S ( X est stable
si, pour toute paire de som mets x, yPS, l’arête [x, y] n’est pas dans G, autre ment dit
deux som mets quel conques de S ne sont pas adja cents. a(G) est alors la plus grande
cardinalité d’un ensemble stable, c’est- à-dire le nombre de som mets d’un ensemble
stable de car di nal maximal (qui com porte le plus grand nombre de som mets).
Bien que le nombre de sta bi lité soit géné
ra le ment dif fi cile à cal cu
ler pour un
graphe quel conque, nous allons mon trer que dans le cas d’un arbre (rap pe lons qu’un
arbre est un graphe d’au moins deux som mets, connexe et sans cycle ; la figure 4.2
repré sente un arbre), ce nombre peut être cal culé rapi de ment avec un algo rithme de
pro gram ma tion dyna mique.
En choi sis sant arbi trai re ment un som met r de l’arbre, nous défi
nis
sons de
manière unique une orien ta tion des arêtes de manière à déduire de cet arbre une
arbo res cence de racine r. Par souci de sim
pli fi ca tion, nous appel le
rons aussi G
cette arbo res cence et confon drons les arêtes de l’arbre avec les arcs de l’arbo -
res cence. Nous note rons G i la sous- arborescence extraite de l’arbo res cence G de
racine i
1
et, par exten sion, le sous- graphe cor res pon dant.
L’algo rithme est fondé sur la prop riété évi dente sui vante :
si S
*
est un ensemble stable pour G i alors soit le sommet i H S
*
, soit i x S
*
.
Pour chaque G i nous allons cal cu ler deux valeurs : R i la taille d’un ensemble stable
maximal (au sens de l’inclu sion) conte nant i, et R i la taille d’un ensemble stable
maximal ne conte nant pas i. Ainsi il est aisé de consta ter que a1 G i 2 5 max1 R i , R i 2 .
Nous allons main te nant mon trer com ment obte nir les deux valeurs R i et R i à par tir
des valeurs R j et R j des suc ces seurs j de i. Rappelons que G(i) désigne l’ensemble des
successeurs j du sommet i.
1. Pour alléger les notations, tout sommet x i est désigné cidessous par son numéro : i.
102
mi sation ne peuvent se faire que selon des ordres par ti cu liers ; dans les pro blèmes for te -
ment ordon nés, une seule décom po si tion et un seul ordre d’opti mi sation sont pos sibles.
Même en ave nir déter miné, les pro blèmes de carac tère éco no mique se posent dif fé -
rem ment lorsque l’hori zon est limité ou, au contraire, illi mité. Si, par exemple, le nombre
de phases aug mente indé fi ni ment, il se peut qu’on ait des dif fi cul tés à com pa rer des
fonc tions qui, elles aussi, aug mentent indé fi ni ment. Dans ce cas, on a sou
vent recours
à une pro cé dure d’actua li sa tion, qui est légi time à la fois du point de vue mathéma -
tique et du point de vue éco no mique, lorsque les phases se suc cèdent dans le temps.
Dans le cas contraire, on essaie par fois d’obte nir la conver gence « en moyenne » :
lim
NS 1`
F1 x 0 , c , x N 2
N
.
4.1.2 Exemple d’appli ca tion : déter mi na tion d’un ensemble
stable de car di nal maximal dans un arbre
Voici un exemple par
ti cu liè re ment effi cace d’uti li sation de la pro
gram ma tion dyna
mique. Nous consi dé rons G 5 1 X, E 2 un arbre pour lequel nous dési rons cal cu ler le
nombre de sta bi lité a1 G2 . Nous dirons qu’un ensemble de som mets S ( X est stable
si, pour toute paire de som mets x, yPS, l’arête [x, y] n’est pas dans G, autre ment dit
deux som mets quel conques de S ne sont pas adja cents. a(G) est alors la plus grande
cardinalité d’un ensemble stable, c’est- à-dire le nombre de som mets d’un ensemble
stable de car di nal maximal (qui com porte le plus grand nombre de som mets).
Bien que le nombre de sta bi lité soit géné
ra le ment dif fi cile à cal cu
ler pour un
graphe quel conque, nous allons mon trer que dans le cas d’un arbre (rap pe lons qu’un
arbre est un graphe d’au moins deux som mets, connexe et sans cycle ; la figure 4.2
repré sente un arbre), ce nombre peut être cal culé rapi de ment avec un algo rithme de
pro gram ma tion dyna mique.
En choi sis sant arbi trai re ment un som met r de l’arbre, nous défi
nis
sons de
manière unique une orien ta tion des arêtes de manière à déduire de cet arbre une
arbo res cence de racine r. Par souci de sim
pli fi ca tion, nous appel le
rons aussi G
cette arbo res cence et confon drons les arêtes de l’arbre avec les arcs de l’arbo -
res cence. Nous note rons G i la sous- arborescence extraite de l’arbo res cence G de
racine i
1
et, par exten sion, le sous- graphe cor res pon dant.
L’algo rithme est fondé sur la prop riété évi dente sui vante :
si S
*
est un ensemble stable pour G i alors soit le sommet i H S
*
, soit i x S
*
.
Pour chaque G i nous allons cal cu ler deux valeurs : R i la taille d’un ensemble stable
maximal (au sens de l’inclu sion) conte nant i, et R i la taille d’un ensemble stable
maximal ne conte nant pas i. Ainsi il est aisé de consta ter que a1 G i 2 5 max1 R i , R i 2 .
Nous allons main te nant mon trer com ment obte nir les deux valeurs R i et R i à par tir
des valeurs R j et R j des suc ces seurs j de i. Rappelons que G(i) désigne l’ensemble des
successeurs j du sommet i.
1. Pour alléger les notations, tout sommet x i est désigné cidessous par son numéro : i.