4.1 Notions de pro gram ma tion dyna mique (PRD)
103
© Dunod – Toute reproduction non autorisée est un délit.
Pre mière ment, si G i ne compte que le seul som met i (qui est alors une « feuille »
– ou « som met pen dant » – de l’arbo res cence G) nous avons immé dia te ment
R i 5 1 et R i 5 0. Main te nant, si i a des suc ces seurs et i appar tient à un sous- ensemble
stable de G i , alors aucun de ses suc ces seurs j ne peut appar te nir à ce stable ; donc
R i 5 1 1 a
jPG1i2
R j ; si i n’appar tient pas à un stable de G i , ces suc ces seurs j peuvent
ou non appar te nir à ce stable, donc R i 5 a
jPG1i2
a1 G j 2 . La for mule récur sive sui vante,
appliquée à par tir d’un som met quel conque d’une arbo res cence G, cal cule a1 G i 2 :
• si G(i) 5 [ : R i 5 1 ; R i 5 0 ; a(G i ) 5 1 (initialisation).
• sinon : R i 5 1 1 a
jPG(i)
R j ; R i 5 a
jPG(i)
a(G j ) ; a(G i ) 5 max (R i , R i ).
La figure 4.2 illustre l’appli ca tion de la for mule pré cé dente. Les pre mières
valeurs sont cal cu lées à par tir des feuilles de l’arbre puis remon tées de proche en
proche jus qu’à la racine. Pour tout som met i sont notées les deux valeurs 1 R i , R i 2 , on
en déduit aisé ment a1 G i 2 5 max 1 R i , R i 2 . Les som mets cer clés sont les 10 som mets
for mant un ensemble stable de car di nal maximal. Notons que l’ensemble stable opti -
mal obtenu n’est pas unique, la figure 4.3 montre une deuxième solu tion équi va lente.
L’opti mum n’est pas unique ici ; mais la valeur a(G) est toujours unique.
Figure 4.2 Cal cul du nombre de sta bi lité d’un arbre A : ici a(G) = 10 = R A
S
* 5 5A, F, H, I, K, L, N, O, P, Q6 : on a cerclé en gras ses sommets
L’ensemble stable repré senté dans la figure 4.2 a été obtenu de la manière sui
vante : puisque R A 5 R A 5 10, le som met A peut soit appar te nir soit ne pas appar -
te nir à un ensemble stable de 10 élé ments : choi sis sons la solu tion qui contient A
(remar quons que celle repré sen tée par la figure 4.3 ne contient pas A). Les som -
mets B, C, D, suc ces seurs de A dans l’arbo res cence n’appar tiennent donc pas au
stable ; pour le sous- graphe cor res pon dant à l’arbo res cence de racine B, un ensemble
stable maximal ne conte nant pas B est de taille R B 5 3 et consiste en la réunion
103
© Dunod – Toute reproduction non autorisée est un délit.
Pre mière ment, si G i ne compte que le seul som met i (qui est alors une « feuille »
– ou « som met pen dant » – de l’arbo res cence G) nous avons immé dia te ment
R i 5 1 et R i 5 0. Main te nant, si i a des suc ces seurs et i appar tient à un sous- ensemble
stable de G i , alors aucun de ses suc ces seurs j ne peut appar te nir à ce stable ; donc
R i 5 1 1 a
jPG1i2
R j ; si i n’appar tient pas à un stable de G i , ces suc ces seurs j peuvent
ou non appar te nir à ce stable, donc R i 5 a
jPG1i2
a1 G j 2 . La for mule récur sive sui vante,
appliquée à par tir d’un som met quel conque d’une arbo res cence G, cal cule a1 G i 2 :
• si G(i) 5 [ : R i 5 1 ; R i 5 0 ; a(G i ) 5 1 (initialisation).
• sinon : R i 5 1 1 a
jPG(i)
R j ; R i 5 a
jPG(i)
a(G j ) ; a(G i ) 5 max (R i , R i ).
La figure 4.2 illustre l’appli ca tion de la for mule pré cé dente. Les pre mières
valeurs sont cal cu lées à par tir des feuilles de l’arbre puis remon tées de proche en
proche jus qu’à la racine. Pour tout som met i sont notées les deux valeurs 1 R i , R i 2 , on
en déduit aisé ment a1 G i 2 5 max 1 R i , R i 2 . Les som mets cer clés sont les 10 som mets
for mant un ensemble stable de car di nal maximal. Notons que l’ensemble stable opti -
mal obtenu n’est pas unique, la figure 4.3 montre une deuxième solu tion équi va lente.
L’opti mum n’est pas unique ici ; mais la valeur a(G) est toujours unique.
Figure 4.2 Cal cul du nombre de sta bi lité d’un arbre A : ici a(G) = 10 = R A
S
* 5 5A, F, H, I, K, L, N, O, P, Q6 : on a cerclé en gras ses sommets
L’ensemble stable repré senté dans la figure 4.2 a été obtenu de la manière sui
vante : puisque R A 5 R A 5 10, le som met A peut soit appar te nir soit ne pas appar -
te nir à un ensemble stable de 10 élé ments : choi sis sons la solu tion qui contient A
(remar quons que celle repré sen tée par la figure 4.3 ne contient pas A). Les som -
mets B, C, D, suc ces seurs de A dans l’arbo res cence n’appar tiennent donc pas au
stable ; pour le sous- graphe cor res pon dant à l’arbo res cence de racine B, un ensemble
stable maximal ne conte nant pas B est de taille R B 5 3 et consiste en la réunion