任何一个无向连通图有几棵最小生成树

2026年09月25日 14:23
有1个网友回答
网友(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边数最少的无向连通图,故必有树