离散数学测验题图论部分优选.docx
- 文档编号:11880699
- 上传时间:2023-06-03
- 格式:DOCX
- 页数:19
- 大小:115.29KB
离散数学测验题图论部分优选.docx
《离散数学测验题图论部分优选.docx》由会员分享,可在线阅读,更多相关《离散数学测验题图论部分优选.docx(19页珍藏版)》请在冰点文库上搜索。
离散数学测验题图论部分优选
离散数学图论单元测验题
一、单项选择题(本大题共10小题,每小题2分,共20分)
1、在图G=
(A)deg(vi)=2∣E∣(B)deg(vi)=∣E∣(C)
(D)
2、设D是n个结点的无向简单完全图,则图D的边数为()
(A)n(n-1)(B)n(n+1)(C)n(n-1)/2(D)n(n+1)/2
3、设G=
(A)∆(G)
4、图G与G'的结点和边分别存在一一对应关系,是G≌G'(同构)的()
(A)充分条件(B)必要条件(C)充分必要条件(D)既非充分也非必要条件
5、设
,则与V能构成强连通图的边集合是()
(A)
(B)
(C)
6、有向图的邻接矩阵中,行元素之和是对应结点的(),列元素之和是对应结点的()
(A)度数(B)出度(C)最大度数(D)入度
7、设图G的邻接矩阵为
则G的边数为().
A.5B.6C.3D.4
8、设
为连通平面图且有r个面,则r=()
(A)m-n+2(B)n-m-2(C)n+m-2(D)m+n+2
9、在5个结点的二元完全树中,若有4条边,则有()片树叶。
(A)2(B)3(C)5(D)4
10、图2是()
(A)完全图(B)欧拉图(C)平面图(D)哈密顿图
二、填空题(本大题共10小题,每题2分,共20分)
1、设图G=
2、设G是完全二叉树,G有15个结点,其中有8个是树叶,则G有条边,G的总度数是,G的分支点数是,G中度数为3的结点数是.
3、一棵树有两个结点度数为2,一个结点度数为3,三个结点度数为4,问它有几个度数为1的结点。
4、画出满足下列条件的图:
(1)画一个有一条欧拉回路和一条哈密顿回路的图;
(2)画一个有一条欧拉回路,但没有哈密顿回路的图;
(3)画一条没有欧拉路,但有一条哈密顿回路的图.
5、设G是n个结点的简单图,若G中每对结点的度数之和,则G一定是哈密顿图.
6、一个有向树T称为根树,若,其中称为树根,
称为树叶.
7、设G是平面图,G有8个面,每个面的度数都是3,则G有__________条边,G有__________个顶点。
8、设G是有n个结点,m条边的连通图,要确定G的一棵生成树,必须删去G的条边.
9、在下图中,哪些是欧拉图?
哪些是哈密顿图?
哪些是平面图?
(6)
(4)
(3)
(5)
(1)
(2)
10、设G是n阶无向带权边连通图,各边的权均为a(a>0),设T是G的一棵最小生成树,则T的权W(T)=________(n-1)*a_______________。
三、计算题(本大题共4小题,每小题10分,共40分)
1、设G=
(1)G=
(2)画出G的图示;
(3)指出与v3邻接的结点,以及与v3关联的边;(4)指出与e1关联的结点;
(5)该图是否有孤立结点和孤立边?
(6)求出各结点的度数;
2、设图G是具有3个顶点的无向完全图,试问
(1)G有多少个子图?
(2)G有多少个生成子图?
(3)如果没有任何两个子图是同构的,则G的子图个数是多少?
将它们构造出来.
3.图G=
(1)画出G的图形;
(2)写出G的邻接矩阵;
(3)求出G权最小的生成树及其权值.
4.设有一组权为2,3,5,7,11,13,17,19,23,29,31,试
(1)画出相应的最优二叉树;
(2)计算它们的权值.
四、证明题(本大题共3小题,任选2题,每小题10分,共20分)
1.若无向图G中只有两个奇数度结点,则这两个结点一定是连通的.
2.设G是一个n阶无向简单图,n是大于等于2的奇数.证明图G与它的补图
中的奇数度顶点个数相等.
3.设连通图G有k个奇数度的结点,证明在图G中至少要添加
条边才能使其成为欧拉图.
补充
1、若图G是不连通的,则G的补图G是连通的。
2、当且仅当G的一条边e不包含在G的回路中时,e才是G的割边。
3、设G是简单平面图,则它—定有一个度数≤5的结点。
解答:
一、单项选择题(本大题共10小题,每小题2分,共20分)
1、在图G=
(A)deg(vi)=2∣E∣(B)deg(vi)=∣E∣(C)
(D)
答案:
(C)
2、设D是n个结点的无向简单完全图,则图D的边数为()
(A)n(n-1)(B)n(n+1)(C)n(n-1)/2(D)n(n+1)/2
答案:
(C)
3、设G=
(A)∆(G)
答案:
(A)
解答:
因为G中无平行边和环,任何结点最多有n-1条边与其相关联,最大度数小于或等于n-1.故选择(A)
4、图G与G'的结点和边分别存在一一对应关系,是G≌G'(同构)的()
(A)充分条件(B)必要条件(C)充分必要条件(D)既非充分也非必要条件
答案:
(B)
解答:
见图的同构定义.
5、设
,则与V能构成强连通图的边集合是()
(D)
(E)
(F)
(G)
答案:
(A)
解答:
有向图G任何一对结点间都互相可达,称该图是强连通的.(A)所给的边的集合存在一个通过所有结点的通路.故选择(A).
6、有向图的邻接矩阵中,行元素之和是对应结点的(),列元素之和是对应结点的()
(A)度数(B)出度(C)最大度数(D)入度
答案:
(B),(D)
解答:
见邻接矩阵的定义.
7、设图G的邻接矩阵为
则G的边数为().
A.5B.6C.3D.4
答案:
(D)
8、设
为连通平面图且有r个面,则r=()
(A)m-n+2(B)n-m-2(C)n+m-2(D)m+n+2
答案:
(A)
解答:
见欧拉公式.
9、在5个结点的二元完全树中,若有4条边,则有()片树叶。
(A)2(B)3(C)5(D)4
答案:
(B)
解答:
二元完全树,即每个结点只有0个或2树枝的树,树根必有2个树枝,于是2个树枝只能其一又有2个树枝,而另一个就无树枝.满足5个结点4条边.可见有3片树叶.选择(B)正确.
10、图2是()
(A)完全图(B)欧拉图(C)平面图(D)哈密顿图
答案:
(D)
解答:
因为n=6,每对结点度数之和
大于或大于6,满足存在哈密顿回路的条
件,故为哈密顿图.选择(D)正确.
二、填空题(本大题共10小题,每题2分,共20分)
1、设图G=
答案:
解答:
见真子图和生成子图的定义.
2、设G是完全二叉树,G有15个结点,
其中有8个是树叶,则G有条边,G的总度数是,G的分支点数是,G中度数为3的结点数是.
答案:
14;28;7;6.
解答:
可画图如图3.有8个树叶,15个结点的完全
3、一棵树有两个结点度数为2,一个结点度数为3,三个结点度数为4,问它有几个度数为1的结点。
解:
设有x个度数为1的结点,结点数v=2+1+3+x=6+x,边数e=v-1=5+x。
而2e=∑deg(vi),故2(5+x)=2·2+1·3+3·4+x·1,x=9。
4、画出满足下列条件的图:
(1)画一个有一条欧拉回路和一条哈密顿回路的图;
(2)画一个有一条欧拉回路,但没有哈密顿回路的图;
(3)画一条没有欧拉路,但有一条哈密顿回路的图.
5、设G是n个结点的简单图,若G中每对结点的度数之和,则G一定是哈密顿图.
答案:
大于或等于n
6、一个有向树T称为根树,若,其中称为树根,
称为树叶.
答案:
若有向图T恰有一个结点的入度为0,其余结点入度为1;入度为0的结点;入度为1的结点.
解答:
见根树、树根、树叶的定义.
7、设G是平面图,G有8个面,每个面的度数都是3,则G有__________条边,G有__________个顶点。
解答:
12条边,6个顶点
8、设G是有n个结点,m条边的连通图,要确定G的一棵生成树,必须删去G的条边.
答案:
m-n+1
解答:
见生成树的破圈或避圈求法.
9、在下图中,哪些是欧拉图?
哪些是哈密顿图?
哪些是平面图?
(1)
(2)
解答:
欧拉图:
5;哈密顿图:
4、5、6;平面图:
除6都是
10、设G是n阶无向带权边连通图,各边的权均为a(a>0),设T是G的一棵最小生成树,则T的权W(T)=________(n-1)*a_______________。
三、计算题(本大题共4小题,每小题10分,共40分)
1、设G=(V,E)是一个无向图,
(1)G=
(2)画出G的图解;
(3)指出与v3邻接的结点,以及与v3关联的边;(4)指出与e1关联的结点;
(5)该图是否有孤立结点和孤立边?
(6)求出各结点的度数;
解
(1)G=
(2)所给图G的一个图解,如图4.
(3)结点v1,v2,v4与v3邻接,v3关联
的边为e1,e2,e3.
(4)与边e1关联的结点为v2,v3.
(5)结点v6是孤立点;e5是孤立边.
(6)deg(v1)=3,deg(v2)=2,deg(v3)=3,
deg(v4)=2=deg(v5),deg(v6)=0,
deg(v7)=1=deg(v8).
2、设图G是具有3个顶点的无向完全图,试问
(1)G有多少个子图?
(2)G有多少个生成子图?
(3)如果没有任何两个子图是同构的,则G的子图个数是多少?
将它们构造出来.
解
(1)因为只有1个结点的子图有
个(平凡子图);
2个结点的子图有
个;3个结点的子图有
个;
所以,G共有3+6+8=17个子图.
(2)G的生成子图,含有G的所有结点,G有3条边,构成子图时,每条边有选中或不选中两种可能,所以G的生成子图的个数是23=8个.
(3)G的所有不同构的子图有7个,如图6所示.
3.图G=
(1)画出G的图形;
(2)写出G的邻接矩阵;
(3)求出G权最小的生成树及其权值.
解:
(1)因为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
所以,G的图形如右图所示:
(2)分析:
设G=
邻接矩阵:
(3)用避圈法:
第1步:
选(a,e)和(c,e)边;
第2步:
选(b,d)边;(为什么不选(a,c)?
)
第3步:
选(d,f)边;
第4步:
选(a,b)边.
这样,得到了最小的生成树,如右图中粗线所示.
最小的生成树的权为1+1+5+2+3=12.
上学期作业中的最小的生成树求的不对,主要是没有把握“取权数最小的边,且与前面取到的边不构成圈”,常常是只注意取权数最小的边了,而忽略“不构成圈”的要求。
问:
如果结点集是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,那么会求吗?
4.设有一组权为2,3,5,7,11,13,17,19,23,29,31,试
(1)画出相应的最优二叉树;
(2)计算它们的权值.
解:
(1)最优二叉树如右图所示:
方法(Huffman):
从2,3,5,7,11,13,17
19,23,29,31中选2,3为最低层结点,并
从权数中删去,再添上他们的和数,即
5,5,7,11,13,17,19,23,29,31;
再从5,5,7,11,13,17,19,23,29,31中选
5,5为倒数第2层结点,并从上述数列中
删去,再添上他们的和数,即7,10,11,13,
17,19,23,29,31;
然后,从7,10,11,13,17,19,23,29,31中选7,10和11,13为倒数第3层结点,并从上述数列中删去,再添上他们的和数,即17,17,24,19,23,29,31;
……
(2)权值为:
2⨯6+3⨯6+5⨯5+7⨯4+11⨯4+13⨯4+17⨯3+19⨯3+23⨯3+29⨯3+31⨯2
=12+18+25+28+44+52+51+57+69+87+62=505
讲评:
作业中最优二叉树都画对了,但计算总权值时把有些权的层数计算错了,导致总权值计算错误。
问:
如果一组权为2,3,6,9,13,15,能否画出最优二叉树?
四、证明题(本大题共3小题,任选2题,每小题10分,共20分)
1.若无向图G中只有两个奇数度结点,则这两个结点一定是连通的.
证明:
用反证法.设G中的两个奇数度结点分别为u和v.假设u和v不连通,即它们之间无任何通路,则G至少有两个连通分支G1,G2,且u和v分别属于G1和G2,于是G1和G2各含有一个奇数度结点.这与定理3.1.2的推论矛盾.因而u和v一定是连通的.
2.设G是一个n阶无向简单图,n是大于等于2的奇数.证明图G与它的补图
中的奇数度顶点个数相等.
证明:
设
,
.则
是由n阶无向完全图
的边删去E所得到的.所以对于任意结点
,u在G和
中的度数之和等于u在
中的度数.由于n是大于等于2的奇数,从而
的每个结点都是偶数度的(
度),于是若
在G中是奇数度结点,则它在
中也是奇数度结点.故图G与它的补图
中的奇数度结点个数相等.
3.设连通图G有k个奇数度的结点,证明在图G中至少要添加
条边才能使其成为欧拉图.
证明:
由定理3.1.2,任何图中度数为奇数的结点必是偶数,可知k是偶数.
又根据定理4.1.1的推论,图G是欧拉图的充分必要条件是图G不含奇数度结点.因此只要在每对奇数度结点之间各加一条边,使图G的所有结点的度数变为偶数,成为欧拉图.
故最少要加
条边到图G才能使其成为欧拉图。
1、若图G是不连通的,则G的补图G是连通的。
证明若图G=
由于任意两个连通分支G(Vi)与G(Vj)(i≠j)之间不连通,因此两个结点子集Vi与Vj之间的所有连线都在图G的补图G'中。
任取两个结点u和v,有两种情形:
a)u和v分别属于两个不同结点子集Vi与Vj。
由上可知G'包含边(u,v),故u和v在G'中是连通的。
b)u和v属于同—个结点子集Vi。
可在另一个结点子集Vj中取一个结点w,由上可知边(u,w)及边(v,w)均在G'中,故邻接边(u,w)和(w,v)组成的路连接结点u和v,即u和v在G'中也是连通的。
由此可知,当图G不是连通图时,G'必是连通图。
2、当且仅当G的一条边e不包含在G的回路中时,e才是G的割边。
证明必要性。
设e是连通图G的割边,e关联的两个结点
是u和v。
如果e包含在G的一个回路中,那么除边e=(u,v)外
还有一条分别以u和v为端点的路,所以删去边e后,G仍为连通
图,这与e是割边相矛盾。
充分性。
如果边e不包含在G的任一回路中,那么连接结点
u和v只有边e,而不会有其它连接u和v的任何路。
因为如果连
接u和v还有不同与边e的路,此路与边e就组成一条包含边e
的回路,从而导致矛盾。
所以删去边e后,u和v就不连通,故边
e是割边。
3、设G是简单平面图,则它—定有一个度数≤5的结点。
证明不妨设G是连通的。
若不连通,就可考察G中的一个连通分支。
因G是简单图,所以每个面至少有三条边,所以,3r≤2e,即有r≤
。
如果每个结点的度数都≥6,则6v≤2e,即有v≤
。
由欧拉公式可得
2=v-e+r≤
-e+
=0
矛盾。
所以,G中至少有一个结点的度数≤5。
最新文件----------------仅供参考--------------------已改成-----------word文本---------------------方便更改
赠人玫瑰,手留余香。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 测验 题图论 部分 优选