试卷七试题与附标准答案

《试卷七试题与附标准答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、、图的邻接矩阵为()。A、；B、；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）}

3、。聞創沟燴鐺險爱氇谴净。4、下列图中是欧拉图的有()。5、，其中，为集合对称差运算，则方程的解为（）。A、；B、；C、；D、。一、证明34%1、证明：在至少有2个人的人群中，至少有2个人，他的有相同的朋友数。（8分）2、若图G中恰有两个奇数顶点，则这两个顶点是连通的。（8分）3、证明：在6个结点12条边的连通平面简单图中，每个面的面度都是3。（8分）4、证明循环群的同态像必是循环群。（10分）二、中国邮递员问题13%求带权图G中的最优投递路线。邮局在v1点。三、根树的应用13%在通讯中，八进制数字

4、出现的频率如下：0：30%、1：20%、2：15%、3：10%、4：10%、5：5%、6：5%、7：5%求传输它们最佳前缀码（写出求解过程）。四、10%设B4={e,a,b,ab}，运算*如下表，*则是一个群（称作Klein四元群答案：一、填空15%（每小题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）

5、残骛楼諍锩瀨濟溆塹籟。现证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

6、、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(a)生成元的循

7、环群。一、中国邮递员问题14%解：图中有4个奇数结点，（1）求任两结点的最短路再找两条道路使得它们没有相同的起点和终点，且长度总和最短：（2）在原图中复制出，设图G‘，则图G‘中每个结点度数均为偶数的图G‘存在欧拉回路，欧拉回路C权长为43。二、根树的应用13%解：用100乘各频率并由小到大排列得权数（1）用Huffman算法求最优二叉树：（1）前缀码用00000传送5；00001传送6；0001传送7；100传送3；101传送4；001传送2；11传送1；01传送0（频率越高传送的前缀码越短）。謀

8、荞抟箧飆鐸怼类蒋薔。二、10%证明：（1）乘：由运算表可知运算*是封闭的。（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