资源描述：
《离散数学图论部分综合练习》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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．
2、deg(V)=2½E½B．deg(V)=½E½C．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）
3、与（d）如图四所示，则下列结论成立的是()．图四A．（a）是强连通的B．（b）是强连通的C．（c）是强连通的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
4、连通且至多有两个奇数度结点11．设G是有n个结点，m条边的连通图，必须删去G的()条边，才能确定G的一棵生成树．A．B．C．D．12．无向简单图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，
5、在G中删除S中的所有结点得到的连通分支数为W，则S中结点数
6、S
7、与W满足的关系式为．4．无向图G存在欧拉回路，当且仅当G连通且．5．设有向图D为欧拉图，则图D中每个结点的入度 ．应该填写：等于出度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，则可从
8、G中删去条边后使之变成树．11．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为．12．设G＝是有6个结点，8条边的连通图，则从G中删去条边，可以确定图G的一棵生成树．13．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素，则该序列集合构成前缀码．三、判断说明题1．如图六所示的图G存在一条欧拉回路．v1v2v3v5v4dbacefghn图六2．给定两个图G1，G2（如图七所示）：（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由．（2）若是欧拉图，请写出一
9、条欧拉回路．9v1v2v3v4v5v6ooooov5v1v2v4v6ov3图八图七3．判别图G(如图八所示)是不是平面图，并说明理由．4．设G是一个有6个结点14条边的连通图，则G为平面图．四、计算题1．设图G=，其中V={a1,a2,a3,a4,a5},E={，，，，}（1）试给出G的图形表示；（2）求G的邻接矩阵；（3）判断图G是强连通图、单侧连通图还是弱连通图？2．设图G=，V={v1，v2，v3，v4，v5}，E={
10、(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,v4)，(v3,v5)，(v4,v5
