Question

任何一个无向连通图的最小生成树为什么有一棵或多棵呢?

Answer 1

1.可以有多棵最小生成树

例如图(i-j k :点i到j间有边且权为k)

1-2 1

2-3 1

1-3 1

选边1-2,2-3是边权和为2的最小生成树

选边1-3,2-3也是边权和为2的最小生成树

2.树是E=V-1边数最少的无向连通图,故必有树