离散数学第二次作业Word文档下载推荐.docx
- 文档编号:6427689
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:11
- 大小:91.06KB
离散数学第二次作业Word文档下载推荐.docx
《离散数学第二次作业Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《离散数学第二次作业Word文档下载推荐.docx(11页珍藏版)》请在冰点文库上搜索。
(3)最多有n条(4)至少有n条
9、如右图
相对于完全图K5的补图为()。
10、给定无向图G如下图所示,下面给出的结点集子集中,不是点割集的为().
A.{b,d}B.{d}
C.{a,c}D.{b,e}
11、图G如右图所示,以下说法正确的是().
A.{(a,c)}是割边
B.{(a,c)}是边割集
C.{(b,c)}是边割集
D.{(a,c),(b,c)}是边割集
12、给定无向图G=<
V,E>
如下图所示,下面哪个边集不是其边割集()。
A、
;
B、{<
v1,v4>
<
v4,v6>
};
C、
D、
。
13、设有向图(a)、(b)、(c)与(d)如下图所示,则下列结论成立的是().
A.(a)是强连通的B.(b)是强连通的
C.(c)是强连通的D.(d)是强连通的
14、下图的邻接矩阵A=
15、设无向图G的邻接矩阵为
,则G的边数为().
A.5B.6C.3D.4
16、图的邻接矩阵为()。
B、
综合题
17、设G=<
V,E>
,V={v1,v2,v3,v4,v5},E={(v1,v3),(v2,v3),(v2,v4),(v3,v4),(v3,v5),(v4,v5)},试
(1)给出G的图形表示;
(2)写出其邻接矩阵;
(3)求出每个结点的度数;
(4)画出其补图的图形.
18、已知:
D=<
V,E>
,V={1,2,3,4,5},E={<
1,2>
1,4>
2,3>
3,4>
3,5>
5,1>
},求D的邻接距阵A和可达距阵P。
19、无向图G有12条边,G中有6个3度结点,其余结点的度数均小于3,问G中至少有多少个结点?
20、有向图
如右图所示。
(1)求
的邻接矩阵
(2)
中
到
长度为4的路径有几条?
(3)
到自身长度为3的回路有几条?
(4)
是哪类连通图?
21、设图
如图1所示,
(1)求
(2)求
,说明从
的长为
的路径各有几条;
(3)求
的可达矩阵
(4)求
的强连通分图。
22、设有如下有向图G=<
,
(1)求G的邻接矩阵;
(2)G中v1到v4的长度为4的通路有多少条?
(3)G中经过v1的长度为3的回路有多少条?
(4)G中长度不超过4的通路有多少条?
其中有多少条通路?
二、二部图、欧拉图、哈密顿图
23、无向图G存在欧拉通路,当且仅当().
A.G中所有结点的度数全为偶数
B.G中至多有两个奇数度结点
C.G连通且所有结点的度数全为偶数
D.G连通且至多有两个奇数度结点
24、无向图G是欧拉图,当且仅当()
(A)G的所有结点的度数都是偶数(B)G的所有结点的度数都是奇数
(C)G连通且所有结点的度数都是偶数(D)G连通且G的所有结点度数都是奇数。
25、当n为时,非平凡无向完全图Kn是欧拉图。
26、下列图中是欧拉图的有()。
27、下图中既不是Eular图,也不是Hamilton图的图是()
28、在如下各图中()是欧拉图。
29、若一个有向图
是欧拉图,它是否一定是强连通的?
若一个有向图
是强连通的,它是否一定是欧拉图?
说明理由。
30、一次学术会议的理事会共有20个人参加,他们之间有的相互认识但有的相互不认识。
但对任意两个人,他们各自认识的人的数目之和不小于20。
问能否把这20个人排在圆桌旁,使得任意一个人认识其旁边的两个人?
根据是什么?
三、树及应用
31、设G是有n个结点,m条边的连通图,必须删去G的()条边,才能确定G的一棵生成树.
A.
B.
C.
D.
32、已知一棵无向树T中有8个结点,4度,3度,2度的分支点各一个,T的树叶数为().
A.8B.5C.4D.3
33、连通无向图G有6个顶点9条边,从G中删去条边才有可能得到G的一棵生成树T.
34、已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,
则T中有个1度顶点。
35、一棵树有2个2度顶点,1个3度顶点,3个4度顶点,则其1度顶点为()。
(1)5
(2)7(3)8(4)9
36、一棵无向树的顶点数n与边数m关系是。
37、有n个结点的树,其结点度数之和是。
38、设G是一棵树,n,m分别表示顶点数和边数,则()
(1)n=m
(2)m=n+1(3)n=m+1(4)不能确定。
39、任何连通无向图G至少有棵生成树。
40、下面给出的集合中,哪一个不是前缀码()。
(1){a,ab,110,a1b11}
(2){01,001,000,1}
(3){1,2,00,01,0210}(4){12,11,101,002,0011}
41、下面给出的集合中,哪一个是前缀码?
()
(1){0,10,110,101111}
(2){01,001,000,1}
(3){b,c,aa,ab,aba}(4){1,11,101,001,0011}
42、图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的图形;
(2)写出G的邻接矩阵;
(3)求出G权最小的生成树及其权值.
43、已知带权图G如右图所示.
(1)求图G的最小生成树;
(2)计算该生成树的权值.
44、如下图所示的赋权图表示某七个城市
及预先算出它们之间的一些直接通信成路造价(单位:
万元),试给出一个设计方案,使得各城市之间既能够通信又使总造价最小。
45、设带权无向图G如下,求G的最小生成树T及T的权总和,要求写出解的过程。
46、求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。
47、在通讯中,八进制数字出现的频率如下:
0:
30%、1:
20%、2:
15%、3:
10%、4:
10%、5:
5%、6:
5%、7:
5%
求传输它们最佳前缀码(写出求解过程)。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 第二次 作业