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

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

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