algorithm - 一种算法，看看图中是否恰好有两个MST？

Question

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

如果我想看看是否有2个MST，该怎么办？

Answer 1

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

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

Kruskal算法通过始终包含连接到目前已构建的森林的不同组件的第二个最小边缘来构建MST。每当选择任何这样的最小边缘时，即不管如何排序具有相等权重的边缘，该算法都是正确的。

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

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

假设在执行了Kruskal算法的边加法步骤的某些块定义数i> = 0之后，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个结果树中的每一个中，一组顶点不受权重w边的特定排序的影响，该排序导致C（i）中的边。

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

计算MST

定理：MST的数量是每个块定义i的多图C（i）中生成林的数量的乘积。

证明：如在引理中所确定的，在F（i + m-k）中每个结果树分量的顶点集上，通过在C（i）中的边的某些排列上运行Kruskal可以产生的每个森林都是相同的。 C（i）的s顶点分量的每个生成树代表一组不同的s-1边，可以通过Kruskal算法选择它们，以生成包含F（i）中相应的s树集合的独特底层MST。 。生成林是生成树的组合，每个组成部分一个，因此生成林的数量是每个包含的树的生成树数量的乘积。称C（i）q（i）中的成林数。由于后续Kruskal块中的边缘加法步骤并不关心每个组件的边缘结构，而仅关心每个组件中的顶点，因此，从步骤i开始的块的q（i）生成林的任何选择都不会影响从步骤j> i开始的下一个块的跨林数量，并且所有q（i）* q（j）森林都是不同的。

用于计算图的生成树数量的算法有些复杂，例如基于Kirchhoff's theorem，given by imslavko的算法。我不确定那是否适用于多图。但是无论如何，由于我们只关心1、2和2以上的特殊情况，因此可以采用捷径。


如果我们只想检测图是否正好是1个MST或大于1，则可以使用以下事实：整数乘积等于1的唯一方法是每个因子等于1：即是否有任何块对于C（i）具有超过1个生成树，请立即停止并报告“大于1”。如果没有发生这种情况，请报告“ 1”。
如果我们要检测图是否具有精确的2个MST，则可以使用以下事实：对于等于2的整数乘积，恰好其中一个因子必须等于2，其余所有因子必须等于1。 multigraph要有2个生成树，它必须由一个森林加上两个顶点之间正好有一个边的正好一个附加（平行）边组成。 （任何包含k> = 3的k循环的多图必须至少有k个生成树，通过删除k个边中的任意一个形成。）


算法概述

照常执行Kruskal，但是只要有新的块开始（由添加的权重大于以前添加的边缘的边表示），在添加边缘之前，请执行以下步骤：


使用邻接表表示创建一个空的多重图形C。
向前扫描具有此权重的所有其余边缘，并为每个边缘（u，v）将（c（u），c（v））添加到C，其中c（v）是联合发现的v的代表性节点/ find结构用于检查连通性。
通过使用一组标志来记录已访问过哪些顶点，通过此Multigraph的每个组件执行DFS。此DFS的目的是检查循环和平行边：


如果有任何长度为3或更高的循环，则该组件至少具有3个生成树，这意味着算法可以在此点终止。
如果出现平行度大于或等于3的平行边，该算法同样可以立即终止。
每次在两个顶点之间看到双边时，都增加一个全局计数器：如果此计数器大于1，则至少存在2 * 2 = 4个MST，因此算法可以立即终止。如果我们到达Kruskal算法的末尾，并且计数器为1，则确切地存在2个MST。否则，它必须为0，在这种情况下恰好存在1个MST。



所有这些附加操作在不相交的边块上花费线性时间，因此它们不会增加基础Kruskal算法的时间复杂度超过O（E log V）。