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']);
}
need proof that max(a['X'], b['X'])
is the cardinal of the maximum independent set in the tree.
What am I missing ?
Thank you in advance.