图表完全是2个最小的生成树

Question

说一个图表， $ g=（v，e）$ 有2个最小的生成树（MSTS）。 鉴于此条件规定，证明了所有的任何循环 MSTS（即，2中边缘的结合）中的边缘 MSTS）至少在集合中的2个边缘是 边缘具有平等的重量。还表明这个边缘是 循环中最大的重量，或者不是循环中最大的重量。

整体上我很困难这个问题。

我的初始想法是以下内容：在任何一个以上超过1兆的图表中，显然这意味着边缘权重不能明确，否则不会有多个MST。此外，图 $ g $ 必须包含周期，否则，它不会有多个MST。

证明由两个MST的边缘联盟形成的任何周期都将在 $ mst_1 $ 中有一些边缘， $ e $ 不在 $ mst_2 $ 并且还有一些边缘 $ f $ 不是 $ mst_1 $ 。如果 $ e $ 未放入 $ mst_2 $ 和 $ F $ 未放置在 $ mst_1 $ 然后我们有那个的权重> $ f $ ， $ e $ ， $ w（f）= w（e）$ 。

虽然遇到了正式化，并且想知道它是否实际上是正确的扣除。鉴于一些示例和绘图，我觉得它有意义，但实际上并不完全是真的。然后从那里开始，我觉得必须有一些节点， $ z $ 这样 $ z $ 2具有相同权重的边，并且当我们将边缘与 $ mst_1 $ 和 $ mst_2 $ 我们最终与<跨度类=“math-container”> $ z $ 形成循环的边缘，并且边缘是相同的权重，所以我们知道至少2个边缘形成一个循环。 。或者边缘的联合可以形成一个循环图本身，然后将显示具有相同权重的2个边缘是循环的一部分，我认为？这有点在正确的轨道上吗？图形是否有一些条件， $ g $ ，以便它恰好有2个MSTS？或者有一些我缺少的财产？

如果有人可以在正确的方向上提供一点指导，那就非常感谢。谢谢。

Answer 1

lemma： let $ c $ 是 $ g $ 包含一个唯一的边缘 $ e $ 的最大重量。边缘 $ e $ 不属于 $ g $ 。

证明： 假设MST $ t ^ *=（v，e ^ *）$ $ g $ 包含 $ e=（u，v）$ 。 root $ t ^ * $ $ u $ ，让> $ f $ 是 $ c \ setMinus e ^ * $ 在 $ t ^ * $ rooted $ v $ （此边缘始终存在，因为 $ c \ setminus $ 是来自 $ v $ 到 $ u $ 避免 $ e $ ）。边缘 $ f $ 关闭包含 $ e $ 的基本循环，并且是 $ w（f）<（e）$ 。 然后 $（v，（e ^ * \ setminus \ {e \}）\ cup \ {f \} $ ）是 $ g $ 重量小于 $ t ^ * $ 。这是一个矛盾。 $ \ square $

let $ t_1=（v，e_1）$ 和 $ t_2=（v，e_2）$ 是 $ g $ 的两个不同的msts。 让 $ c $ 是 $（v，e_1 \ cup e_2 $ ）的一个周期。 让 $ m=arg \ max_ {e \ in c} w（e）w（e）$ 。

如果 $ | m |> 1 $ 我们完成了。假设然后 $ m={e \} $ 。 通过上述LEMMA， $ E $ 是 $ c $ 的唯一最重的边缘，因此它不能属于到 $ g $ 的任何MST。这是一个矛盾，因为<跨度类=“math-container”> $ e $ 必须属于 $ e_1 $ 和 $ e_2 $ 。

Answer 2

考虑典型的MST算法。如果在某些步骤中，您可以在两个平等的两个边缘之间选择两个MST，并且只有在它们是周期的一部分时，才会发生。他们必须足够便宜地纳入MST，但这更难表征...