最小生成树和周期

Question

最小生成树是否有一个周期IF，使得周期的加权成本为0？既然这不会改变重量，它仍然可以被认为是最小的生成树吗？

Answer 1

通过适当考虑MST的定义可以回答这个问题。根据定义，树不包含循环。因此，即使使用零加权边创建的循环也不能成为树的一部分。我们可以删除这个零加权边缘，使其再次成为一棵树。但是，要使其成为MST，我们必须删除周期中最高权重边缘（请注意，我假设您的问题的前提假设唯一使得生成图不是最小的而不是树是循环）。

你提到了最小生成图的想法（MSG - 这不是一个真正的缩写，因为，由于原因解释，这不是真正的事情）。这实际上并不是一个有用的概念，因为在除零加权边缘之外的每种情况下，MST都是MSG。只删除一条边即可断开所有树木。因此，它们没有无关的边缘 - 因此添加另一条边以使其成为图形只会增加重量。例外是零加权边缘 - 添加它不会增加任何重量。从理论上讲，您可以根据需要为MST添加任意数量的零加权边，以生成任意数量的MSG。然而，由于两个原因，这不是一个非常有趣的属性：

1. MST将始终是任何MSG的子图，因此大多数分析都可以完成MST - 由于边缘较少，复杂性较低。
2. 基本上没有现实世界的情况由图表建模，其中0加权边缘是有意义的。在高速公路系统中，每个路段都有一定的长度。在每个电路中，每根电线都有一些电阻。即使您发现任何这些示例的零加权边缘（例如具有0欧姆电阻的电线，撇开这种物体的物理不可能性），您仍然需要MST，因为零加权边缘的货币成本肯定是非零的。