边数为e，应满足e3v6，但现在16376，
显然不成立，所以假设错误。
f5．设G是一个连通平面图，且有6个结点11条边，则G有7个面．
对。根据欧拉定理，有ver2，结点数v11，边数e6，代入公式求出面数r7。
三、计算题
1．设GV，E，Vv1，v2，v3，v4，v5，Ev1v3，v2v3，v2v4，v3v4，v3v5，v4v5，
试
1给出G的图形表示；
2写出其邻接矩阵；
3求出每个结点的度数；
4画出其补图的图形．
v1
00100
00110
1v2
v5
2

1
1
0
1
1
01101
3
v1，v2v，3v3，v4，vv51结v点4的度数依次为

0
1，2，4，3，2。
0
1
1
0
4

d
2b．图eGv2Vc
E，其中Vabecddve5
cde，Eabacaeb，对应边的权值依次为2、1、2、3、6、1、4
及5，试
（（3）1）求画出出G权G最的v小3图的形生成；树及v其4权值．
（2）写出G的邻接矩阵；
a

2
1
01101

1
0
0
1
1

1b
2
6
3
4

2c
A1

0
01
01
10
1
1

1
11110
3权值


d
5a
e

WT1212371
3．已知带权图G如右图所示．1求图bG的最小生成树；2计算c该生成树的权值．
1
3
1
1d
2e
75
3
2权值12357184．设有一组权为23571731，试画出相应的最优二叉树，计算该最优二叉树的权．
f65
3
31
4
1
17
7
1
7
0
5
5
2
3
权为2535547317231131四、证明题
1．设G是一个
阶无向简单图，
是大于等于3的奇数．证明图G与它的补图G中的奇数度顶点
个数相等．
证明：设GVE，GVE．则E是由
阶无向完全图K
的边删去E所得到的．所以对
于任意结点uV，u在G和G中的度数之和等于u在K
中的度数．由于
是大于等于3的奇数，从
而K
的每个结点都是偶数度的（
12度），于是若uV在G中是奇数度结点，则它在G中
也是奇数度结点．故图G与它的补图G中的奇数度结点个数相等．2．设连通图G有k个奇数度的结点，证明在图G中至少要添加k条边才能使其成为欧拉图．2
证明：由定理312，任何图中度数为奇数的结点必是偶数，可知k是偶数．又根据定理411的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图．
故最少要加k条边到图G才能使其成为欧拉图．2
fr