离散生期末题集合论与图论

1、集合论与图论试 。 。（） （） （）4集合1，2，10上共个不同的二（）（）（）（）8P为正整数，Kp的顶点连通度为P1（）9（P，P）（） （2） （）123456789把置换579413826分解成循环置换的乘积计算下面两个图G1 和G2 的色数（答：G1 的色数，G2 的色数设X为集合，R为X上的偏序关系，计算URi等于什么求下面的有向图D（）6一个有向图D=(V，A)满足什么条件是V 到V ）（）8Xn 个元素的集合，X（） 设A、B、C和D(AC)(BD) (AI B)(CD)U(AB)X为有穷集合，gf X X，gfIx fgg f1举例说明，当X为无穷集时，上述结论不成立。（1

2、2 分，每小题 6 分）证明：每个平面图G VE，如果G 是偶图，则V ，使得deg 3设TVA为具有P个顶点的二元树，T有n22的顶点。求Tn0设G(V,E)为通图，e为G的一条边。证明：e是G的桥当且仅当e在X a,bcdR 哈工2006年科季学集合论与图论试题参考二、1.n2 ；2.15)278)(396)；3.3、2；4. 0 1 1 1 1 邻接矩阵AR1 1 1 1 1 1 0 1 1 1 1 V，od()12(P1)； 1人诚nn2 9. 9（奇数三、1.证 设(x, y)(AC)(BD) ，则(x, y)AC ，且(x, y)BD，于是， xA、yC 、xB但yD或xB或yD。

3、if xB，则xA B，yC ，故 (x, y)(A B)C 右 边 ； ify D ， 则 y 。 若 xB ， 则 (x y, (A I(C 右边。因此，左 右。反之，设(x y, 右。if(xyAI B(CDxA，xB，yC yD， (x, yAC (x, yBD(x y, 左；if(x, yA BC xAxB， yC ，故(x, yAC ，且(x, yBD(x y, 左。 Ixf fgg f1X12,3,LfgNN 。定义f(n n1nN g(1) 1， g(nn1,n1gof(1)1gof(ng(n1)nn1gof Ix，但fg均不是一一g f1。四、1.证 如果结论不成立，那么V

4、deg 4，从而4p2q三角形，故每个面上至少4条边。于是4f 2q，从而p f q，2.证 1 n1pn2n1n0p12n2n1，于是n2n1n012n2n1，从而n0 n21五、1. 该图不是图。如果是哈氏图，则有哈圈C。于是，边28 在C 上，否则 6789106C28C23、89C上，从而 43、39 在C 上。411 不在C 上，119 在C 上，9 有三边在C 上。 否则 G 有一生成树不含边 e，但G e不连通，。设边e在G的每个生成树中，则G e 无生成树，从而不连通。六、1. R (a,b),(bc),(cc),(ac),(ba)(c,b),(aa),(b,b),(c2X上二元关系如果是自反的，对称且传递的，则称为X上等价关系。xX，集合xy | yXx y称 的一个等价类。X 上每个等价关系的所有等价类之集是 X 七、1.证如果从 N 到0, 1的所有之集可数，则可排成无重复项的无穷序 ifaii0；否则bi0。该序列对应的函数f(i)bi，iN，不为f1, f2,L 任一个，2证 if f 1，则为树，结论成立。iff 1时结论成立，则设Gf+1G 中去掉一个面上一条边得 G。在G中有p(q1)(f 1)2，pq f 2。五、2.的简单