图其中Vabcdef，Eabacaebdbecededfef，对应边的权值依次为5，2，1，2，6，1，9，3及8．1画出G的图形；2写出G的邻接矩阵；
5
f★形成性考核作业★
3求出G权最小的生成树及其权值．
011解：2G010
110100011000010100111010100110
3最小生成树是aeecbddf权值为
3．已知带权图G如右图所示．1求图G的最小生成树；2计算该生成树的权值．
解：1最小生成树为1432752权值为22
4．设有一组权为23571731，试画出相应的最优二叉树，计算该最优二叉树的权．
6
f★形成性考核作业★
解：1图画在材料纸上2由图得到最优二叉树的权为：65
五、证明题证明题1．设G是一个
阶无向简单图，
是大于等于3的奇数．证明图G与它的补图G中的奇数度顶点个数相等．证明：因为G是
阶无向简单图，且
是大于等于3的奇数，故无向图的结点数为奇数，又对于任何图有奇数度数和偶数度数之和是结点数的2倍，故G图的度数为偶数，故G中需要的是奇数的结点，偶数度数，故G和G的奇数度数相同，顶点个数也是相同的。即证。
2．设连通图G有k个奇数度的结点，证明在图G中至少要添加使其成为欧拉图．
k条边才能2
证明：由于是连通图并且有k个奇数度的结点，根据定理“在任何图中，度数奇数的结点必定是偶数个”得到，G图中的结点数为偶数个；又连通图G要形成欧拉图，必须是结点数为偶数的；又有结点度数的总k和是边数的2倍，则边数E最少要达到E，综上所属成立，即证。2
7
fr