查看图中是否有两个MST的算法？

Question

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

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

Answer 1

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

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

Kruskal算法通过始终包含连接到目前为止构建的森林的不同组件的下一个最小边缘来构建MST.无论何时选择任何这样的最小边缘,即无论如何对具有相等权重的边进行排序,该算法都是正确的.

Kruskal可以找到每个MST

此外,每个 MST都可以通过选择某种特定方式来生成每组等权重边缘,然后运行Kruskal算法来生成.为了看到这一点,假设有一些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,则调用i 块定义,或者R(i)中的最小权重边缘大于步骤1中添加的任何边缘.

假设在执行Kruskal算法的边缘相加步骤的一些块定义数i> = 0之后,R(i)中的最小边(即,不会产生周期的下一个最小边)具有权重w .在进行任何其他操作之前,Kruskal算法将以某种方式将所有树之间具有权重w的树连接在一起,即使为这些等权边选择不同的边排序也会影响生成的树,但它不会影响该集顶点的每棵树.使这更精确:

定义一个新的未加权多图(即,在一对顶点之间可以有多个边的图)C(i)由森林F(i)中每个组件(树)的顶点组成.对于C(i)中的任何顶点v,调用t(v)F(i)中对应于v的树.每当R(i)中存在权重w边缘时,在两个顶点u和v之间创建C中的边在t(u)中的一些顶点和t(v)中的一些顶点之间.在步骤之后调用C(i)组件图.

引理:假设对于某些块定义数i,C(i)具有包含至少1个边的k个分量(即,不是单个顶点的分量),并且在这些分量中总共有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边缘中首先出现,因此可以被选择接下来是Kruskal算法.添加它的效果是将F(i)中的两个树连接在F(i + 1)中的一个树中,并从R(i + 1)中丢弃一个或多个边.对组件图的影响是将C(i)中的u和v合并为C(i + 1)中的单个顶点x,删除C(i + 1)中u和v之间的所有其他平行边,并更改第三个顶点y和u或v之间的所有边缘在C(i)中进入y和新顶点x之间的边缘C(i + 1).如果Kruskal接下来选择C(i)的一个分量中的边缘,则其他分量中的边缘不受影响,因此在置换中如何交错不同分量的边缘没有影响.因此,我们可以假设首先看到一个组件的所有边,然后看到另一个组件的所有边,依此类推,直到第k个组件.假设第一个组件有顶点.通过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个顶点,则需要mk步骤将每个组件缩小到单个顶点.

计算MST

定理:对于每个块定义i,MST的数量是多图C(i)中生成森林数量的乘积.

证明:如在引理中所确定的,通过在C(i)中的边缘的一些排列上运行Kruskal可以产生的每个森林与F(i + mk)中每个得到的树分量中的顶点集相同.C(i)的s-顶点分量的每个生成树表示可以由Kruskal算法选择的不同的s-1边缘集合,以产生包含F(i)中的对应s树集合的不同底层MST. .生成林是生成树的组合,每个组件一个,因此生成林的数量是每个包含的树的生成树数量的乘积.在C(i)q(i)中调用生成森林的数量.由于后续Kruskal块中的边缘添加步骤不关心每个组件的边缘结构,而只涉及每个组件中的顶点,因此从步骤i开始的块的q(i)生成林的任何选择都不会影响从步骤j> i开始的下一个块的生成森林数量,并且所有q(i)*q(j)森林都是不同的.

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

• 如果我们只想检测图形是否恰好是1 MST或大于1,我们可以使用以下事实:整数乘积等于1的唯一方法是每个因子是否等于1:即如果任何块C(i)有超过1个生成树,立即停止并报告"超过1".如果我们在没有发生这种情况的情况下结束,请报告"1".

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

算法概述

像往常一样执行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)的时间复杂度.

Answer 2

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

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