16

我有一个无向连通图 G。如果至少有 2 个 MST，我希望找到一个返回 true 的算法。

如果我想查看是否正好有 2 个 MST 怎么办？

4

2 回答 2

22

我们可以通过修改 Kruskal 算法有效地检测这两种情况。如果有人能想到一种更简单的方式来描述这一切，请告诉我！

Kruskal 为等权边的每个排列构建一个 MST

Kruskal 算法通过始终包含连接迄今为止已构建的森林的不同组件的下一个最小边来构建 MST。只要选择了任何这样的最小边，即不管具有相同权重的边如何排序，该算法都是正确的。

克鲁斯卡尔可以找到每一个 MST

此外，每可以通过选择某种特定的方式对每组等权边进行排序，然后运行 ​​Kruskal 算法来生成 MST。为了看到这一点，假设有一些 MST 不能以这种方式生产。现在从这个 MST 中每个边的权重中减去一些小量 epsilon（小于任何不相等边权重之间的差）：这个 MST 现在是唯一的 MST，所以 Kruskal 必须在使用新的边权重运行时产生这个 MST . 但是因为我们最多只通过 epsilon 调整边，所以当边按权重排序时，权重为 w_i - epsilon 的所有边的集合必须立即出现（以某种顺序）在权重为 w_i 的边集（以某种顺序）之前，两组之间没有其他边。但对于原始的、未修改的边缘，这是一个有效的可能排序，并且 Kruskal 算法只关心边的顺序而不是它们的特定权重，因此 Kruskal 算法也必须从该顺序中产生 MST。这与我们的假设相矛盾，因此必须是克鲁斯卡尔算法可以产生每个 MST。

组件图

在 i >= 0 边添加步骤 F(i) 之后调用由 Kruskal 算法构建的森林，剩余的边要考虑并且不会创建循环 R(i)。（当在步骤 i 中添加一条边时，我们通过从 R(i-1) 的副本开始并删除刚刚添加的边和连接同一对组件的所有其他边来形成 R(i)。虽然 Kruskal算法实际上“懒惰地”消除了这些其他边，以这种方式定义 R(i) 简化了证明算法的属性。）我们将把 Kruskal 算法分解为一系列块，每个块都由一系列边添加组成，其中的边添加相同的重量。如果 i = 0 或 R(i) 中的最小权重边大于在步骤 1 中添加的任何边，则调用 i块定义.. i。

假设在执行了一些块定义数 i >= 0 的 Kruskal 算法的边加法步骤之后，R(i) 中的最小边（即不会创建循环的下一个最小边）的权重为 w . Kruskal 算法将继续以某种方式将所有在它们之间具有权重 w 边的树连接在一起，然后再执行其他任何操作，即使为这些等权边选择不同的边排序会影响生成的树，但它不会影响每棵树中的顶点集。使这更精确：

定义一个新的、未加权的多重图（即，在一对顶点之间可以有多个边的图）C(i)，由森林 F(i) 中每个组件（树）的顶点组成。对于 C(i) 中的任何顶点 v，调用 t(v) F(i) 中对应于 v 的树。只要 R(i) 中存在权重 w 边，就在 C 中的两个顶点 u 和 v 之间创建一条边在 t(u) 中的某个顶点和 t(v) 中的某个顶点之间。在 i 步后调用 C(i)组件图。

引理：假设对于某个块定义数 i，C(i) 有 k 个分量包含至少 1 个边（即不是单个顶点的分量），并且这些分量中总共有 m >= 2k 个顶点。称这组顶点为M。那么不管等权边是如何排序的，经过Kruskal算法mk个边加法步骤后，M中的顶点对应的m棵树将被合并为k棵树，其中第 j 棵树由对应于 C(i) 的第 j 个分量的顶点的树的并集组成，加上一个或多个权重为 w 的边，每个 1 <= j <= k。特别是，k 个结果树中的每一个中的顶点集不受在 C(i) 中产生边的权重 w 边的特定排序的影响。

证明：C(i) 中的每条边 (u, v) 对应于 R(i) 中的一个权重 w 边，该边可能首先出现在等权边的某个排列中的所有权重 w 边中，因此可以通过以下方式选择克鲁斯卡尔算法。添加它的效果是将 F(i) 中的两棵树合并为 F(i+1) 中的一棵树，并丢弃 R(i+1) 中的一条或多条边。对组件图的影响是将 C(i) 中的 u 和 v 合并为 C(i+1) 中的单个顶点 x，删除 C(i+1) 中 u 和 v 之间的所有其他平行边，并更改第三个顶点 y 和 C(i) 中的 u 或 v 之间的所有边变成 y 和 C(i+1) 中的新顶点 x 之间的边。如果接下来由 Kruskal 选择 C(i) 的一个分量中的一条边，则其他分量中的边不受影响，因此不同分量的边在排列中如何交错没有影响。因此我们可以假设首先看到一个组件的所有边，然后是另一个组件的所有边，依此类推，直到第 k 个组件。假设第一个组件有 s 个顶点。Kruskal 算法添加的每条边都会将该组件的顶点数减少 1，而不会断开该组件。在 C(i+j) 中的分量中存在一条边表示在 R(i+j) 中存在一条连接 F(i+j) 中两棵不同树的权重 w 边，因此 Kruskal 算法将继续选择缩小该分量的边，直到它成为 C(i+s-1) 中的单个顶点。无论在每一步选择哪些边，F(i+s-1) 中相应树中的顶点将由 F(i) 中 s 树中的所有顶点的并集组成。这可以对剩余的组件重复。

计算 MST

定理： MST 的数量是多重图 C(i) 中每个块定义 i 的生成森林数量的乘积。

证明：正如引理中所确定的，通过在 C(i) 中的边的某些排列上运行 Kruskal 可以产生的每个森林相对于 F(i+mk) 中每个结果树组件中的顶点集都是相同的。C(i) 的 s 顶点分量的每个生成树代表一组不同的 s-1 边，可以通过 Kruskal 算法选择这些边以生成一个不同的底层 MST，该 MST 包含 F(i) 中相应的 s 树集. 生成林是生成树的组合，每个组件一个，因此生成林的数量是每个包含的树的生成树数量的乘积。将 C(i) 中的生成森林数称为 q(i)。由于后续 Kruskal 块中的边添加步骤不关心每个组件的边结构，而只关心每个组件中的顶点，

计算图的生成树数量有一些复杂的算法，例如imslavko 给出的基于Kirchhoff 定理的算法。我不确定那个是否适用于多图。但无论如何，由于我们只关心特定情况 1、2 和 2 以上，我们可以走捷径。

  • 如果我们只想检测图形是否正好有 1 个 MST 或大于 1，我们可以使用这样一个事实，即整数乘积等于 1 的唯一方法是每个因子都等于 1：即如果有任何块C(i) 的生成树超过 1 个，立即停止并报告“超过 1 个”。如果我们没有发生这种情况就结束了，报告“1”。

  • 如果我们想检测图是否正好有 2 个 MST，我们可以使用这样一个事实：对于整数乘积等于 2，恰好有 1 个因子必须等于 2，其余的因子都必须为 1。对于多重图要恰好有 2 棵生成树，它必须由一个森林组成，再加上两个顶点之间已经有一条边的额外（平行）边。（任何包含 k >= 3 的 k 循环的多重图必须至少有 k 个生成树，通过删除 k 个边中的任何 1 个而形成。）

算法概述

像往常一样执行 Kruskal，但是每当一个新块开始时（由添加的边缘比之前添加的任何边缘都具有更高的权重表示），在添加边缘之前，执行以下步骤：

  1. 使用邻接表表示创建一个空的多重图 C。
  2. 向前扫描所有具有此权重的剩余边，对于每条边 (u, v)，将 (c(u), c(v)) 添加到 C，其中 c(v) 是联合找到的 v 的代表节点/find 用于检查连通性的结构。
  3. 通过这个多重图的每个组件执行 DFS，使用一组标志来记录哪些顶点已经被访问过。此 DFS 的目的是检查循环和平行边：
    • 如果有任何长度为 3 或更高的循环，则该组件至少有 3 棵生成树，这意味着算法可以在此时终止。
    • 如果出现任何平行边的重数为 3 或更多，该算法同样可以立即终止。
    • 每次在两个顶点之间看到一条双边，就增加一个全局计数器：如果这个计数器大于 1，那么至少存在 2*2 = 4 个 MST，因此算法可以再次立即终止。如果我们到达 Kruskal 算法的末尾并且计数器为 1，那么恰好存在 2 个 MST；否则它必须为 0，在这种情况下恰好存在 1 个 MST。

所有这些额外的操作在不相交的边块上都需要线性时间，因此它们不会增加底层 Kruskal 算法的时间复杂度超过 O(E log V)。

于 2012-12-08T15:57:08.107 回答
2

我知道确定不同生成树数量的算法：该算法使用基尔霍夫定理。我记得解决了关于最小树数的问题，但如果我没记错的话，它是指数级的。主要思想是测试树中使用的边缘的位掩码和包含-排除方法。

顺便说一句，如果所有边的权重都不同，则只有一个 MST。希望能帮助到你。

于 2012-12-08T01:48:21.137 回答