黑龙江科技学院试题
第1套
课程名称：离散数学 课程编号：24014270适用专业：数学 08-1、2 共2页 命题： 张亚江 教研室主任： 第1页
一、填空题（每空5分，共40分）
1、n阶k?正则图G的边数m? 。
无向图G有8条边，1个1度顶点，2个2度顶点，1个5度顶点，其余顶点度 均为3，求3度顶点的个数为 。
3、在完全图K2k(k?2) 上至少加____ _______条边，才能成为欧拉图。 4、设T是个边带权均为1的n阶带权图的一颗最小生成树，则W（T）= 。 5、n阶m条边的无向连通图G,对应它的生成树T有 个基本回路系统。 6、当n为 时，完全图既是欧拉图，又是哈密顿图。 7、n阶竞赛图的基图为 。
8、度数列（3，3，2，1）不可图化的理由是 。 二、（10分）
画出3阶有向完全图的所有2条边的非同构的子图。
三、（9分）画出3颗树高为3，其基图非同构的正则2叉树。 四、（10分）
下面两组数中，哪个能充当无向树的度数列？若能，画出至少3颗非同构的无向树：（1）1，1，1，2，2，2，2，3；（2）1，1，1，2，2，2，2，5. 五、（8分）
求带权为5，5，6，7，10，15，20，30的最优树T，并求W(T)。
1
黑龙江科技学院试题
第1套
课程名称：离散数学 课程编号：24014270适用专业：数学 08-1、2 共2页 命题： 张亚江 教研室主任： 第2页
六、（10分）
求出图中各面的边界及次数，重新找两个平面嵌入，使外部面的次数分别为3和4。 七、（13分）有向图D如图所示：（1）求D的邻接矩阵A，以及A，A，A. （2）D中v4到v3长度为1，2，3，4的通路个为几条？ （3）D中v1到v1长度为1，2，3，4的通路个为几条？ （4）D中长度为4的通路共有多少条？其中有多少条是回路？
234e1 e6 V1 e7 V4 e5 e2 e4 e3第六题图 e8 V2 第七题图 V3
2
黑龙江科技学院考试题答案
一、填空题（每题5分共40分） 1、
kn 2、 2 3、 k 4 n?1 25、 m-n+1 6、 奇 数 7、 无向完全图 8、含3个奇度顶点（奇度顶点不能为奇数个） 二、（10分）每图2分
三、（9分）每图三分
。 。 。
。 。 。 。 。 。
。 。 。 。 。 。 。 。 。 。
。 。 。 。 。 。 。 。 。 。 。 。 四、（10分）
1中数组满足条件。长度为n的数组，若能充当无向树T的度数列，则阶树n和边数m的关系为m=n-1,由握手定理有2n?2?树的度数列。图形如下：
?di?1ni，可知（2）数列不能充当无向
3
。 。 。
。 。 。 。 。 。
。 。 。 。 。 。
。 。 。 。 。
。 。 。 。
。 。 。 。
。 。 。 。 五、（8分）
所求最优树如图所示：w(T)=267 98
40 58
20 20 28 30
10 10 13 15 5 5 6 7 六、（10分）deg(R1)= deg(R3)=3 , deg(R2)=4 , deg(R0)=6 .
。 。 。
。
。 。 。 。 。 。 。 。 外部面为3 外部面为4
4
相关推荐：
loading