《试卷七试题与附标准答案》由会员分享，可在线阅读，更多相关《试卷七试题与附标准答案（5页珍藏版）》请在金锄头文库上搜索。
1、试卷七试题与答案一、 填空 15% （每小题 3分）1. 任何(n,m) 图G = (V,E) , 边与顶点数的关系是 。2. 当n为 时,非平凡无向完全图Kn是欧拉图。3. 已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,则T中有个1度顶点。4. n阶完全图Kn的点色数X(KN)= 。5. 一组学生,用两两扳腕子比赛来测定臂力大小,则幺元是 。二、 选择 15% （每小题 3分）1、下面四组数能构成无向图的度数列的有( )。 A、 2,3,4,5,6,7； B、 1,2,2,3,4； C、 2,1,1,1,2； D、 3,3,5,6,0。2、图 的邻接矩阵为( )。A、；B、
2、；C、；D、。3、下列几个图是简单图的有( )。A. G1=(V1,E1), 其中 V1=a,b,c,d,e,E1=ab,be,eb,ae,de；B. G2=(V2,E2)其中V2=V1,E2=,；矚慫润厲钐瘗睞枥庑赖。C. G=(V3,E3), 其中V3=V1,E3=ab,be,ed,cc；D. G=(V4,E4),其中V4=V1,E4=（a,a）,（a,b）,（b,c）,（e,c）,（e,d）。聞創沟燴鐺險爱氇谴净。4、下列图中是欧拉图的有( )。5、，其中，为集合对称差运算，则方程的解为（）。A、； B、； C、； D、。三、 证明 34% 1、 证明：在至少有2 个人的人群中，至少有2
3、 个人，他的有相同的朋友数。（8分）2、 若图G中恰有两个奇数顶点，则这两个顶点是连通的。（8分）3、 证明：在6个结点12条边的连通平面简单图中，每个面的面度都是3。（8分）4、 证明循环群的同态像必是循环群。（10分）四、 中国邮递员问题13%求带权图G中的最优投递路线。邮局在v1点。五、 根树的应用 13%在通讯中，八进制数字出现的频率如下：0：30%、1：20%、2：15% 、3：10%、4：10%、5：5%、6：5%、7：5%求传输它们最佳前缀码（写出求解过程）。六、 10%设B4=e , a , b , ab ，运算*如下表，*则是一个群（称作Klein四元群答案：一、 填空 15
4、%（每小题3分）1、；2、奇数；3、5；4、n；5、臂力小者二、 选择 15%（每小题 3分）题目12345答案BCBBA三、 证明 34%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中顶点数到值只能是1，2，n-1这n-1个数，因而取n-1个值的n个顶点的度数至少有两个结点度数
5、是相同的。酽锕极額閉镇桧猪訣锥。2、（8分）证：设G中两个奇数度结点分别为u，v。若 u，v不连通，即它们中无任何通路，则至少有两个连通分支G1、G2，使得u，v分别属于G1和G2。于是G1与G2中各含有一个奇数度结点，与握手定理矛盾。因而u，v必连通。彈贸摄尔霁毙攬砖卤庑。3、（8分）证：n=6,m=12 欧拉公式n-m+f=2知 f=2-n+m=2-6-12=8由图论基本定理知：，而，所以必有，即每个面用3条边围成。4、（10分）证：设循环群A，的生成元为a，同态映射为f，同态像为，于是都有对n=1有n=2, 有若n=k-1时有对n=k时，这表明，f(A)中每一个元素均可表示为，所以是以f
6、(a) 生成元的循环群。四、 中国邮递员问题 14%解：图中有4个奇数结点，（1） 求任两结点的最短路再找两条道路使得它们没有相同的起点和终点，且长度总和最短：（2） 在原图中复制出，设图G，则图G中每个结点度数均为偶数的图G存在欧拉回路，欧拉回路C权长为43。五、 根树的应用13%解：用100乘各频率并由小到大排列得权数（1） 用Huffman算法求最优二叉树：（2） 前缀码用 00000传送 5；00001传送 6；0001传送 7；100传送 3；101传送 4；001传送 2；11传送 1；01传送 0 （频率越高传送的前缀码越短）。謀荞抟箧飆鐸怼类蒋薔。六、 10%证明：（1） 乘：
7、由运算表可知运算*是封闭的。（2） 群：即要证明，这里有43=64个等式需要验证但： e是幺元，含e的等式一定成立。ab=a*b=b*a，如果对含a，b的等式成立，则对含a、b、ab的等式也都成立。剩下只需验证含a、b等式，共有23=8个等式。即：(a*b)*a=ab*a=b=a*(b*a)=a*ab=b； (a*b)*b=ab*b=a=a*(b*b)=a*e=a；厦礴恳蹒骈時盡继價骚。(a*a)*a=e*a=a=a*(a*a)=a*e=a ； (a*a)*b=e*b=b=a*(a*b)=a*ab=b；茕桢广鳓鯡选块网羈泪。(b*b)*a=e*a=a=b*(b*a)=b*ab=a； (b*b)*b=e*b=b=b*(b*b)=b*e=b；鹅娅尽損鹌惨歷茏鴛賴。(b*a)*a=ab*a=b=b*(a*a)=b*e=b ； (b*a)*b=ab*b=a=b*(a*b)=b*ab=a 。籟丛妈羥为贍偾蛏练淨。（3） 幺： e为幺元（4） 逆：e -1=e ；a -1=a ；b -1=b ； (ab) -1=ab 。所以为群。
