欧阳体创编 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
离散数学图论部分综合练习之欧阳体创编
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)