时间戳

首页 > 解决方案 > 是切割属性二的方式吗？

algorithm - 是切割属性二的方式吗？

问题描述

根据 MST 的割属性，如果一条边属于图的割集，则 MST 包含这条边。

但是，如果一个 MST 包含一条边，那么这条边是否一定属于割集？

标签： algorithmgraph-algorithmminimum-spanning-tree

解决方案

您没有正确复制 cut 属性。cut 属性是（来源：维基百科

对于图的任意割C，如果C的割集中边e的权重严格小于C割集的所有其他边的权重，则该边属于图的所有MST .

因此，一条边只属于任何割的割集是不够的。此外，它必须是该割集中唯一的最小权重边。

那么，倒置呢：如果一条边属于 MST，那么一定存在一个割集，其割集包含这条边。

这显然是正确的，因为您可以定义任意切割。包括一个在其切割集中包含边的。

更精确的公式是什么：如果一条边属于 MST，那么一定有一个割，其割集包含这条边，并且该边的权重严格小于该割集的所有其他边。

这不是真的。只需考虑一个所有边都相等的图。然后没有满足标准的边（没有边的权重比其他任何边都小），但 MST 不是空的。

推荐阅读