资源描述：
《离散数学期中测验题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、数学系0801、0802离散数学期中测验题及答案一、填空15%（每小题3分）1、设A={2，3，4，5，6}上的二元关系，则R=R的关系矩阵MR=2、设A={1，2，3}，则A上既不是对称的又不是反对称的关系R=；A上既是对称的又是反对称的关系R=A上空关系或A上恒等关系。3、表达式的二元树表示为4、若一棵完全二元（叉）树有2n-1个顶点，则它有n片树叶。5、设G是有n个结点m条边的连通平面图，且有k个面，则k等于(m-n+2)二、选择20%（每小题2分）1、设，S上关系R的关系图为则R具有（D）性质。A．自反性、对称性、传递性；B．反自反性、反对称性；C．
2、反自反性、反对称性、传递性；D．自反性。2、设G是一棵树，则G的生成树有(B)棵。A.0 B.1 C.2 D.不能确定3、下列哪一种图不一定是树（C）。A.无简单回路的连通图B.有n个顶点n-1条边的连通图C.每对顶点间都有通路的图D.连通但删去一条边便不连通的图4、下列图中是欧拉图的有(A)。A.[A]B.[D]C.[A][C]D.[B][D]5、N是自然数集，定义（即x除以3的余数），则f是（D）。A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射三、判断题5%（每小题1分）1、设A={a,{a}}，则{a}P(A) （错）2、空
3、集只是非空集合的子集（错）3、一条回路和任何一棵生成树至少有一条公共边。（错）4、可能有某种关系，既不是自反的，也不是反自反的。（对 ）5、若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（错）四、解答题40%（每小题8分）1、设A={1,2,…,10}。下列哪个是A的划分？若是划分，则它们诱导的等价关系是什么？（1）B={{1,3,6},{2,8,10},{4,5,7}};（2）C={{1,5,7},{2,4,8,9},{3,5,6,10}};（3）D={{1,2,7},{3,5,10},{4,6,8},{9}}解：（1）和（2）都不是
4、A的划分。（3）是A的划分。其诱导的等价关系是I{<1,2>,<2,1>,<1,7>,<7,1>,<2,7>,<7,2>,<3,5>,<5,3>,<3,10>,<10,3>,<10,5>,<5,10>,<4,6>,<6,4>,<4,8>,<8,4>,<6,8>,<8,6>}。2、设X={1,2,3,4,5}，X上的关系R={<1,1>,<1,2>,<2,4>,<3,5>,<4,2>}，求R的传递闭包t(R)。解：（用矩阵运算求，过程略）t(R)={<1,1>,<1,2>,<1,4>,<2,2>,<2,4>,<3,5>,<4,2>,<4,4>}3、设S={1,
5、2,3,4,6,8,12,24}，“”为S上整除关系，问：（1）画出偏序集的Hass图（2）偏序集的极小元、最小元、极大元、最大元是什么?解（1）≤={<1,2>,<1,3>,<1,4>,<1,6>,<1,8>,<1,12>,<1,24>,<2,4>,<2,6>,<2,8>，<2,12>,<2,24>,<3,6>,<3,12>,<3,24>,<4,8>,<4,12>,<4,24>,<6,12>,<6,24>,<8,24>,<12,24>}Hass图为（2）极小元、最小元是1，极大元、最大元是24。4、构造一个结点数与边数奇偶性相反的欧拉图。解：5、一次会议有
6、20人参加，其中每个人都在其中有不下10个朋友。这20人围成一圆桌入席。有没有可能使任意相邻而坐的两个人都是朋友？为什么？解：可以。将每个人对应成相应的顶点，若两人是朋友，则对应的两个顶点间连上一条无向边，作出一个简单无向图。由已知，图中每个顶点的度数都大于等于10。即图中任两个不相邻的顶点的度数大于等于20，即顶点数。故这个图是一个哈密尔顿图，从而存在哈密尔顿回路。任取一条哈密尔顿回路，按回路经过的顶点的次序安排对应的人的座位，就可满足要求。五、证明题1、设A是集合，RA×A，则R是对称的R＝R－1。证明：R，R是对称的，yRx。即R，
7、故R_1。从而RR-1。反之R-1,即R。R是对称的，yRx。即R，R_1R。故R=R-1。x，yA，若R，即R-1。R=R-1，R。即yRx，故R是对称的。2、若集合Ｘ＝｛（１，２），（３，４），（５，６），……｝（1）证明R是X上的等价关系。（2）求出X关于R的商集。1）证明：（1）自反性：（2）对称性：（3）传递性：即由（1）（2）（3）知：R是X上的先等价关系。2）、X/R=3、设G=是n个顶点的无向图(n>2)，若对任意u,vV，有d(u)+d(v)n，则G是连通图。证
8、明：用反证法证明。若G不连通，则它可分成两个独立的子
