黑龙江科技学院试题第1套。
课程名称：离散数学课程编号：24014270适用专业：数学 共2页。
命题： 张亚江教研室主任第1页。
一、填空题（每空5分，共40分）
3、在完全图上至少加条边，才能成为欧拉图。
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套。
课程名称：离散数学课程编号：24014270适用专业：数学 共2页。
命题： 张亚江教研室主任第2页。
六、（10分）
求出图中各面的边界及次数，重新找两个平面嵌入，使外部面的次数分别为3和4。
七、（13分）有向图d如图所示：（1）求d的邻接矩阵。
2）d中长度为1，2，3，4的通路个为几条？
3）d中长度为1，2，3，4的通路个为几条？
4）d中长度为4的通路共有多少条？其中有多少条是回路？
黑龙江科技学院考试题答案。
一、填空题（每题5分共40分）
1、 2、 2 3、 k 4
5、 m-n+1 6、 奇数 7、 无向完全图
8、含3个奇度顶点（奇度顶点不能为奇数个）
二、（10分）每图2分。
三、（9分）每图三分。
四、（10分）
1中数组满足条件。长度为n的数组，若能充当无向树t的度数列，则阶树n和边数m的关系为m=n-1,由握手定理有，可知（2）数列不能充当无向树的度数列。图形如下：
五、（8分）
所求最优树如图所示：w(t)=267
六、（10分）deg(r1)= deg(r3)=3 , deg(r2)=4 , deg(r0)=6 .
外部面为3外部面为4
七（13分）
1)v1到v3长度为1，2，3，4的通路分别为0条，2条，2条，2条；
2)v1到v1长度为1，2，3，4的通路分别为1条，1条，2条，4条；
3）d中长度为4的通路共34条，其中9条是回路；
离散数学试题
网络学院离散数学模拟试题1 考试时间 90 分钟考试方式 开卷。专业年级姓名学号 一 选择填空题 每个空格3分，共30分。答案写在答题纸上。1b.b.cd.2 若集合p q满足，则 必成立。c abcd 3 设，则是 d a 从x到y的双射。b 从x到y的满射，但不是单射。c 从x到y的映射，但不是...
离散数学试题
一 填空题 每题2分，共14分 1 若g为连通的平面图，有n个顶点，k个面，则g的边数为。2 设a b 则a b 3 集合的幂集。4 设表示 会飞 论述域为，则命题 一切鸟都会飞 可译为 5 若集合a上的二元关系r的关系矩阵主对角线上元素全是1，则关系r具有性质。6 公式的对偶公式为。7 连通无向图...
离散数学试题
1 设a是m元集合，b是n元集合。问a到b共有多少个不同的二元关系？设a b 试写出a到b的全部二元关系。p18 2 用演绎法证明共同蕴涵p s。p48 3 将下面的命题符号化 已知每一个运动员都是强壮的，而每一个既强壮又聪明的人在他所从事的事业中都将获得成功，彼得是运动员并且是聪明的，证明彼得在他...