2024国家开放大学离散数学(本)形考任务答案

.

（3）

其中权值是：7

3．已知带权图G如右图所示．

(1) 求图G的最小生成树； (2)计算该生成树的权值．

答：（1）

.

.

（2） 权值：18

4．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．

权值：65

四、证明题

1．设G是一个n阶无向简单图，n是大于等于3的奇数．证明图G与它的补图G中的奇数度顶点个数相等．

.

.

证明：设a为G中任意一个奇数度顶点，由定义，a仍为顶点，为区分起见，记为a’, 则deg(a)+deg(a’)=n-1, 而n为奇数，则a’必为奇数度顶点。由a的任意性，容易得知结论成立。

2．设连通图G有k个奇数度的结点，证明在图G中至少要添加使其成为欧拉图．

证明：由定理推论知：在任何图中，度数为奇数的结点必是偶数个，则k是偶数。又由欧拉图的充要条件是图G中不含奇数度结点。因此，只要在每对奇数度结点间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图。故最少要加条边才能使其成为欧拉图。

k条边才能2.