离散数学部分测试题有答案.docVIP

离散数学第三部分测试题 填空题 1.设是有6个点的无向完全图，则有 15 条边。 2．n阶有向完全图的边数为: 3.图G的连通分支数P(G)= 4 。 4．无向图G是欧拉图当且仅当 G是连通图且没有奇度顶点 。 5．有向图G是欧拉图当且仅当 G是强连通图且每个顶点的入度等于出度 。 选择题 1．下面四组数能构成无向图的度数列的有（ B ） A．2，3，4，5，6，7 B．1，2，2，3，4 C．2，1，1，1，2 D．3，3，5，6，0 计算题  HYPERLINK /courses/lssx/longtime/part4/chapter14/14_01_11_02.htm 无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点的度数均小于3，问G的阶数n至少为几？ 解 设G的阶数为n，即n个顶点，不妨设，而均小于3，由握手定理得： 2．设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G中至少有几个顶点？在最少顶点的情况下，写出G的度数列、Δ(G)、δ(G).  HYPERLINK javascript:popwin(%22ex14_01.htm%22,%22400%22,%22150%22) 答案 (1)G中至少有7个顶点。 (2)在最少顶点情况下，度数列为2,2,2,3,3,4,4 (3)在最少顶点情况下，Δ(G)=4，δ(G)=2 3.有向图D如图所示： D （1）D中V1到V4长度为1，2，3，4的通路各有多少条？ （2）D中V1到V1长度为1，2，3，4的回路各为多少条？ （3）D中长度为4的通路（不含回路）有多少条？ （4） HYPERLINK /courses/lssx/longtime/part4/chapter14/14_04_04_08.htm D中长度为4的回路有多少条? （5）D中长度小于等于4的通路共有多少条？其中有几条是回路？ （6） HYPERLINK /courses/lssx/longtime/part4/chapter14/14_04_04_10.htm 写出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） HYPERLINK /courses/lssx/longtime/part4/chapter14/14_04_04_08.htm D中长度为4的回路有13条； （5）D中长度小于等于4的通路共有7+14+26+48=95条 其中1+3+7+13=24条是回路；  HYPERLINK /courses/lssx/longtime/part4/chapter14/14_04_04_10.htm D的可达矩阵为 4.一棵无向树T有5片叶子，3个2度分支点，其余的分支点是3度顶点，问T是几阶无向树？ 解 设3度顶点的个数为x,根据握手定理可得 故T是11阶无向树.