一、简答题。
1.设kn无向完全图，当n。取怎样的值时kn为欧拉图？当n取怎样的值时kn为哈密顿图？
2．设kn无向完全图，当n。取怎样的值时kn为平面图？当n去怎样的值时kn为非平面图？
3. 树中的定点数与边数有怎样的关系？具有100个顶点和99条边的无向图有什么情况下是树？
4连通的平面图中定点数、边数和面数有怎样的关系？连通的极大平面图中定点数、边数有怎样的关系？
5.什么叫群？[z,+]与[z,*]哪个是群？
6．什么叫单位环？[z,+,与[e,+,哪个是单位环？
7.什么叫格？偏序集（,整除）与（,小于等于）是格？
8.什么叫布尔代数？格（，整除）是布尔代数吗？
二、求解题。
1．设v=,有向图g=的邻接矩阵为。
求g的可达矩阵和v1可达集合。
2.若无向树t中有4个2度顶点、3个3度顶点、2个4度顶点，求t中树叶的个数和t中边的条数。
3.假设传输的信息中a、b、c、d、e的频率分别是%，设计最佳的二元前缀码。
4.求群[z10,+10]的所有子群和所有生成元。
5.求格[p(),的所有互不同构的五元子格（画出哈密顿图即可）
6.求四阶非循环群的运算表。
三、证明题。
1设无向简单图g有n个顶点，p条边，如果p大于等于1/2(n-1)(n-2)+1，试证g是连通图。
2.设无向简单图g中无回路，证明：如果g的定点数n与边数m满足n=m+1，则g是树。
3.设无向图g的最小度数为k，证明g中存在长度不小于k的基本回路。
4. 证明：若群g对任意的x∈g有x^2=e,则g是交换群。
5. 证明：实数加法群[q,+]到非零实数乘法群[q-,*不存在同构映射。
6证明在又补分配格[l, ∧中，对任意a，b∈l有（a∧b）‘=a’ ∨b’
离散数学试卷A
2011 2012 课程名称 离散数学考试时间120分钟 一 填空题 每空2分，共16分 1 已知个体域是 p 1,1 1 p 1,2 1,p 2,1 0,p 2,2 0,则公式xy p x，y 的真值为。2 公式 x p x y q x,y 的前束范式为。3 设二元关系f g a 则fdom f。...
离散数学试卷
一 判断题。1.设g为无向图，若g中恰好n个结点，n 1条边，则g必为一棵树。2.若a b，则p a p b 3.设g为无向图，若g无回路，则g必为一棵树。4.设a，b是集合，若a b，则p a p b 5.无向图g是欧拉图当且仅当g连通且具有零个或两个奇数度结点。6.设a,b是任意集合，则 a b...
离散数学试卷 A
2014 2015学年第二学期。每题10分，共100分，答案一律写在答题纸上 1.化为主析取范式与主合取范式。2.证明 3.甲 乙 丙 丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的 1 甲和乙只有一人参加 2 丙参加，丁必参加 3 乙或丁至多参加一人 4 丁不参加，...