樹中的最大獨立集。回顧算法，需要證明

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的最大獨立集的大小。

該算法遞歸地計算這些值，然後在根上選擇兩者中的最大值。