06任务
讨论主题 树的性质及最小生成树的算法实时讨论 讨论内容
06任务答案
1. 解：因为要使有 6 个结点的连通图 G成为一棵生成树，只能保留6－1=5条边，所以从图 G 中删去8－5=3条边后可以确定图 G的一棵生成树。
2. 解：设有x片树叶，则阶数n=2+4+x=6+ x，边数m=5+ x，利用握手定理得： 2m=2×2+4×3+ x×1，2（5+ x）=16+ x，解得：x=6，所以应该有6片树叶。
3. 解：第一次取边ab=1；第二次取边ef=3；第三次取边af=4；第四次取边ad=9；第五次取边bc=23；由这5条边组成最小生成树。
4.（1）B
（2）解：第一次取边ab=1；第二次取边ac=2；第三次取边be=2；第四次取边bd=4；由这4条边组成最小生成树。其权值为：1+2+2+4=9。
