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

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 成为水平函数。 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（略有偏移）描述为"the number of independent sets on a complete binary tree with 2^(n-1)-1 nodes"，看来这种做法是有道理的。

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

Algorithm: How to find the number of independent sets in a tree?

algorithm

graph-theory

independent-set