欧阳体创编 2021.02.03 欧阳美创编 2021.02.03
离散数学图论部分综合练习
时间：2021.02.03 创作：欧阳体 1．设图G＝
v?VE B．deg(V)=
E
v?VE
a ? b ?
? f
?e
C．?deg(v)?2E D．?deg(v)?d?
? c
图一
2．图G如图一所示，以下说法正确的是 ( ) ． A．{(a, d)}是割边 B．{(a, d)}是边割集 C．{(d, e)}是边割集 D．{(a, d) ,(a, c)}是边割集
3．如图二所示，以下说法正确的是 ( )． A．e是割点 B．{a,e}是点割集
C．{b, e}是点割集 D．{d}是点割集
4．如图三所示，以下说法正确的是 ( )． 图二
A．{(a, e)}是割边 B．{(a, e)}是边割集 C．{(a, e) ,(b, c)}是边割集 D．{(d, e)}是边割集 图三
5．设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是 ( )．
图四
A．（a）是强连通的 B．（b）是强连通的
C．（c）是强连通的D．（d）是强连通的
6．设完全图Kn有n个结点(n≥2)，m条边，当（ ）时，Kn中存在欧拉回路．
A．m为奇数 B．n为偶数 C．n为奇数 D．m为偶数
7．设G是连通平面图，有v个结点，e条边，r个面，则r= ( )．
A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2
欧阳体创编 2021.02.03 欧阳美创编 2021.02.03
欧阳体创编 2021.02.03 欧阳美创编 2021.02.03
8．无向图G存在欧拉通路，当且仅当( )． A．G中所有结点的度数全为偶数 B．G中至多有两个奇数度结点 C．G连通且所有结点的度数全为偶数 D．G连通且至多有两个奇数度结点
9．设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树．
A．m?n?1B．m?nC．m?n?1D．n?m?1
10．无向简单图G是棵树，当且仅当( )．
A．G连通且边数比结点数少1 B．G连通且结点数比边数少1
C．G的边数比结点数少1 D．G中没有回路． 二、填空题 1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是．
2．设给定图G(如图四所示)，则图G的点割b a 集是．
?
?
3．若图G=
e d
数|S|与W满足的关系式为．
图四
4．无向图G存在欧拉回路，当且仅当G连通 且．
5．设有向图D为欧拉图，则图D中每个结点的入度．
6．设完全图Kn有n个结点(n2)，m条边，当时，Kn中存在欧拉回路．
7．设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式．
8．设连通平面图G的结点数为5，边数为6，则面数为． 9．结点数v与边数e满足关系的无向连通图就是树．
10．设图G是有6个结点的连通图，结点的总度数为18，
欧阳体创编 2021.02.03 欧阳美创编 2021.02.03
欧阳体创编 2021.02.03 欧阳美创编 2021.02.03
则可从G中删去
条边后使之变成树．
11．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 ．
12．设G＝
13．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素，则该序列集合构成前缀码．
三、判断说明题
1．如图六所示的图G存在一条欧拉回路．
v4 d 2．给定两个图G1，gG（如图七所示）： e 2v1 n c （1）试判断它们是否为欧拉图、汉密尔顿图？并说明理f h a 由． v3 b v2 v5 图六 （2）若是欧拉图，请写出一条欧拉回路．
v1
v6
v5
v4
v2
v3
v1
? G(如图八所示)是不是平面图， v6 ? ? v5
v2 ? ? v3
? v4
图八
图七
3．判别图并说明理由．
4．设G是一个有6个结点14条边的连 通图，则G为平面图．
四、计算题
1．设图G
E
a5,a2
V，Ea1,a2
，其中V，
a2,a4
a1,a2,a3,a4,a5，
a3,a1
，
, a4,a5
，
（1）试给出G的图形表示；
（2）判断图G是强连通图、单侧连通图还是弱连通图？
欧阳体创编 2021.02.03 欧阳美创编 2021.02.03
离散数学图论部分综合练习之欧阳体创编
