您好,欢迎访问三七文档
当前位置:首页 > 财经/贸易 > 资产评估/会计 > 北大集合论与图论往年考题
2008年期中考题:一、用真值表证明德*摩根律(证明其中一条即可)。二、设A,B,C是集合,试问在什么条件下(A-B)-C=A-(B-C)?给出证明。三、设A={a,b,c},问A上有多少种不同的:二元关系?自反关系?对称关系?传递关系?等价关系?偏序关系?良序关系?四、用花括号和空集来表示12(注意表示集合的叉乘).五、设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阶(n3)简单图G中,对于任何1jn/2,G中度数不超过j的顶点个数都小于j,则G一定是哈密顿图。2007年期中考题一、设A,B为集合,P(A)为A的幂集,证明:P(A)P(B)当且仅当AB.二、设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(XY)与(ZX)Y;(2)P(XY)与P(X)P(Y).(假设XY=)四、已知对每个自然数n,都存在唯一后继n+=n{n}.证明:对于每个非零自然数n,都存在唯一前驱n-,满足n=(n-)+.五、设f:AB是单射,g:BA是单射,证明:存在集合C,D,E,F,使得A=CD,CD=,B=EF,EF=,并且f(C)=E,g(F)=D.2007年期末考题一、化简自然数的集合表达式(注意所有运算都是集合运算):(23).二、证明集合之间的等势关系是等价关系.三、每个奇数阶竞赛图都可既是有向欧拉图又是有向哈密顿图吗?为什么?四、完全图K4在对边进行标定的情况下有多少棵不同的生成树?为什么?画出两棵不同构的生成树,并写出其中一棵对应的基本回路系统和基本割集系统.五、计算出右图中v2到v2长度为5的回路数,并计算出全体极小支配集和全体极小点覆盖集(要写出计算过程的主要步骤).六、求彼德森图的点色数、边色数、点连通度、边连通度,并说明理由.七、证明简单平面图中至少有一个顶点的度数不超过5.八、证明:在8×8的国际象棋棋盘的一条主对角线上移去两端1×1的方格后,所得棋盘不能用1×2的长方形恰好填满。
本文标题:北大集合论与图论往年考题
链接地址:https://www.777doc.com/doc-4766933 .html