Ensemble indépendant maximal dans un arbre. algorithme d'examen, besoin de preuves

Question

pseudocode:

void recursive('k'){ // 'k' and 'i' vertices 
    sumA = 0; 
    sumB = 0; 
    for each non visited 'i' neighbor do{ 
    recursive('i'); 
    sumA = sumA + b['i']; 
    sumB = sumB + max(a['i'], b['i']); 
    } 
    a['k'] = 1 + sumA; 
    b['k'] = sumB; 
    } 


void main(){ 
a = b = 0; //initialize tables with 0 (zeros) 
recursive('X'); //let 'X' be an arbitrary root 
cout<<max(a['X'], b['X']); 
} 

besoin d'une preuve que max(a['X'], b['X']) est le cardinal de l'ensemble maximal indépendant dans l'arbre. Qu'est-ce qui me manque?

Merci d'avance.

Answer 1

L'élément a [i] est la taille de l'ensemble indépendant maximal de la sous-arborescence de i qui contient i.

L'élément b [i] est la taille de l'ensemble indépendant maximal dans le sous-arbre enraciné dans i qui ne contient pas i.

L'algorithme les calcule de manière récursive, puis choisit le maximum des deux à la racine.