试卷七试题与答案

试卷七试题与答案一、填空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、0001101110100001；B、1111111111111111；C、0001101111000010；D、0001101110100010。3、下列几个图是简单图的有()。A.G1=(V1,E1),其中V1={a,b,c,d,e},E1={ab,be,eb,ae,de}；B.G2=(V2,E2)其中V2=V1,E2={a,b,b,c,c,a,a,d,d,a,d,e}；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、),2(SG，其中}3,2,1{S，为集合对称差运算，则方程}3,1{}2,1{x的解为（）。A、}3,2{；B、}3,2,1{；C、}3,1{；D、。三、证明34%1、证明：在至少有2个人的人群中，至少有2个人，他的有相同的朋友数。（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}，运算*如下表，则B4,*是一个群（称作Klein四元群答案：一、填空15%（每小题3分）1、Vvmvd2)(；2、奇数；3、5；4、n；5、臂力小者二、选择15%（每小题3分）题目12345答案BCBBA三、证明34%1、（10分）证明：用n个顶点v1，…，vn表示n个人，构成顶点集V={v1，…，vn}，设},,,|{v）（uvuVvuuvE是朋友且，无向图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个顶点的度数至少有两个结点度数是相同的。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由图论基本定理知：242)deg(mF，而3)deg(iF，所以必有3)deg(iF，即每个面用3条边围成。4、（10分）证：设循环群[A，·]的生成元为a，同态映射为f，同态像为f（A），*，于是Aaamn,都有)(*)()(mnmnafafaaf*eababeeababaaeabbbbabeaababbae对n=1有)()(afafn=2,有22))(()(*)()()(afafafaafaf若n=k-1时有11))(()(kkafaf对n=k时，kkkkkafafafafafaafaf))(()(*))(()(*)()()(111这表明，f(A)中每一个元素均可表示为naf))((，所以f(A),*是以f(a)生成元的循环群。四、中国邮递员问题14%解：图中有4个奇数结点，5)(,3)(,5)(,3)(5321vdvdvdvd（1）求5321,,,vvvv任两结点的最短路5736562532457133212211535232513221,,,,,4)(,3)(,2)(,4)(,5)(,3)(vvvpvvvpvvpvvvpvvvpvvpvvdvvdvvdvvdvvdvvd再找两条道路使得它们没有相同的起点和终点，且长度总和最短：,,3245713vvpvvvp（2）在原图中复制出43,pp，设图G‘，则图G‘中每个结点度数均为偶数的图G‘存在欧拉回路157123.5726542371vvvvvvvvvvvvvvvvC，欧拉回路C权长为43。五、根树的应用13%解：用100乘各频率并由小到大排列得权数30,20,15,10,10,5,5,587654321（1）用Huffman算法求最优二叉树：（2）前缀码用00000传送5；00001传送6；0001传送7；100传送3；101传送4；001传送2；11传送1；01传送0（频率越高传送的前缀码越短）。六、10%证明：（1）乘：由运算表可知运算*是封闭的。（2）群：即要证明)*(**)*(zyxzyx，这里有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。所以B4,*为群。