在无向连通图中，如果e是与顶点v相邻的最轻边，那么e是某些MST的一部分吗？
我说是因为MST选择了所有最轻的边，这是正确的想法吗？
最佳答案
设T为最小权生成树，v w为与v相关的最轻边，P为T中v与w之间的唯一路径，如果P不是vw本身，则它包含一些其他边vx设t'是通过插入vw和移除vx从t导出的边集。我声称（1）T'至少和T一样轻，因为vw至少和vx一样轻（2）T'是一棵树，因为它连接了所有的东西（对于每个walk-in T，通过用vw和P的其余部分替换vx得到一个具有相同端点的相关walk-in T'，并且具有正确的边数，因此（3）T'是包含vw的最小权重生成树。
关于algorithm - 是MST中最相邻的一条边，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50166422/