离散数学复习提纲.doc
《离散数学复习提纲.doc》由会员分享,可在线阅读,更多相关《离散数学复习提纲.doc(14页珍藏版)》请在三一文库上搜索。
1、集合论一、基本概念集合(set):做为整体识别的、确定的、互相区别的一些对象的总体。规定集合的三种方式:列举法、描述法、归纳法集合论的三大基本原理外延公理:两个集合A和B相等当且仅当它们具有相同的元素(无序性)概括公理:对于任意个体域U,任一谓词公式P都确定一个以该域中的对象为元素的集合S(确定性)正规公理:不存在集合A1,A2,A3,使得A3A2A1(有限可分,集合不能是自己的元素)注意:隶属、包含的判断(有时两者兼有)定理1:对于任意集合A和B,A=B当且仅当A B且B A传递性,对全集、空集的关系等定理5:空集是唯一的子集、真子集、子集个数等运算:并、交、补、差、幂集,及一些运算性质、公
2、式幂集:对任意集合A,(A)称作A的幂集,定义为:(A)=x|xA,所有子集的集合设A,B为任意集合, AAB当且仅当(A) (B)集合族:如果集合C中的每个元素都是集合,称C为集合族集合族的标志集:如果集合族C可以表示为某种下标的形,C=Sd|dD,那么这些下标组成的集合称作集合族C的标志集广义并、广义交,及相关运算性质、公式归纳定义:基础条款:规定某些元素为待定义集合成员,集合其它元素可以从基本元素出发逐步确定归纳条款:规定由已确定的集合元素去进一步确定其它元素的规则终极条款:规定待定义集合只含有基础条款和归纳条款所确定的成员基础条款和归纳条款称作“完备性条款”,必须保证毫无遗漏产生集合中
3、所有成员终极条款又称“纯粹性条款”,保证集合中仅包含满足完备性条款的那些对象例:自然数的归纳定义、数学归纳法等(建议看一下课件例子了解一下思路)二、关系有序组(二元):设a,b为任意对象,称集合族a,a,b为二元有序组,简记为称a为的第一分量,b为第二分量递归定义:n=2时,=a1,a1,a2n2时,=, an集合的笛卡儿积:对任意集合A,A2,A,A1A2称作集合A1,A2的笛卡儿积,定义如下:A1A2 = | uA1,vA2A1A2 An =(A1A2 An-1) An定理:对于任意有限集合A1,An,有|A1An|=|A1|*|An|一些运算性质关系是各个对象之间的联系和对应R称为集合A
4、1,A2,An-1到An的n元关系,如果R是A1A2An的一个子集。当A1=A2=An-1=An时,也称R为A上的n元关系几个特殊二元关系:空关系、全关系、相等关系定义:设R为A到B的二元关系(RAB)xRy表示R, xRy表示R定义域domain:Dom(R)=x|xA$y(R)R的值域range:Ran(R)=y|yB$x(R)称A为R的前域,B为R的陪域注意:前域与定义域,陪域与值域的差别。尤其是定义域与前域,与函数的差别关系表示法:集合表示法关系图表示法(有向箭头,主要是前域陪域相同的关系图)关系矩阵(mij=1当且仅当aiRbj;mij=0当且仅当aiRbj)关系相等:相同前域陪域,
5、且xy(xRyxSy)运算:要有相同前域、陪域。但总可以对关系的前域和陪域做适当的扩充,使之满足条件并(矩阵分量析取)交(矩阵分量合取)差(前一个关系和后一个关系的补矩阵做合取)补(矩阵做否定)逆运算:R=|xRy,RAB,是BA上的关系,关系矩阵转置合成:RAB,SBC,R和S的合成关系RS定义为:RS=|xAzC$y(yBxRyySz),RS AC矩阵乘法,其中乘法用合取,加法用析取幂运算:定义为自身的n次合成Rn=RR(n个R合成),R0=EA幂关系有限定理:设集合A的基数为n,R是A上的二元关系,则存在自然数i,j使得0 ij2n2,有Ri=Rj(鸽笼原理,AA有n2个元素,子集个数为
6、2n2个)自反关系:(就是每个元素都和自己有关系)x(xAxRx)关系图:每个节点都有环关系矩阵:对角线全为1反自反关系:(每个元素都和自己没关系)x(xA xRx)关系图:每个节点都没有环关系矩阵:对角线全为0对称关系:(每对关系都是相互的)xy(x,yAxRyyRx)关系图:两个节点之间有边的就有反向边关系矩阵:对称矩阵反对称关系:(若有相互关系则只能是同一个元素,不同元素间不能有相互关系)xy(x,yAxRyyRxx=y)关系图:两个节点之间只能有一条单向边关系矩阵:ci,j=1(ij)时cj,i=0传递关系:xyz(x,y,zAxRyyRzxRz)关系图:如果有边v1v2,vn-1vn
7、,则有边v1vn注意:A上的空关系是反自反的,不是自反的(此外是对称的、反对称的、传递的)如果A=,那么A上的空关系就是自反的,同时也是反自反的,因为注意定义谓词的前件xA始终为假A上的相等关系EA既是对称的,又是反对称的即对于特殊集合、关系的判断要从定义式出发,注意前件的真假R自反当且仅当EARR反自反当且仅当EARR对称当且仅当RRR反对称当且仅当RREAR传递当且仅当R2R运算的封闭性:如果关系R的某个性质经过关系运算后仍然保持,则称该性质对这个运算封闭(以上5个特性对交和求逆运算都封闭,自反对合成封闭)等价关系:等价关系R为A上的自反、对称、传递的二元关系等价类:设R为A上的等价关系,
8、对于每个aA,a的等价类记做aR(简记a),定义为:aR=x|xA xRa,a称作aR的代表元素划分:满足下列条件的集合A的子集族B(B B)(划分单元里没有空集)=A(所有划分单元合起来是全集)B B(BBBB B B=)(划分单元两两不相交)中的元素称为划分的单元特别约定A=时只有划分A上的等价关系R的所有等价类的集合,构成A的一个划分,称作等价关系R对应的划分反过来,集合A的一个划分,也对应A上的一个等价关系R,称作划分对应的等价关系等价关系和划分的一一对应划分的“粗细”概念:如果1的每一个单元都包含于2的某个单元,称1细于2,表示为12;如果12而且12 ,则表示为12,称作“真细于”
9、定理:1,2分别是等价关系R1,R2对应的划分,那么R1R2 12定理说明,越“小”(包含二元组较少)的等价关系对应越细的划分;最小的等价关系是相等关系EA;最大的等价关系是全关系划分的运算:(结合图来很好理解)积划分运算:划分1和2的积划分12是满足如下条件的划分:12细于1和2;如果某个划分细于1和2,则一定细于12;也就是说, 12是细于1和2的最粗划分(”最小公倍数”)积划分对应于等价关系交运算和划分运算:划分1和2的和划分1+2是满足如下条件的划分:1和2均细于1+2;如果有划分, 1和2均细于,则1+2细于。也就是说, 1+2是粗于1和2的最细划分(“最大公约数”)和划分不对应于等
10、价关系的并运算,而是对应于等价关系并运算结果的传递闭包二元关系R的传递闭包t(R):t(R) 是传递的,Rt(R),对于A上的任意一个具有传递性质且包含R的关系R,t(R)R商集:R是A上的等价关系,称A的划分aR|aA为A的R商集,记做A/RA/(R1R2 )=A/R1A/R2A/t(R1R2)=A/R1+A/R2序关系:R为集合A上的自反、反对称、传递的二元关系存在序关系R的集合A称作有序集(ordered set),用二元有序组表示,一般的有序集表示成哈斯图:对序关系关系图的一种简化画法由于序关系自反,各结点都有环,省去;由于序关系反对称且传递,所以关系图中任何两个不同的结点直接不会有双
11、向的边或通路,所以省去边的箭头,把向上的方向定为箭头方向由于序关系传递,所以省去所有推定的边,即ab,bc有ac,省去ac边元素排序:ab,称a先于或等于b;a小于或等于b;如果(ab),则称a,b不可比较或者不可排序最大(小)元、极大(小)元(必须是B中元素):为有序集,BAB的最小元b:bBx(xBbx)(必须比每个B的元素都小于或等于)B的最大元b:bBx(xBxb)(必须每个B的元素都比它小于或等于)B的极小元b:bB$x(xBxbxb)(比B中每个可比元都小于或等于)B的极大元b:bB$x(xBxbbx)(B中每个可比元都比它小于或等于)极大和最大的差别在于B中是否包含不可比较的元素
12、最大(小)元必为极大(小)元;最大(小)元若有则唯一;极大(小)元恒存在未必唯一上(下)界,上(下)确界(只要是A中元素):为有序集,BAB的上界a:aAx(xBxa)(必须每个B的元素都比它小于或等于)B的下界a:aAx(xBax)(必须比每个B的元素都小于或等于)B的上确界a:a是B的所有上界的集合最小元B的下确界a:a是B的所有下界的集合最大元最大(小)元是上(下)确界;属于B的上(下)界为最大(小)元;都未必存在链、反链半序关系:R为集合A上的反自反、反对称、传递的二元关系(即序关系除去每个元素与自己的关系)三、函数定义:如果X到Y的二元关系fXY,对于每个xX,都有唯一的yY,使得f
13、,则称f为X到Y的函数,记做:f:XY前域和定义域重合;单值性:ff y=yy=f(x),称x为自变元,y为函数在x处的值,y为x的像点,x为y的源点(基于映射)X时,空关系不是函数,当X时,空关系是函数,称作空函数函数的规定方法:列表法、图标法、解析法、递归定义函数相等与包含函数个数:如果|X|=m,|Y|=n,则f|f:XY的基数为nm,共有nm个X到Y的函数。X到Y的全体函数集合表示为YX定义域子集的映象:f(A)=y|$x(xAy=f(x)(即定义域的一个子集A的值域)函数合成(恩,不写了。)单射:如果任意x1x2有f(x1)f(x2)。如果f和g都是单射函数,则其合成gf也是单射函数
14、。如果gf是单射函数,则f是单射函数满射:如果任意y都有x使得y=f(x),即Ran(f)=Y。如果f和g都是满射函数,则其合成gf也是满射函数。如果gf是满射函数,则g是满射函数双射函数:如果f既是单射函数又是满射函数,称作双射函数。如果f和g都是双射函数,则其合成gf也是双射函数。如果gf是双射函数,则f是单射函数,g是满射函数逆函数:只有双射函数存在逆函数左逆函数:如果g f=EX,则称g为f的左逆函数右逆函数:如果f g=EY,则称g为f的右逆函数f可逆当且仅当f既有左逆函数,又有右逆函数,而且左逆函数和右逆函数相等图论图:由结点和联结结点的边所构成的离散结构G=结点集V(非空),边集
15、E(多重集,可以有多个相同边)有向边:结点的二元有序组表示无向边:结点的两元素多重集表示有限图:V,E都有限集重边:重数大于1的边有重边的为重图,否则为单图简单图:无环无重边的无向图完全图:任意两个不同结点间都有边,Kn孤立结点、零图(只有孤立结点)赋权图:G=,结点权函数:f:VW,边权函数:g:EW结点的度:d(v)定义为关联端点v的边的数目注意对有向图来说度d(v)=d+(v)+d-(v)度的总和为偶数,边数目的两倍;有向图出度等于入度悬挂点:一度的顶点正则图:所有顶点的度均相同的图称为正则图,按照顶点的度数k称作k-正则图,Kn是n-1正则图子图、真子图:边集结点集都必须为子集生成子图
16、:结点集相同的子图补图:结点集相同,边集交集为空,并集为完全图图的同构:可以将V1中所有的结点一一对应地置换为V2中的结点名后得到的图等于G2(同分异构体)拟路径:v1,e1,v2,e2,v3,vl-1,el-1,vl,其中ei=或者vi,vi+1,拟路径中的边数目称作拟路径的长度路径:拟路径中的边各不相同闭路径:v1=vl的路径通路:路径中的顶点各不相同回路:v1=vl的通路路径和通路定理:在有n个顶点的图G中,如果有顶点u到v的拟路径,那么u到v必有路径,并且必有长度不大于n-1的通路闭路径和回路定理:在有n个顶点的图G中,如果有顶点v到v的闭路径,那么必定有一条从v到v的长度不大于n的回
17、路可达:u=v,或者存在一条u到v的路径连通的无向图:无向图中任意两个顶点都是可达的强连通的有向图:有向图中任意两个顶点都是互相可达的单向连通的有向图:任意两个顶点,至少从一个顶点到另一个是可达的弱连通的有向图:将有向图看作无向图时是连通的连通分支:图G的连通子图G,而且G不是任何其它连通子图的真子图(最大性)欧拉图:如果图G上有一条经过所有顶点、所有边的闭路径(允许顶点重复) 无向图:G连通,所有顶点的度都是偶数 有向图:G弱连通,每个顶点的出度与入度相等欧拉路径:如果图G上有一条经过所有顶点、所有边的路径(非闭)(允许顶点重复) 无向图:G连通,恰有两个顶点的度是奇数 有向图:G连通,恰有
18、两个顶点出度与入度不相等,其中一个出度比入度多1,另一个入度比出度多1哈密顿图:如果图G上有一条经过所有顶点的回路(不要求经过所有边)哈密顿通路:如果图G上有一条经过所有顶点的通路(非回路)判定定理(充分非必要):如果具有n个顶点的图G的每一对顶点的度数之和都不小于n-1,那么G中有一条哈密顿通路。如果G的每一对顶点度数之和不小于n,且n=3,则G为一哈密顿图邻接矩阵:无重边的有向图G=,其邻接矩阵AG定义为,aij=1, 当E,aij=0, 当E注意:与关系矩阵的联系。拟路径,邻接矩阵自乘L次:AL,则乘积结果矩阵中每个分量aij(L)的含义为G中顶点vi到vj的长度为L的拟路径条数路径矩阵
19、B=A A(2) A(3) A(|V|),其中A(m)=A A AB的每个分量bij表示vi到vj是否有路径可达性矩阵:P=I B,加上顶点的自身可达性关联矩阵(简单无向图):表示顶点和边的关联关系,n*m矩阵。通过矩阵的秩来判定图的连通分支个数二分图:满足如下条件的无向图G=有非空集合X,Y, X Y=V, X Y= 每个vi,vjE,都有viXvjY或者viYvjX可以用G=表示二分图bipartite graph如果X,Y中任意两个顶点之间都有边,则称为完全二分图。记作K|X|,|Y|二分图的等价条件:G至少要有两个顶点,而且G中所有回路的长度都是偶数匹配:将E的子集M称作一个匹配,如果
20、M中的任意两条边都没有公共端点。边数最多的匹配称作最大匹配。如果X(Y)中的所有的顶点都出现在匹配M中,则称M是X(Y)-完全匹配。如果M既是X-完全匹配,又是Y-完全匹配,称M是完全匹配*匈牙利算法:任取一个匹配,取非饱和点走交错路(边交替属于不属于已有匹配),若终点是非饱和点,则令匹配为原匹配和增广路的(即属于这两个集合但不属于交集部分);若终点是饱和点,则将起点去掉不再考虑(我猜不会考)平面图:如果无向图G可以在一个平面上图示出来,并且各边仅在顶点处相交,称作平面图。K5和K3,3都不是平面图,K5是顶点数最少的非平面图,K3,3是边数最少的非平面图平面图等价条件:G或者G的子图作任何同
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 复习 提纲
链接地址:https://www.31doc.com/p-913998.html