qua*_*abe 16 algorithm minimum-spanning-tree
我正在研究一种算法来检查给定边缘是否包含在所有可能的mst之一中.
对于这个问题,我们正在考虑非不同的值,我们的边e连接顶点A和B.
到目前为止,我有:如果一条路径可以从A到B组成,边缘的权重小于或等于我们边缘e的权重 - 我们可以说边缘e不是任何MST的一部分.
我在这里遗漏了什么/关于更好算法的想法吗？
编辑:
关于循环属性的解决方案有什么想法 - 所以,我们认为所有边缘的权重都小于我们考虑的边缘.如果我们可以使用这些边缘从A-> B创建路径,我们可以说它不是任何MST的一部分？
Nik*_*nka 24
我们将使用MST循环属性来解决这个问题,该属性表示"对于图中的任何循环C,如果C的边e的权重大于C的所有其他边的权重,则该边不能属于MST".
现在,运行以下O(E+V)算法来测试连接顶点u和v的边E是否是某个MST的一部分.
步骤1
从边缘E的一个端点(u或v)运行dfs,仅考虑那些权重小于E的边缘.
第2步
情况1 如果在此dfs的末尾,顶点u和v连接,则边E不能是某些MST的一部分.这是因为在这种情况下,图中肯定存在一个周期,边E具有最大权重,并且它不能是MST的一部分(来自循环特性).
情况2 但是如果在dfs u和v的末尾保持断开连接,则边E必须是某些MST的一部分,因为在这种情况下,E始终不是它所属的所有周期中的最大权重边.
小智 5
我将写下我对这个问题的想法。
循环属性在这里非常重要：任何循环中的最大边不能位于最小生成树中。
为了证明循环性质，假设存在一棵最小生成树 T，其中包含边 e，该边 e 是循环中最大成本边。那么我们可以删除树T中的边e，得到两个集合S和T。那么环路中一定包含除e之外的连接集合S和T的边。那么从割性质来看，边e不能是在最小生成树中。
一旦我们有了循环属性，我们就可以继续断言某个边 e 是否在最小生成树中：
当且仅当存在时，边 e(v,w) 不属于任何最小生成树来自 v 和 w 的路径，其中该路径上的每条边都小于 e。
使用上述主张，算法如下：
删除所有大于或等于 e 的边，现在我们得到图 G'。运行DFS检查G'中v和w是否连通。如果v和w仍然相连，则边e不属于任何最小生成树。如果 v 和 w 没有连接，则边 e 在某个最小生成树中。