．设G是一个连通平面图，且有6个结点11条边，则G有7个面．答：对。因为61172符合欧拉定理ver2。
三、计算题1．设GV，E，Vv1，v2，v3，v4，v5，Ev1v3，v2v3，v2v4，v3v4，v3v5，v4v5，试1给出G的图形表示；2写出其邻接矩阵；3求出每个结点的度数；4画出其补图的图形．答：（1）：
3
f★形成性考核作业★
（2）邻接矩阵为：
（3）degv11degv22degv34degv43degv524图G的补图为
2．图GVE，其中Vabcde，Eabacaebdbececdde，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G的图形；（2）写出G的邻接矩阵；
4
f★形成性考核作业★
（3）求出G权最小的生成树及其权值．答（1）：
（2）：
（3）最小生成树：
权WG11237
3．已知带权图G如右图所示．1求图G的最小生成树；解答2计算该生成树的权值．
5
f★形成性考核作业★
1最小生成树
2权WG5123718
4．设有一组权为23571731，试画出相应的最优二叉树，计算该最优二叉树的权．解答最优二叉树
权WT25355473172311131
6
f★形成性考核作业★
四、证明题1．设G是一个
阶无向简单图，
是大于等于3的奇数．证明图G与它的补图G中的奇数度顶点个数相等．证明：因为
是奇数，即
阶完全图每个顶点度数为偶数．那么，若G中顶点v的度数为奇数时，在补图G中v的度数一定也是奇数，所以G与G中的奇数度顶点个数相等．
2．设连通图G有k个奇数度的结点，证明在图G中至少要添加使其成为欧拉图．
k条边才能2
证明：由定理312，任何图中度数为奇数的结点必是偶数，可知k是偶数．又根据定理411的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图．k故最少要加条边到图G才能使其成为欧拉图．2
7
fr