树中的最大独立集。审查算法，需要证明

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的子树中最大独立集的大小。

该算法递归地计算这些，然后在根处选择两者中的最大值。