离散数学期末复习辅导（二）
解 这棵无向树T有7条边，所有结点的度数之和为14，而4度、3度、2度的分支点各一个共3个结点占用了9度，所以剩下的5个结点占用5度，即这5个结点每个都是1度结点，故有5片树叶． 答 B
15．设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树．
A．m?n?1 B．m?n C．m?n?1 D．n?m?1
答 A（n个结点的连通图的生成树有n?1条边，必须删去m?(n?1)条边）
16．设无向图G的邻接矩阵为
?0?1??1??1??11111?0011??， 0000??1001?1010??则G的边数为( )．
A．1 B．6 C．7 D．14
17．如图二（下图）所示，以下说法正确的是 ( )． A．e是割点 B．{a, e}是点割集 C．{b, e}是点割集 D．{d}是点割集
答 C
图二
答 A
6
离散数学期末复习辅导（二）
18．设有向图（a）、（b）、（c）与（d）如图六（下图）所示，则下列结论成立的是( )．
图六
A．（a）只是弱连通的 B．（b）只是弱连通的 C．（c）只是弱连通的 D．（d）只是弱连通的
19．无向完全图K4是（ ）．
A．欧拉图 B．汉密尔顿图 C．非平面图 D．树
20．以下结论正确的是( )． A．无向完全图都是欧拉图
B．有n个结点n－1条边的无向图都是树 C．无向完全图都是平面图 D．树的每条边都是割边
二、填空题
1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 ． 解 设G有x条边，则由握手定理，
1?1?2?2?3?3?4?4?2x，x?15
答 D
答 B
答 D
答 15
2．设给定图G(如右由图所示)，则图G的点割集是 ．
解 从图G中删除结点f，得到的子图是不连通图，即结点集{f}是点割集；从图G中删除结点c和e，
得到的子图是不连通图，而只删除c或e，得到的子图仍然是连通的，所以结点集{c,
7
离散数学期末复习辅导（二）
e}也是点割集．而其他结点集都不满足点割集的定义的集合，所以应该填写：{f}、{c, e}
答 {f}、{c,e}
提示：若f是图G的割点，则{f}是图G的点割集，删除f点后图G是连通吗？
3．设G是一个图，结点集合为V，边集合为E，则G的结点 等于边数的两倍． 答 的度数之和
4．无向图G存在欧拉回路，当且仅当G连通且 ． 答 G的结点度数都是偶数（定理4.1.1的推论）
5．设G=
6．若图G=
7．设完全图Kn有n个结点(n?2)，m条边，当 时，Kn中存在欧拉回路． 答 n为奇数（同一、8题）
8．结点数v与边数e满足 关系的无向连通图就是树． 答 e?v?1（定理5.1.1（树的等价定义））
9．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 条边后使之变成树．
解 由握手定理（定理3.1.1）知道图G有18?2=9 条边，又由定理5.1.1中给出的图T
8
离散数学期末复习辅导（二）
为树的等价定义之一是“图T连通且e=v-1”，可以知道图G的生成树有5条边，从而要删去4条边． 答 4
10．设正则5叉树的树叶数为17，则分支数为i = ．答 4（定理5.2.1：(m-1)i=t-1）
三、判断说明题（判断下列各题，并说明理由．）
1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路． 解 错误．
只有当G是连通图且其结点度数均为偶数时，图G才存在一条欧拉回路．
2．如下图所示的图G存在一条欧拉回路．
解 错误．
因为图G有两个奇数度（3度）结点，所以不存在欧拉回路．
注：这是一个汉密尔顿图，但不是欧拉图。可见汉密尔顿图不一定是欧拉图． 其实，欧拉图也不一定是汉密尔顿图．
如下图所示，图（1）是欧拉图又是汉密尔顿图，图（2）是欧拉图但不是汉密尔顿图，图（3）不是欧拉图但它是汉密尔顿图，图（4）不是欧拉图也不是汉密尔顿图。
9
离散数学期末复习辅导（二）
3．如下图所示的图G不是欧拉图而是汉密尔顿图．
图G
解 正确．
图G有4个3度结点a，b，d，f，所以图G不是欧拉图．图G有汉密尔顿回路abefgdca，所以图G是汉密尔顿图．
4．设G是一个有7个结点16条边的连通简单图，则G为平面图． 解 错误．
由定理4.3.3知，若G有v个结点e条边，且v?3，则e≤3v?6．但本题中，16≤3×7?6不成立．
5．设G是一个连通平面图，且有6个结点11条边，则G有7个面． 解 正确．
由欧拉定理，连通平面图G的结点数为v，边数为e，面数为r，则v?e+r=2．于是有r=2?v+e=2?6+11=7．
问：“完全图K6是平面图”是否正确？ 答 不正确．
因为完全图K6有6个结点15条边，且15?3?6-6=12，即e ? 3v-6对K6不成立，所以K6不是平面图．
10