是否存在不包含最小/最大加权边的最小生成树？

Question

如果我们有一个(任意)连接的无向图G,其边缘具有不同的权重,

另外,如果有人能够提供一些在处理此类MST问题时必须记住的关键事项,我会更感谢.

这是一个家庭作业问题.谢谢.

Answer 1

是否存在不包含最大加权边的G的MST？

可能有,但没有必要.考虑如下的4顶点图:

[A]--{2}--[B]
 |         |
 |         |
{1}       {3}
 |         |
 |         |
[C]-{50}--[D]

最小生成树由边集{CA,AB,BD}组成.沿着{CD},最大边缘权重为50,但它不是MST的一部分.但如果G已经等于它自己的MST,那么显然它会包含它自己的最大边缘.

G的每个MST都包含最小加权边？

是.MST具有切割属性.甲切仅仅是图的顶点的一个分区成两个不相交的集合.对于任何可以进行的切割,如果切割中边缘的权重小于切割中其他边缘的权重,则此边缘属于图形中的所有MST.因为您保证边缘权重是不同的,所以您还保证边缘小于所有其他边缘.

另外,如果有人能够提供一些在处理此类MST问题时必须记住的关键事项,我会更感谢.

您最好的选择是使用MST的属性进行推理,并尝试构建您认为可以证明您的情况的特定反例.我给出了上面每行推理的一个例子.由于切割和循环属性,您始终可以确切地确定MST中的哪些边缘,因此您可以系统地测试每个边缘以确定它是否在MST中.

Answer 2

G的每个MST是否包含最小加权边？

是。假设我们有一个MST不包含最小权重边的。现在，将此边缘包括在内MST将导致cycle。现在将始终存在另一个边cycle，可以删除该边以删除循环并仍然保持graph（MST）连接。

G的MST是否不包含最大加权边？

取决于图形。如果其graph本身是一棵树，则需要将其所有n-1边缘都包括在中MST，因此不能排除最大权重边缘。同样，如果最大权重边为a cut-edge，则将其排除将永远不会导致连通性，则不能排除最大权重边。但是，如果最大重量边缘是的一部分，cycle则可以从中排除MST。