南京理工大学紫金学院离散数学(朱保平教授)期末复习试卷

1、（8分）已知{,{1}}Aa，{{}}Bb试求（1）2A（2）2AB2、（8分）已知YX,是2个任意的集合，试证明YXYX222。3、（6分）,*)(G是一个群，R是G上的一个二元关系，且对于Gyx,，Ryx),(当且仅当G，使得1**xy，试证明R是G上的等价关系。4、（8分）已知集合)}3,3(),2,2(),1,1(),,(),,(),,{(ccbbaaA，分别写出满足如下性质的二元关系：（1）该关系具有反自反性、传递性。（2）该关系具有自反性、反对称性和对称性。5、（8分）若在一个边长为4的正方形内任取129个点，则至少存在3个点，由它们构成的三角形（可能是退化的三角形，即一条直线）其面积小于81。试用抽屉原理证明之。6、（8分）已知(G，·)是一个群，Gg，作G到G的一个映射gf如下，对于Gx，xgxfg)(。求证gf是双射。7、(6分)图),(EVG，有n个顶点，n4条边，存在一个7度顶点，试证明其它顶点的度数均大于7。7、(6分)若无向图G中只有两个奇数度结点，则这两个结点一定连通。8、（8分）有24个人围坐一圆桌，边开会边交流网球技术。已知这24个人中，每个人至少与其余12个人打过球，试问是否有一种坐法，使每个人左、右两人都和他打过球？试用图论的语言证明之。9、（8分）按要求画图：（1）画一个14个顶点的哈密尔顿图但非欧拉图，有偶数条边；（2）（1）画一个14个顶点的欧拉图但非哈密尔顿图，有奇数条边；10、（6分）),(EVG是一个无向图。若10||V，则G或者G的补图G是非平面图。11、（6分）),(EVG是一个连通图，Vv，deg(v)=1，Ee是关联顶点v的一条边。试证明e一定是任何一棵生成树的枝。12、（6分）),(EVT是一棵树，它有3个1度顶点，2个2度顶点，则至少有一个顶点度数大于等于3。13、（8分）Q是一个有理数集，}0{*QQ,为*Q上的二元运算，且对于xyyxQyx10,,*。试证明),(*Q为群。14、（6分）设H是群G的子群，Gx，令}**|{xHHxGxA，证明A是G的子群。1、（8分）已知{,{1}}Aa，{{}}Bb试求（1）2A（2）2AB答：}}}1{{},{,,{2aAA}})}1{{,(}).,{,(),,(),,{(2AABA2、（8分）已知YX,是2个任意的集合，试证明YXYX222。证明：（1）对于任意的YXx22,则交集的定义知Xx2且Yx2，于是有YxXx,，从而有YXx，于是YXx2，故YXYX222。（2）对于YXx2,由幂集的定义知YXx,于是Xx，Yx，从而有Xx2且Yx2，因此YXx22，故YXYX222。3、（6分）,*)(G是一个群，R是G上的一个二元关系，且对于Gyx,，Ryx),(当且仅当G，使得1**xy，试证明R是G上的等价关系。证明：（1）自反性：对于Gx。因为,*)(G为一个群，所以Ge，使得11****xexex，由R的定义知，Rxx),(。（2）对称性：对于Gyx,，若Ryx),(，则G，使得1**xy。因为,*)(G为一个群，所以G11，使得，xexexxy**)*(**)*(*)**(***11111，即有，111**yx，由R的定义知，Rxy),(。（3）传递性：对于Gzyx,,，若RzyRyx),(,),(，则由R的定义知，G21,，使得122111**,**yzxy。因为,*)(G为一个群，所以G12*，使得111212121112**)*(**)*(*)**(*xxxz，由R的定义知，Rzx),(。综上，R是G上的等价关系。4、（8分）已知集合)}3,3(),2,2(),1,1(),,(),,(),,{(ccbbaaA，分别写出满足如下性质的二元关系：（1）该关系具有反自反性、传递性。（2）该关系具有自反性、反对称性和对称性。答：（1）（2）))}3,3(),3,3(()),2,2(),2,2(()),1,1(),1,1(()),,(),,(()),,(),,(()),,(),,{((ccccbbbbaaaa5、（8分）若在一个边长为4的正方形内任取129个点，则至少存在3个点，由它们构成的三角形（可能是退化的三角形，即一条直线）其面积小于81。试用抽屉原理证明之。证明：把边长为4的正方形等分边长为21的64个小正方形，在正方形内任取129个点，根据抽屉原理知，存在一个小正方形内至少有3个顶点，则它们构成的三解形其面积小于待于81。6、（8分）已知(G，·)是一个群，Gg，作G到G的一个映射gf如下，对于Gx，xgxfg)(。求证gf是双射。证明：（1）单射，对于任意Gxx21,，若)()(21xfxfg，即21xgxg，因为(G，·)为群且群满足左消去律，所以21xx。（2）满射，对于Gy，因为(G，·)为群，所以ygx1，使得yxfg)(。7、(6分)若无向图G中只有两个奇数度结点，则这两个结点一定连通。证明：若这两个结点不连通，则G一定可以分为两个不连通的子图，该2子图仅有一个奇数度顶点，与握手定理知矛盾。故这两个结点一定连通。8、（8分）有24个人围坐一圆桌，边开会边交流网球技术。已知这24个人中，每个人至少与其余12个人打过球，试问是否有一种坐法，使每个人左、右两人都和他打过球？试用图论的语言证明之。证明：24个人为24个顶点建立顶点集},,,{2421vvvV，对于任意的2个人，若它们打过球，则在2点间画一条边，构成边集E，从而构成图),(EVG。因为每个人至少与其余12个人打过球，则每个顶点的度数大于等于12，对于任意的2个顶点24)()(.,vdudvu，则哈密尔顿图的充分条件知，G中存在哈密尔顿图圈，按哈密尔顿图圈就坐就能使得每个人左、右两人都和他打过球。9、（8分）按要求画图：（1）画一个14个顶点的哈密尔顿图但非欧拉图，有偶数条边；（2）（1）画一个14个顶点的欧拉图但非哈密尔顿图，有奇数条边；略10、（6分）),(EVG是一个无向图。若10||V，则G或者G的补图G是非平面图。证明：设G和G的补图G均为平面图，令),(EVG，),(EVG，1||,||,||mEmEnV，则63,631nmnm，于是126)1(211nnnmm，02)2)(11(nn，因为10||V，所以02)2)(11(nn，矛盾，故G或者G的补图G是非平面图。11、（6分）),(EVG是一个连通图，Vv，deg(v)=1，Ee是关联顶点v的一条边。试证明e一定是任何一棵生成树的枝。证明：设存在一棵生成树e不为其枝，则e为弦。e对应一个圈，由于Ee是关联顶点v的一条边，则d(v)大于等于2，矛盾。故e一定是任何一棵生成树的枝。12、（6分）),(EVT是一棵树，它有3个1度顶点，2个2度顶点，则至少有一个顶点度数大于等于3。证明：设有顶点度数均小于等于2，根据握手定理知||21||2)5|(|243)(||2EEVvdE,矛盾。故至少有一个顶点度数大于等于3。13、（8分）Q是一个有理数集，}0{*QQ,为*Q上的二元运算，且对于xyyxQyx10,,*。试证明),(*Q为群。证明：（1）封闭性，对于*,Qba，显然有*10Qabba。（2）结合律，对于*,,Qcba，有cbabcabcacba)()10(10)10()(。（3）幺元为101（4）对于*Qa，其逆元为a100114、（6分）设H是群G的子群，Gx，令}**|{xHHxGxA，证明A是G的子群。证明：（1）因为H是群G，e为幺元，显然有eHHe**，故Ae。（2）对于Aba,，则A的定义知bHHbaHHa**,**，从而有),*(*)*()*(*)*(,*)*(**)*(*11111111bbHbbHbbbbHbbHbb于是11**bHHb，从而有)*(**)*()*(**)*(**)*(11111baHbHabHaaHbaHba故A是G的子群。