离散数学部分测试题有附标准答案

《离散数学部分测试题有附标准答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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阶无向树.