不同的最小生成树

Question

对于连通的，加权的，无向图G：G具有唯一的MST，如果对于G的每次切割，则存在穿过切口的唯一最小权重边。

这个陈述是真的吗？

我认为是假的，因为对于给定链接中的下图，可以有多个MST。

https://drive.google.com/file/d/1yDK3juPxeDBdS-aEOx0aAsphy4odZ55l/view?usp=drivesdk

Answer 1

如果您指的是连通图G，边缘成本都是不同的。然后G有一个唯一的最小生成树。

证明：假设有两个不同的MST，称为T1和T2，它们具有不同的边缘集 - T1的{t11，t12，... t1n-1}和T2的{t21，t22，... t2n-1}。因此，让ti成为仅在T1（而不是T2）中具有最小权重的边缘。由于它是最小的，因此必须包含在MST的“每个选择”中。也就是说，T1和T2的MST都会拥有它。但这与ti的定义相矛盾。