图．答：错误。若G是连通平面图，那么若vG≥3就有e≤3v－6，而163×7－6，所以
不满足定理条件，叙述错误。
5．设G是一个连通平面图，且有6个结点11条边，则G有7个面．
答：正确。因为连通平面图满足欧拉公式。即：ver2。由此题条件知61172成立。
三、计算题
1．设GV，E，Vv1，v2，v3，v4，v5，Ev1v3，v2v3，v2v4，v3v4，v3v5，
v4v5，试
1给出G的图形表示；
2写出其邻接矩阵；
3求出每个结点的度数；答：（1）
4画出其补图的图形．
（2）
（3）degv11degv22、degv34、degv43、degv52
（4）
2．图GVE，其中Vabcde，Eabacaebdb
ececdde，对应边的权值依次为2、1、2、3、6、1、4及5，试
（1）画出G的图形；
（2）写出G的邻接矩阵；
（3）求出G权最小的生成树及其权值．
解：（1）
（2）
（3）G权最小的生成树的权值：11237
3．已知带权图G如右图所示．
1求图G的最小生成树；2计算该生成树的权值．
答：（1）
（2）该生成树的权值为1235718
4．设有一组权为23571731，试画出相应的最优二叉树，计算该最优二叉树
的权．
答：最优二叉树如下：
解：从23571731中选2，3为最低层结点，并从权数中删去再添上它们的和数，
即5，5，7，11，31再从5，5，7，11，31选5，5为倒数第二层结点，并从上述数列中删去，再添上它们的和数，即17，17，31…
f最优二叉树的权为：2×53×54×57×317×231×1101520213431131
四、证明题
1．设G是一个
阶无向简单图，
是大于等于3的奇数．证明图G与它的补图G中的奇数度顶点个数相等．
证明：设a为G中任意一个奇数度顶点，由G定义，a仍为G顶点，为区分起见，记为a’则degadega’
1而
为奇数，则a’必为奇数度顶点。由a的任意性，容易得知结论成立。
k2．设连通图G有k个奇数度的结点，证明在图G中至少要添加2条边才能使其成为欧拉图．证明：由定理推论知：在任何图中，度数为奇数的结点必是偶数个，则k是偶数。又由欧拉图的充要条件是图G中不含奇数度结点。因此，只要在每对奇数度结点间各加一条
k边，使图G的所有结点的度数变为偶数，成为欧拉图。故最少要加2条边才能使其成为欧拉图
fr