这不是作业。我正在尝试根据教科书进行练习以理解 MST(最小生成树)。
假设我在加权无向图 G 中有一个循环 C。据我了解，以下是正确的:
C中的最重 边属于G的no MST。也就是说，G的没有 MST 包含该边。C中的最轻 边属于G的一些 MST。也就是说，存在一个G的MST，它包含该边。
现在我想知道以下说法是否也正确。
C中的最轻 边属于G的所有 MST。也就是说，G的 no MST 不包含该边。C中的任何边，最重 边都属于一些 MST。也就是说，对于C中的每条边(最重 边除外)，都有一个包含该边的 MST。
你能证明最后的说法吗？
最佳答案
即使对于第一个声明，如果有多个最轻的边，则不需要全部包含在 MST 中。
关于algorithm - 最小生成树的基本问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13891430/