关于最小生成树计数算法的粗浅证明

问题描述

最小生成树计数问题是给定一个无向带权图，问你能生成最小生成树的数量为多少。

存在多个最小生成树的原因

出现多棵最小生成树的原因在于，我们存在一些权值相同的边，相互替换之后整张图的联通性不变。

这里你可能会问，为什么权值不同的边就不能替换了呢？

简单证明一下
就拿两两交换的情况来说，因为一一交换显然不成立，如果你还要对此表示质疑我也没办法……

两两交换的情况就是* 存在用两条不是很大也不是很小的边与替代两条极大极小的边的情况。*

稍微专业点的说法就是，存在极小和极大的中间有两条边可以替代两边的边 不仅能保持整张图联通性不变，并且权值和不会增大。

我这里表示，不可能

举个例子，首先 b – c 已经在同一个集合中了。
并且 存在 四条边

1. a – b 权值为 1
2. c – d 权值为 100
3. a – c 权值为 50
4. c – d 权值为 51

我们要考虑的问题是 能否让 3 边和 4 边去替代 1 边和 2 边
有了数据，这个问题就很显然了，1 边和 2 边根本不可能在最小生成树上，因为不仅 1 边 和 3 边的联通性与之相同，并且权值更小。

同理，我们可以将之拓展到 n >= 3 的情况。

算法引入

最小生成树计数算法是基于克鲁斯卡尔算法的一些操作。

根据以上存在多个最小生成树的原因，我们把最小生成树分成多个权值相同的边的最小生成树，再运用乘法原理计算。

因此在运用克鲁斯卡尔算法的中间过程中，我们需要记录所有相同权值的边，和这些边在整个最小生成树的联通度。
因为在克鲁斯卡尔算法的流程中，每条边都是按照边权排序的，所以我们记录所有相同权值的边只需要记录一个区间即可。
而联通度，只需要在合并操作中进行记录即可。

剩下的关键就是如何求出生成树的数量。(因为权值都已经相同了)

• 一种暴力的解法就是直接搜索，这个方法复杂度就是相同权值的边数的最大数量的阶乘。搜索途中满足联通性不变则方案数++即可。优点就是写得快，不建议在最大边数大于10的时候使用。
• 另一种方法是运用矩阵树定理。这种算法写起来很长，但复杂度为 点数 n ^ 3 。
  (这里我不细讲这些)

这个时候有些朋友就会提出这样的困惑，如何保证在每个权值相同的生成树计算过程中，整棵树的桥必定会包含在内
这个问题其实挺煞笔的，我写这个问题主要是我煞笔的被困在这里面一小段时间。

保证整棵树的桥必定会被加入到相应的生成树的原因

再简单证明一下
既然是整棵树的桥，那么也就是权值相同的生成树的桥，所以无论在计算最小生成树的过程中，还是在计算权值相同的生成树的过程中，这条边必定会加入在内。
前者因为不加的话，无法形成生成树。后者则是不满足联通性条件。