文档介绍：一、填空15%(每空3分)
1、设G为9阶无向图,每个结点度数不是5就是6,则G中至少有个5度结点。
2、n阶完全图,Kn的点数X (Kn) = 。
3、有向图中从v1到v2长度为2的通路有条。
4、设[R,+,·]是代数系统,如果①[R,+]是交换群②[R,·]是半群
③则称[R,+,·]为环。
5、设是代数系统,则满足幂等律,即对有。
二、选择15%(每小题3分)
下面四组数能构成无向简单图的度数列的有( )。
A、(2,2,2,2,2); B、(1,1,2,2,3);
C、(1,1,2,2,2); D、(0,1,3,3,3)。
下图中是哈密顿图的为( )。
如果一个有向图D是强连通图,则D是欧拉图,这个命题的真值为( )
A、真; B、假。
下列偏序集( )能构成格。
设,*为普通乘法,则[S,*]是()。
A、代数系统; B、半群; C、群; D、都不是。
三、证明 48%
1、(10%)在至少有2个人的人群中,至少有2 个人,他们有相同的朋友数。
2、(8%)若图G中恰有两个奇数度顶点,则这两个顶点是连通的。
3、(8%)证明在6个结点12条边的连通平面简单图中, 每个面的面数都是3。
4、(10%)证明循环群的同态像必是循环群。
5、(12%)设是布尔代数,定义运算*为,
求证[B,*]是阿贝尔群。
四、计算22%
1、在二叉树中
求带权为2,3,5,7,8的最优二叉树T。(5分)
求T对应的二元前缀码。(5分)
下图所示带权图中最优投递路线并求出投递路线长度(邮局在D点)。
一、填空(15%)每空3 分
1、 6;2、n;3、2;4、+对·分配且·对+分配均成立;5、。
二、选择(15%)每小题3分
题目
1
2
3
4
5
答案
A,B
B,D
B
C
D
三、证明(48%)
1、(10分)证明:用n个顶点v1,…,vn表示n个人,构成顶点集V={v1,…,vn},设,无向图G=(V,E)
现证G中至少有两个结点度数相同。
事实上,(1)若G中孤立点个数大于等于2,结论成立。
(2) 若G中有一个孤立点,则G中的至少有3个顶点,既不考虑孤立点。设G中每个结点度数均大于等于1,又因为G为简单图,所以每个顶点度数都小于等于n-1,由于G中n顶点其度数取值只能是1,2,…,n-1,由鸽巢原理,必然至少有两个结点度数是相同的。
2、(8分)证:设G中两个奇数度结点分别为u,v。若 u,v不连通则至少有两个连通分支G1、G2,使得u,v分别属于G1和G2。于是G1与G2中各含有一个奇数度结点,与握手定理矛盾。因而u,v必连通。
3(8分)