北大集合论与图论往年考题

2008年期中考题：一、用真值表证明德*摩根律（证明其中一条即可）。二、设A,B,C是集合，试问在什么条件下(A-B)-C=A-(B-C)？给出证明。三、设A={a,b,c}，问A上有多少种不同的：二元关系？自反关系？对称关系？传递关系？等价关系？偏序关系？良序关系？四、用花括号和空集来表示12（注意表示集合的叉乘）.五、设R是实数集，Q是有理数集，试构造出R-Q与R之间的双射.1．简单叙述构造的思路；2．给出双射f：R-Q-R或f：R-R-Q的严格定义。2008年期末考题：一、在有向图中，如果存在从顶点u到顶点v的有向通路，则说u可达v；如果顶点u和顶点v互相可达，则说u双向可达v。回答下列问题：1．顶点集上的可达关系是不是等价关系？为什么？2．顶点集上的双向可达关系是不是等价关系？为什么？3．对于上述两个关系，如果是等价关系，其等价类的导出子图称为什么？二、一棵树有13个顶点，除了3个2度顶点和若干个树叶之外，其余顶点都是5度。1．求出5度顶点的个数（写出计算过程）；2．画出所有互不同构的这种树。三、计算出右图中v1到v4长度为4的通路数（要写出计算过程的主要步骤），并写出一个最小支配集、一个最大团、一个最小边覆盖、一个最大匹配。四、如果一个图中所有顶点度数都为k，则称为k正则图。8阶3正则简单图一定是平面图吗？一定不是平面图吗？为什么？五、证明：如果正则简单图G和补图G都是连通图，则G和G中至少有一个是欧拉图。六、证明：如果n阶（n3）简单图G中，对于任何1jn/2，G中度数不超过j的顶点个数都小于j，则G一定是哈密顿图。2007年期中考题一、设A,B为集合,P(A)为A的幂集,证明:P(A)P(B)当且仅当AB.二、设A={1,2,3,4},R是A上的二元关系且R={1,2,2,3,3,2,3,4}.(1)给出R的矩阵表示,画出R的关系图;(2)判断R具有哪些关系性质(自反,反自反,对称,反对称,传递);(3)求出R的自反闭包r(R),对称闭包s(R),传递闭包t(R).(用关系图表示)三、设X,Y,Z是任意集合,构造下列集合对之间的双射,并给出是双射的证明.(1)Z(XY)与(ZX)Y;(2)P(XY)与P(X)P(Y).(假设XY=)四、已知对每个自然数n,都存在唯一后继n+=n{n}.证明:对于每个非零自然数n,都存在唯一前驱n-,满足n=(n-)+.五、设f:AB是单射,g:BA是单射,证明:存在集合C,D,E,F,使得A=CD,CD=,B=EF,EF=,并且f(C)=E,g(F)=D.2007年期末考题一、化简自然数的集合表达式（注意所有运算都是集合运算）：(23).二、证明集合之间的等势关系是等价关系.三、每个奇数阶竞赛图都可既是有向欧拉图又是有向哈密顿图吗？为什么？四、完全图K4在对边进行标定的情况下有多少棵不同的生成树？为什么？画出两棵不同构的生成树，并写出其中一棵对应的基本回路系统和基本割集系统.五、计算出右图中v2到v2长度为5的回路数，并计算出全体极小支配集和全体极小点覆盖集（要写出计算过程的主要步骤）.六、求彼德森图的点色数、边色数、点连通度、边连通度，并说明理由.七、证明简单平面图中至少有一个顶点的度数不超过5.八、证明：在8×8的国际象棋棋盘的一条主对角线上移去两端1×1的方格后，所得棋盘不能用1×2的长方形恰好填满。