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をルートとするサブツリー内の最大独立集合のサイズです。

アルゴリズムはこれらを再帰的に計算し、ルートで2つの最大値を選択します。