根据MST的割性，如果一条边属于图的割集，则MST包含这条边。
但是，如果 MST 包含一条边，那么这条边一定属于割集，这是真的吗？
最佳答案
您没有正确复制剪切属性。剪切属性为(来源:Wikipedia
For any cut C of the graph, if the weight of an edge e in the cut-set of C is strictly smaller than the weights of all other edges of the cut-set of C, then this edge belongs to all MSTs of the graph.
因此，边属于任何割的割集是不够的。此外，它必须是该割集中唯一的最小权重边。
那么，反转呢:如果一条边属于 MST，则必须有一个割集包含这条边的割。
这显然是正确的，因为您可以定义任意切割。包括在其切割集中包含边的一个。
更精确的公式是什么:如果一条边属于 MST，则必须有一个切割，其切割集包含该边，并且该边的权重严格小于切割集中的所有其他边。
这不是真的。只需考虑一个所有边都相等的图。则没有满足条件的边(没有边的权重严格小于任何其他边)，但 MST 不为空。
关于algorithm - Cut-Property 是两种方式吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53057955/