java - 具有 N 个标记顶点和 K 个未标记边的简单连通图的数量

Question

tl;博士我的递归关系解释的图表数量少于应有的数量。

我需要找出具有 N 个标记顶点和 K 个未标记边的简单连通图的数量。 Link to full source with complete question

[我看过this post它没有解决我的问题]

约束:2 <= N <= 20。因此，N-1 <= K <= N(N-1)/2。

我用两种不同的(不完全是，我后来意识到)想法来解决这个问题。

第一个想法:用 K 条边连接 N 个节点，使得 2 个节点之间有 1 条路径思路:考虑N-1 节点和K-1 边。添加第N个节点有多少种方法？

• 在节点 N 和任何其他 N-1 节点之间分配 1 条边；这是微不足道的，\binom {N-1}1，即给定 N-1 选择 1。
• 在 .... 之间分配 2 条边
• ....
• ....
• 在...之间分配 N-1 条边。

我想出的“公式”看起来像这样:

我们只看 K ∈ [N-1, N(N-1)/2] 的值(其他值没有意义)。当 K = N-1 时，它基本上属于 Cayley's formula。 .递归关系是我想出的部分。 问题是我考虑的图表数量少于应有的数量。代码:

static Map<List<Integer>, String> resultMap = new HashMap<List<Integer>, String>();
// N -> number of nodes
// K -> number of edges
// N will be at least 2 and at most 20.
// K will be at least one less than n and at most (n * (n - 1)) / 2
public static String answer(int N, int K) {
    /* for the case where K < N-1 */
    if(K < N-1)
        return BigInteger.ZERO.toString();

    /* for the case where K = N-1 */
    // Cayley's formula applies [https://en.wikipedia.org/wiki/Cayley's_formula].
    // number of trees on n labeled vertices is n^{n-2}.
    if(K == N-1)
        return BigInteger.valueOf((long)Math.pow(N, N-2)).toString();

    /* for the case where K > N-1 */
    // check if key is present in the map
    List<Integer> tuple = Arrays.asList(N, K);
    if( resultMap.containsKey(tuple) )
        return resultMap.get(tuple);

    // maximum number of edges in a simply 
    // connected undirected unweighted graph 
    // with n nodes = |N| * |N-1| / 2
    int maxEdges = N * (N-1) / 2;

    /* for the case where K = N(N-1)/2 */
    // if K is the maximum possible 
    // number of edges for the number of 
    // nodes, then there is only one way is 
    // to make a graph (connect each node
    // to all other nodes)
    if(K == maxEdges)
        return BigInteger.ONE.toString();

    /* for the case where K > N(N-1)/2 */
    if(K > maxEdges)
        return BigInteger.ZERO.toString();

    BigInteger count = BigInteger.ZERO;

    for(int k = 1; k <= N-1 ; k++) {
        BigInteger combinations = nChooseR(N-1, k);
        combinations = combinations.multiply(new BigInteger(answer(N-1, K-k)));
        count = count.add(combinations);
    }

    // unmodifiable so key cannot change hash code
    resultMap.put(Collections.unmodifiableList(Arrays.asList(N, K)), count.toString());

    return count.toString();
}

我找到了 this在 MSE 上发帖解决了同样的问题。使用它作为引用，“公式”看起来有点像这样: 这完全符合预期。此部分的代码如下。

static Map<List<Integer>, String> resultMap2 = new HashMap<List<Integer>, String>();
// reference: https://math.stackexchange.com/questions/689526/how-many-connected-graphs-over-v-vertices-and-e-edges
public static String answer2(int N, int K) {
    /* for the case where K < N-1 */
    if(K < N-1)
        return BigInteger.ZERO.toString();

    /* for the case where K = N-1 */
    // Cayley's formula applies [https://en.wikipedia.org/wiki/Cayley's_formula].
    // number of trees on n labeled vertices is n^{n-2}.
    if(K == N-1)
        return BigInteger.valueOf((long)Math.pow(N, N-2)).toString();

    /* for the case where K > N-1 */
    // check if key is present in the map
    List<Integer> tuple = Arrays.asList(N, K);
    if( resultMap2.containsKey(tuple) )
        return resultMap2.get(tuple);

    // maximum number of edges in a simply 
    // connected undirected unweighted graph 
    // with n nodes = |N| * |N-1| / 2
    int maxEdges = N * (N-1) / 2;

    /* for the case where K = N(N-1)/2 */
    // if K is the maximum possible 
    // number of edges for the number of 
    // nodes, then there is only one way is 
    // to make a graph (connect each node
    // to all other nodes)
    if(K == maxEdges)
        return BigInteger.ONE.toString();

    /* for the case where K > N(N-1)/2 */
    if(K > maxEdges)
        return BigInteger.ZERO.toString();

    // get the universal set
    BigInteger allPossible = nChooseR(maxEdges, K);

    BigInteger repeats = BigInteger.ZERO;
    // now, to remove duplicates, or incomplete graphs
    // when can these cases occur?
    for(int n = 0 ; n <= N-2 ; n++) {

        BigInteger choose_n_from_rem_nodes = nChooseR(N-1, n);

        int chooseN = (N - 1 - n) * (N - 2 - n) / 2;

        BigInteger repeatedEdges = BigInteger.ZERO;
        for(int k = 0 ; k <= K ; k++) {
            BigInteger combinations = nChooseR(chooseN, k);

            BigInteger recurse = new BigInteger(answer2(n+1, K-k));

            repeatedEdges = repeatedEdges.add(combinations.multiply(recurse));
        }

        repeats = repeats.add(choose_n_from_rem_nodes.multiply(repeatedEdges));
    }

    // remove repeats
    allPossible = allPossible.subtract(repeats);

    // add to cache
    resultMap2.put(Collections.unmodifiableList(Arrays.asList(N, K)), allPossible.toString());
    return resultMap2.get(tuple);
}

如果有人能指出我的方向，以便我可以在我的第一种方法中发现错误，我将不胜感激。第二种方法有效，但它会进行 O(NK) 次递归调用，并且 K 在 N 中平均为二次方。因此，显然不是很好，尽管我已尝试使用 DP 来最小化计算。 nChooseR() 和 factorial() 函数如下。

nChooseR 代码:

static Map<List<Integer>, BigInteger> nCrMap = new HashMap<List<Integer>, BigInteger>();
// formula: nCr = n! / [r! * (n-r)!]
private static BigInteger nChooseR(int n, int r) {
    // check if key is present
    List<Integer> tuple = Arrays.asList(n, r);
    if( nCrMap.containsKey(tuple) )
        return nCrMap.get(tuple);

    // covering some basic cases using
    // if statements to prevent unnecessary
    // calculations and memory wastage

    // given 5 objects, there are 0 ways to choose 6
    if(r > n)
        return BigInteger.valueOf(0);

    // given 5 objects, there are 5 ways of choosing 1
    // given 5 objects, there are 5 ways of choosing 4
    if( (r == 1) || ( (n-r) == 1 ) )
        return BigInteger.valueOf(n);

    // given 5 objects, there is 1 way of choosing 5 objects
    // given 5 objects, there is 1 way of choosing 0 objects
    if( (r == 0) || ( (n-r) == 0 ) )
        return BigInteger.valueOf(1);

    BigInteger diff = getFactorial(n-r);

    BigInteger numerator = getFactorial(n);

    BigInteger denominator = getFactorial(r);
    denominator = denominator.multiply(diff);

    // unmodifiable so key cannot change hash code
    nCrMap.put(Collections.unmodifiableList(Arrays.asList(n, r)), numerator.divide(denominator));

    return nCrMap.get(tuple);
}

阶乘代码:

    private static Map<Integer, BigInteger> factorials = new HashMap<Integer, BigInteger>();
    private static BigInteger getFactorial(int n) {
        if(factorials.containsKey(n))
            return factorials.get(n);

        BigInteger fact = BigInteger.ONE;
        for(int i = 2 ; i <= n ; i++)
            fact = fact.multiply(BigInteger.valueOf(i));

        factorials.put(n, fact);

        return fact;
    }

部分测试代码:

public static void main(String[] args) {
    int fail = 0;
    int total = 0;
    for(int n = 2 ; n <= 20 ; n++) {
        for(int k = n-1 ; k <= n*(n-1)/2 ; k++) {
            total++;
            String ans = answer(n,k);
            String ans2 = answer2(n,k);
            if(ans.compareTo(ans2) != 0) {
                fail++;
                System.out.println("N = " + n + " , K = " + k + " , num = " + ans + " ||| " + ans2);
            }
        }
    }
    System.out.println("Approach 1 fails " + ((100*fail)/total) + "% of the test");
}

附言作为 Google Foobar 挑战的一部分，我接受了这个挑战。只是想让所有人都知道这一点。 answer2() 根据挑战者无法看到的 Foobar 上的测试用例判断为有效。只是为了阅读所有这些，这里有一个 video of a tiny hamster eating a tiny burrito .

Answer 1

另一种方法...

我们知道 f(n,n-1) = n^{n-2} 是个数的计数函数标记有根树 [Cayley 公式]

现在，令f(n, k) 为具有n 个节点和k 个边的连通图的总数，我们有一个关于如何添加新边缘的特征:

1) Take any graph in F[n,k], and you can add an edge between any of the {n \choose 2} - k pairs of unmatched nodes.

2) If you have two connected graphs g_1 and g_2, say in F[s, t] and F[n-s, k-t] respectively (that is, a connected graph with s nodes and t edges and a connected graph with n-s nodes and k-t edges), then you can surgically construct a new graph by connecting these two subgraphs together.

你有s * (n-s)对顶点可供选择，你可以选择s 点 {n\choose s} 方式。然后你可以总结选择s 和 t 分别从 1 到 n-1，这样做，你将有每张图重复计算两次。我们称此构造为 g(n, k)。

然后 g(n,k) = (\sum_s,t {n\choose s} s (n-s) f(s,t) f(n-s, k​​-t))/2

现在，没有其他方法可以添加额外的边(不减少到上面的两个结构)，所以加法项h(n,k+1) = (N - k)f(n,k) + g(n,k)给出了我们已经得到的多组图的特征建。为什么这是一个多重集？

好吧，我们来看一个关于两个子案例的案例分析(对建筑的归纳)。在h(n, k+1)图中取一个随机图g以这种方式构建。归纳假设是，有k + 1 多重集 h(n, k+1) 中 g 的副本。

我们只看归纳案例如果您断开连接图中的一条边，那么它要么保持连接图或它分成两个连接的图。现在，固定在 edge e 上，如果你打破任何其他边缘，那么 e 仍然是在 (k+1) - 1 个不同的结构中。如果你打破 e，你将拥有另一个独特的建筑。这意味着有 k + 1 种可能的不同图类(两个组件的任何一个组件)我们可以从中构造相同的最终图g。

因此，h(n,k+1) 对每个图形总共计数了 k+1 次，依此类推f(n, k+1) = h(n, k+1)/(k+1) = ((N-k)f(n,k ) + g(n,k))/(k+1).

给定一个固定的n和k，这个循环将在O((nk)^2)时间内计算出正确的结果，如此复杂，它等同于之前的算法。这种构造的好处在于它很容易产生解析生成函数，以便您可以对其进行分析。
在这种情况下，假设您有一个复值函数 f_k(x,y)，然后

2 dy f_{k+1} = (x^2 dx^2 f_k - 2 y dy f_k) +\sum_s z^2 dz f_s dz f_{k-s}。

您将需要大量复杂的分析机制来求解此递归 PDE。

这是一个 java 实现 [ source ]