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

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.

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