アルゴリズム：ツリー内の独立した集合の数を見つける方法は？

Question

私は、各サブツリーに対して2つのケースがあると考えています。ルートは独立セットにあり、ルートはセットに含まれていません。ツリー内の独立した集合の数を見つけるための再帰アルゴリズムを書くにはどうすればよいですか？木はn-aryです。

https://en.wikipedia.org/wiki/Independent_set_(graph_theory)

これは、これまで私の解決策ですが、それは正しくありません。変数parentIncludedは、現在のサブツリーの親がすでに独立セットに含まれている場合はtrueになります。したがって、現在のサブツリーのルートを独立セットに追加することはできません。 parentIncludedがfalseの場合、現在のサブツリーのルートを独立したセットに追加できます。 parentIncludedがfalseの場合は2つの場合があります。最初のケース：セットにルートを追加します。 2番目のケース：ルートを追加しないでください。

public static int numberOfIndependentSets(Binary root) { 
     if (root == null) { 
      return 1; 
     } 
     return numberOfIndependentSets(root, false) + 1; 
    } 

    private static int numberOfIndependentSets(Binary current, boolean parentIncluded) { 
     if (current.left == null && current.right == null) { 
      if (parentIncluded) { 
       return 0; 
      } else { 
       return 1; 
      } 
     } 
     int total = 0; 
     if (parentIncluded) { 
      int left = numberOfIndependentSets(current.left, false); 
      int right = numberOfIndependentSets(current.right, false); 
      total += (left + 1) * (right + 1) - 1; 
     } else { 
      // include current node 
      int left = numberOfIndependentSets(current.left, true); 
      int right = numberOfIndependentSets(current.right, true); 
      total = (left+1) *(right +1); 

      // not include current node 
      left = numberOfIndependentSets(current.left, false); 
      right = numberOfIndependentSets(current.right, false); 
      total += (left+1) * (right+1) -1; 
     } 
     return total; 
    } 

Answer 1

基本的な考え方が有効です。

あなたが根ざし木のセットに二つの相互再帰関数を定義した可能性：

あなたは基本ケースとして、我々が持っている、1ノードの木については f(T) + g(T)

、Lを計算したい

f(T) = number of independent sets containing the root 
g(T) = number of independent sets not containing the root 

：

f(L) = 1 
g(L) = 1 

T_1, T_2, .. T_nはルートのサブツリーです。そして、再帰方程式は、次のとおりです。チェックとして

f(T) = g(T_1)*g(T_2)* ... *g(T_n) 
g(T) = (f(T_1)+g(T_1))*(f(T_2)+g(T_2)) * ... * (f(T_n)+g(T_n)) 

：あなたはnレベル（同等に、高さn-1）との完全なバイナリツリーの独立したセットの数を取得するためにこれを使用することができます。 f、gをレベルの関数にします。 Python実装：

def f(n): 
    if n == 1: 
     return 1 
    else: 
     return (g(n-1))**2 

def g(n): 
    if n == 1: 
     return 1 
    else: 
     return (f(n-1) + g(n-1))**2 

def h(n): return f(n)+g(n) 

[h(n) for n in range(1,7)]は

2, 5, 41, 2306, 8143397, 94592167328105 

に評価これは2で完全二分木の上の独立集合の数」と記載されている（わずかにずれた）オンライン百科事典で配列A076725であります^（n-1）-1個のノード "であるので、このアプローチは理にかなっているようです。