离散数学图论部分综合练习

离散数学图论部分综合练习

ID:18787348

大小:855.00 KB

页数:9页

时间:2018-09-23

离散数学图论部分综合练习_第1页
离散数学图论部分综合练习_第2页
离散数学图论部分综合练习_第3页
离散数学图论部分综合练习_第4页
离散数学图论部分综合练习_第5页
资源描述:

《离散数学图论部分综合练习》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、离散数学图论部分综合练习本课程综合练习共分3次,分别是集合论部分、图论部分、数理逻辑部分的综合练习,这3次综合练习基本上是按照考试的题型安排练习题目,目的是通过综合练习,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次是图论部分的综合练习。一、单项选择题1.设图G的邻接矩阵为则G的边数为().A.6B.5C.4D.32.已知图G的邻接矩阵为,则G有().A.5点,8边B.6点,7边C.6点,8边D.5点,7边ooooocabedof图一3.设图G=,则下列结论成立的是().A.deg(V)=2½E½B.deg(V)=½E½C

2、.D.4.图G如图一所示,以下说法正确的是().A.{(a,d)}是割边B.{(a,d)}是边割集图二C.{(d,e)}是边割集D.{(a,d),(a,c)}是边割集5.如图二所示,以下说法正确的是().A.e是割点B.{a,e}是点割集C.{b,e}是点割集D.{d}是点割集6.如图三所示,以下说法正确的是().9A.{(a,e)}是割边B.{(a,e)}是边割集C.{(a,e),(b,c)}是边割集D.{(d,e)}是边割集图三7.设有向图(a)、(b)、(c)与(d)如图四所示,则下列结论成立的是().图四A.(a)是强连通的B.(b)是强连通的C.(c

3、)是强连通的D.(d)是强连通的应该填写:D8.设完全图K有n个结点(n≥2),m条边,当()时,K中存在欧拉回路.A.m为奇数B.n为偶数C.n为奇数D.m为偶数9.设G是连通平面图,有v个结点,e条边,r个面,则r=().A.e-v+2B.v+e-2C.e-v-2D.e+v+210.无向图G存在欧拉通路,当且仅当().A.G中所有结点的度数全为偶数B.G中至多有两个奇数度结点C.G连通且所有结点的度数全为偶数D.G连通且至多有两个奇数度结点11.设G是有n个结点,m条边的连通图,必须删去G的()条边,才能确定G的一棵生成树.A.B.C.D.12.无向简单图

4、G是棵树,当且仅当().A.G连通且边数比结点数少1B.G连通且结点数比边数少1C.G的边数比结点数少1D.G中没有回路.二、填空题1.已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G的边数是.9ooooocabedof图四2.设给定图G(如图四所示),则图G的点割集是.3.若图G=中具有一条汉密尔顿回路,则对于结点集V的每个非空子集S,在G中删除S中的所有结点得到的连通分支数为W,则S中结点数

5、S

6、与W满足的关系式为.4.无向图G存在欧拉回路,当且仅当G连通且.5.设有向图D为欧拉图,则图D中每个结点的入度   .应该填写:

7、等于出度6.设完全图K有n个结点(n³2),m条边,当时,K中存在欧拉回路.7.设G是连通平面图,v,e,r分别表示G的结点数,边数和面数,则v,e和r满足的关系式.8.设连通平面图G的结点数为5,边数为6,则面数为.9.结点数v与边数e满足关系的无向连通图就是树.10.设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去条边后使之变成树.11.已知一棵无向树T中有8个结点,4度,3度,2度的分支点各一个,T的树叶数为.12.设G=是有6个结点,8条边的连通图,则从G中删去条边,可以确定图G的一棵生成树.13.给定一个序列集合{000,00

8、1,01,10,0},若去掉其中的元素,则该序列集合构成前缀码.三、判断说明题1.如图六所示的图G存在一条欧拉回路.v1v2v3v5v4dbacefghn图六2.给定两个图G1,G2(如图七所示):(1)试判断它们是否为欧拉图、汉密尔顿图?并说明理由.(2)若是欧拉图,请写出一条欧拉回路.9v1v2v3v4v5v6ooooov5v1v2v4v6ov3图八图七3.判别图G(如图八所示)是不是平面图,并说明理由.4.设G是一个有6个结点14条边的连通图,则G为平面图.四、计算题1.设图G=,其中V={a1,a2,a3,a4,a5},E={

9、}(1)试给出G的图形表示;(2)求G的邻接矩阵;(3)判断图G是强连通图、单侧连通图还是弱连通图?2.设图G=,V={v1,v2,v3,v4,v5},E={(v1,v2),(v1,v3),(v2,v3),(v2,v4),(v3,v4),(v3,v5),(v4,v5)},试(1)画出G的图形表示;(2)写出其邻接矩阵;(2)求出每个结点的度数;(4)画出图G的补图的图形.3.设G=,V={v1,v2,v3,v4,v5},E={(v1,v3),(v2,v3),(v2,v4),(v3

10、,v4),(v3,v5),(v4,v5

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。