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

1、1、（8分）已知，试求（1） （2）2、（8分）已知是2个任意的集合，试证明。3、（6分）是一个群，是上的一个二元关系，且对于， 当且仅当，使得，试证明是上的等价关系。4、（8分）已知集合，分别写出满足如下性质的二元关系：（1）该关系具有反自反性、传递性。（2）该关系具有自反性、反对称性和对称性。5、（8分）若在一个边长为4的正方形内任取129个点，则至少存在3个点，由它们构成的三角形（可能是退化的三角形，即一条直线）其面积小于。试用抽屉原理证明之。6、（8分）已知(，)是一个群，作到的一个映射如下，对于，。求证是双射。7、(6分)图，有个顶点，条边，存在一个7度顶点，试证明其它顶点的度数均大

2、于7。7、(6分)若无向图G中只有两个奇数度结点，则这两个结点一定连通。8、（8分）有24个人围坐一圆桌，边开会边交流网球技术。已知这24个人中，每个人至少与其余12个人打过球，试问是否有一种坐法，使每个人左、右两人都和他打过球？试用图论的语言证明之。9、（8分）按要求画图：（1）画一个14个顶点的哈密尔顿图但非欧拉图，有偶数条边；（2）（1）画一个14个顶点的欧拉图但非哈密尔顿图，有奇数条边；10、（6分）是一个无向图。若，则或者的补图是非平面图。11、（6分）是一个连通图，deg(v)=1，是关联顶点的一条边。试证明一定是任何一棵生成树的枝。12、（6分）是一棵树，它有3个1度顶点，2 个

3、2度顶点，则至少有一个顶点度数大于等于3。13、（8分）是一个有理数集，,为上的二元运算，且对于。试证明为群。14、（6分）设是群的子群，令，证明是的子群。1、（8分）已知，试求（1） （2）答： 2、（8分）已知是2个任意的集合，试证明。证明：（1）对于任意的,则交集的定义知且，于是有，从而有，于是，故。（2）对于,由幂集的定义知,于是，从而有且，因此，故。3、（6分）是一个群，是上的一个二元关系，且对于， 当且仅当，使得，试证明是上的等价关系。证明：（1）自反性：对于。因为为一个群，所以，使得，由的定义知，。（2）对称性：对于，若，则，使得。因为为一个群，所以，使得，即有，由的定义知，。（

4、3）传递性：对于，若，则由的定义知，使得。因为为一个群，所以，使得，由的定义知，。综上，是上的等价关系。4、（8分）已知集合，分别写出满足如下性质的二元关系：（1）该关系具有反自反性、传递性。（2）该关系具有自反性、反对称性和对称性。答：（1）（2）5、（8分）若在一个边长为4的正方形内任取129个点，则至少存在3个点，由它们构成的三角形（可能是退化的三角形，即一条直线）其面积小于。试用抽屉原理证明之。证明：把边长为4的正方形等分边长为的64个小正方形，在正方形内任取129个点，根据抽屉原理知，存在一个小正方形内至少有3个顶点，则它们构成的三解形其面积小于待于。6、（8分）已知(，)是一个群，

5、作到的一个映射如下，对于，。求证是双射。证明：（1）单射，对于任意，若，即，因为(，)为群且群满足左消去律，所以。（2）满射，对于，因为(，)为群，所以，使得。7、(6分)若无向图G中只有两个奇数度结点，则这两个结点一定连通。证明：若这两个结点不连通，则G一定可以分为两个不连通的子图，该2子图仅有一个奇数度顶点，与握手定理知矛盾。故这两个结点一定连通。8、（8分）有24个人围坐一圆桌，边开会边交流网球技术。已知这24个人中，每个人至少与其余12个人打过球，试问是否有一种坐法，使每个人左、右两人都和他打过球？试用图论的语言证明之。证明：24个人为24个顶点建立顶点集，对于任意的2个人，若它们打过

6、球，则在2点间画一条边，构成边集，从而构成图。因为每个人至少与其余12个人打过球，则每个顶点的度数大于等于12，对于任意的2个顶点，则哈密尔顿图的充分条件知，G中存在哈密尔顿图圈，按哈密尔顿图圈就坐就能使得每个人左、右两人都和他打过球。9、（8分）按要求画图：（1）画一个14个顶点的哈密尔顿图但非欧拉图，有偶数条边；（2）（1）画一个14个顶点的欧拉图但非哈密尔顿图，有奇数条边；略10、（6分）是一个无向图。若，则或者的补图是非平面图。证明：设和的补图均为平面图，令，则，于是，因为，所以，矛盾，故或者的补图是非平面图。11、（6分）是一个连通图，deg(v)=1，是关联顶点的一条边。试证明一定是任何一棵生成树的枝。证明：设存在一棵生成树不为其枝，则为弦。对应一个圈，由于是关联顶点的一条边，则d(v)大于等于2，矛盾。故一定是任何一棵生成树的枝。12、（6分）是一棵树，它有3个1度顶点，2 个2度顶点，则至少有一个顶点度数大于等于3。证明：设有顶点度数均小于等于2，根据握手定理知,矛盾。故至少有一个顶点度数大于等于3。13、（8分）是一个有理数集，,为上的二元运算，且对于。试证明为群。证明：（1）封闭性，对于