算法:如何找到树中独立集的数量？

Question

我在想每棵子树有两种情况:根在独立集合中和根不在集合中。如何编写递归算法来查找树中独立集的数量？树是 n 元的。

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

到目前为止，这是我的解决方案，但并不正确。如果当前子树的父节点已经包含在独立集中，则变量parentIncluded 等于true，因此当前子树的根不能添加到独立集中。如果parentIncluded等于false，则可以将当前子树的根加入独立集。 parentIncluded 为 false 时有两种情况。第一种情况:将根添加到集合中。第二种情况:不加根。

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

您的基本想法应该可行。

您可以在有根树的集合上定义两个相互递归的函数:

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

您想计算 f(T) + g(T)

对于 1 节点树，L，作为基本情况，我们有:

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成为level的函数。 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

这是序列A076725 Online Encyclopedia(略有偏移)中描述为“具有 2^(n-1)-1 个节点的完整二叉树上独立集的数量”，因此这种方法似乎是有道理的。