离散数学图论练习题Word格式文档下载.doc
- 文档编号:7611004
- 上传时间:2023-05-08
- 格式:DOC
- 页数:4
- 大小:111KB
离散数学图论练习题Word格式文档下载.doc
《离散数学图论练习题Word格式文档下载.doc》由会员分享,可在线阅读,更多相关《离散数学图论练习题Word格式文档下载.doc(4页珍藏版)》请在冰点文库上搜索。
7、一个图的欧拉回路是一条通过图中()的回路。
8、有n个结点的树,其结点度数之和是( )。
9、下面给出的集合中,哪一个不是前缀码()。
(1){a,ab,110,a1b11}
(2){01,001,000,1}
(3){1,2,00,01,0210}(4){12,11,101,002,0011}
10、n个结点的有向完全图边数是(),每个结点的度数是()。
11、一个无向图有生成树的充分必要条件是()。
12、设G是一棵树,n,m分别表示顶点数和边数,则
(1)n=m
(2)m=n+1(3)n=m+1(4)不能确定。
13、设T=〈V,E〉是一棵树,若|V|>
1,则T中至少存在()片树叶。
14、任何连通无向图G至少有()棵生成树,当且仅当G是(),G的生成树只有一棵。
15、设G是有n个结点m条边的连通平面图,且有k个面,则k等于:
(1)m-n+2
(2)n-m-2(3)n+m-2(4)m+n+2。
16、设T是一棵树,则T是一个连通且()图。
17、设无向图G有16条边且每个顶点的度数都是2,则图G有()个顶点。
(1)10
(2)4(3)8(4)16
18、设无向图G有18条边且每个顶点的度数都是3,则图G有()个顶点。
(1)10
(2)4(3)8(4)12
19、任一有向图中,度数为奇数的结点有( )个。
20、具有6个顶点,12条边的连通简单平面图中,每个面都是由( )条边围成?
(1)2
(2)4 (3)3 (4)5
21、在有n个顶点的连通图中,其边数()。
(1)最多有n-1条
(2)至少有n-1条
(3)最多有n条 (4)至少有n条
22、一棵树有2个2度顶点,1个3度顶点,3个4度顶点,则其1度顶点为()。
(1)5
(2)7(3)8 (4)9
23、若一棵完全二元(叉)树有2n-1个顶点,则它()片树叶。
(1)n
(2)2n(3)n-1 (4)2
24、下列哪一种图不一定是树()。
(1)无简单回路的连通图
(2)有n个顶点n-1条边的连通图
(3)每对顶点间都有通路的图 (4)连通但删去一条边便不连通的图
25、连通图G是一棵树当且仅当G中()。
(1)有些边是割边
(2)每条边都是割边
(3)所有边都不是割边 (4)图中存在一条欧拉路径
26.对于无向图,下列说法中()是正确的.
A.不含平行边及环的图称为完全图
B.任何两个不同结点都有边相连且无平行边及环的图称为完全图
C.具有经过每条边一次且仅一次回路的图称为哈密尔顿图
D.具有经过每个结点一次且仅一次回路的图称为欧拉图
27.设图G的邻接矩阵为
则G的边数为().
A.5B.6C.3D.4
28.设图G=<
V,E>
,则下列结论成立的是().
A.deg(V)=2½
E½
B.deg(V)=½
C.D.
29.图G如右图所示,以下说法正确的是().
A.{(a,d)}是割边
B.{(a,d)}是边割集
o
c
a
b
e
d
f
C.{(d,e)}是边割集
D.{(a,d),(a,c)}是边割集
30.设G是连通平面图,有v个结点,e条边,r个面,则r=().
A.e-v+2B.v+e-2C.e-v-2D.e+v+2
31.无向图G存在欧拉通路,当且仅当().
A.G中所有结点的度数全为偶数
B.G中至多有两个奇数度结点
C.G连通且所有结点的度数全为偶数
D.G连通且至多有两个奇数度结点
二、填空题
1.已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G的边数是.
2.设给定图G(如右图所示),则图G的点割集是
.
3.设无向图G=<
是汉密尔顿图,则V的任意非空子集V1,都有
£
½
V1½
.
4.设有向图D为欧拉图,则图D中每个结点的入度 .
5.设完全图K有n个结点(n³
2),m条边,当时,K中存在欧拉回路.
6.给定一个序列集合{1,01,10,11,001,000},若去掉其中的元素,则该序列集合构成前缀码.
三、计算题
1.设图G=<
V,E>
,其中V={a1,a2,a3,a4,a5},
E={<
a1,a2>
,<
a2,a4>
a3,a1>
a4,a5>
a5,a2>
}
(1)试给出G的图形表示;
(2)求G的邻接矩阵;
(3)判断图G是强连通图、单侧连通图还是弱连通图?
2.图G=<
,其中V={a,b,c,d,e,f},E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(d,e),(d,f),(e,f)},对应边的权值依次为5,2,1,2,6,1,9,3及8.
(1)画出G的图形;
1
5
2
6
9
3
8
(2)写出G的邻接矩阵;
(3)求出G权最小的生成树及其权值.
问:
如果结点集是V={a,b,c,d,e},边集E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(d,e)},对应边的权值依次为5,2,1,2,6,1,9,那么会求吗?
3.设有一组权为2,3,5,7,11,13,17,19,23,29,31,试
(1)画出相应的最优二叉树;
7
13
11
17
34
160
29
10
23
19
42
24
53
31
95
65
(2)计算它们的权值.
解:
(1)最优二叉树如右图所示:
如果一组权为2,3,6,9,13,15,能否画出最优二叉树?
4
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 练习题