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