Максимальный независимый набор в дереве. Алгоритм обзора, необходимо доказательство

Question

псевдокод:

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']); 
} 

нужно доказательство того, что max(a['X'], b['X']) является кардинальное максимального независимого множества в дереве. Что мне не хватает?

Заранее спасибо.

Answer 1

Элемент a [i] - это размер максимального независимого множества в поддереве, установленном в i, который содержит i.

Элемент b [i] представляет собой размер максимального независимого множества в поддереве, корневом в i, который не содержит i.

Алгоритм вычисляет эти рекурсивно, а затем выбирает максимальное из двух в корне.