唯一的最小生成树充分必要的条件 [英] unique minimum spanning tree sufficient and necessary conditions

问题描述

给出图G，这是充分必要的条件，因此该图具有唯一的最小生成树?此外，如何证明这些条件?

Given a graph G,which are the sufficient and necessary conditions , so that this graph has a unique minimum spanning tree?In addition , how can I proove these conditions?

到目前为止，我发现这些条件是:

So far , I had found that those conditions are :

1)对于将V(G)分为两个子集的每个分区，每个子集中具有一个端点的最小权重边是唯一的.

1)For every partition of V(G) into two subsets, the minimum weight edge with one endpoint in each subset is unique.

2)在G的任何循环中，最大重量边都是唯一的.

2)The maximum-weight edge in any cycle of G is unique.

但是我不确定这是否正确.即使万一是正确的，我也无法证明其正确性.

But I am not sure if this is correct.Even in case this is correct,I cannot prove its correctness.

推荐答案

实际上，唯一的MST有必要的充分条件.在图论的第一门课程中，它是作为练习给出的:

Actually, there is a necessary and sufficient condition for unique MST. In the book A First Course In Graph Theory, it is given as an exercise:

锻炼4.30

让G为一个连通加权图，T为G的最小生成树.证明且仅当当不在T中的G的每个边e的权重超过权重时，T才是G的唯一最小生成树.T + e中周期的每个其他边的数量.

Let G be a connected weighted graph and T a minimal spanning tree of G. Show that T is a unique minimal spanning tree of G if and only if the weight of each edge e of G that is not in T exceeds the weight of every other edge on the cycle in T+e.

我写我的证明 查看全文