欢迎来到天天文库
浏览记录
ID:34816754
大小:75.00 KB
页数:3页
时间:2019-03-11
《离散数学部分测试题有附标准答案》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、离散数学第三部分测试题一、填空题1.设是有6个点的无向完全图,则有15条边.2.n阶有向完全图的边数为:3.图G的连通分支数P(G)=4.4.无向图G是欧拉图当且仅当G是连通图且没有奇度顶点.5.有向图G是欧拉图当且仅当G是强连通图且每个顶点的入度等于出度.二、选择题1.下面四组数能构成无向图的度数列的有(B)A.2,3,4,5,6,7B.1,2,2,3,4C.2,1,1,1,2D.3,3,5,6,0计算题1.无向图G有16条边,3个4度顶点,4个3度顶点,其余顶点的度数均小于3,问G的阶数n至少为几?矚慫润厲钐瘗睞枥庑赖。解设G的阶数为n,即n个顶点,不妨设,而均小于3,由握手定理得:2.
2、设无向图G有10条边,3度与4度顶点各2个,其余顶点的度数均小于3,问G中至少有几个顶点?在最少顶点的情况下,写出G的度数列、Δ(G)、δ(G).聞創沟燴鐺險爱氇谴净。答案残骛楼諍锩瀨濟溆塹籟。(1)G中至少有7个顶点.(2)在最少顶点情况下,度数列为2,2,2,3,3,4,4(3)在最少顶点情况下,Δ(G)=4,δ(G)=23.有向图D如图所示:D(1)D中V1到V4长度为1,2,3,4的通路各有多少条?(2)D中V1到V1长度为1,2,3,4的回路各为多少条?(3)D中长度为4的通路(不含回路)有多少条?(4)D中长度为4的回路有多少条?酽锕极額閉镇桧猪訣锥。(5)D中长度小于等于4的通路
3、共有多少条?其中有几条是回路?(6)写出D的可达矩阵.彈贸摄尔霁毙攬砖卤庑。解有向图D的邻接矩阵为,,,(1)D中V1到V4长度为1,2,3,4的通路分别有0,0,2,2条;(2)D中V1到V1长度为1,2,3,4的回路分别有1,1,3,5条;(3)D中长度为4的通路(不含回路)有35条;(4)D中长度为4的回路有13条;謀荞抟箧飆鐸怼类蒋薔。(5)D中长度小于等于4的通路共有7+14+26+48=95条其中1+3+7+13=24条是回路;(6)D的可达矩阵为厦礴恳蹒骈時盡继價骚。4.一棵无向树T有5片叶子,3个2度分支点,其余的分支点是3度顶点,问T是几阶无向树?解设3度顶点的个数为x,根据
4、握手定理可得故T是11阶无向树.
此文档下载收益归作者所有