离散数学总复习

离散数学总复习离散数学总复习n1.主范式、集合、布尔格主范式、集合、布尔格(有补分配格有补分配格)运算运算n2.命题符号化命题符号化+命题命题/谓词逻辑推理谓词逻辑推理n3.前束范式前束范式n4.元素与集合、集合与集合的关系元素与集合、集合与集合的关系(判断判断,证明证明)n5.排列组合、容斥原理、递推方程排列组合、容斥原理、递推方程n6.关系合成、函数复合、置换乘法关系合成、函数复合、置换乘法n7.等价关系等价关系(等价类、商集、划分、自然映射等价类、商集、划分、自然映射)n8.偏序集偏序集(偏序关系、覆盖、哈斯图偏序关系、覆盖、哈斯图)、格、格n9.同构同构=同态同态双射双射n10.代数系统及其性质代数系统及其性质(判断判断)n11.域域=整环整环除环除环n0.重要概念重要概念:幂集幂集,笛卡积笛卡积,闭包闭包,积代数积代数,循环群循环群;0.重要概念重要概念:生成子图生成子图,自补图自补图,自对偶图自对偶图,割集割集n12.握手定理握手定理n13.邻接矩阵邻接矩阵n14.最短路径最短路径(标号法标号法)与与关键路径关键路径(最长路径最长路径)n15.图的类型图的类型(二部二部,欧拉欧拉,哈密顿哈密顿,平面平面,树树)判别判别n16.平面图欧拉公式：平面图欧拉公式：n m+r=2n17.树的重要性质：树的重要性质：m=n-1n18.最小生成树最小生成树(避圈法避圈法)、基本回路、基本回路/割集系统割集系统n19.Huffman算法算法(最优二元树最优二元树/最佳前缀码最佳前缀码)n20.二二/多项式定理与组合恒等式多项式定理与组合恒等式n21.分治算法的常用递推公式分治算法的常用递推公式第第1章章 命题逻辑命题逻辑1.1命题符号化及联结词（联结词是基础）命题符号化及联结词（联结词是基础）1.2命题公式及分类命题公式及分类1.3等值演算等值演算1.4联结词全功能集联结词全功能集1.5对偶与范式（主范式演算是重点）对偶与范式（主范式演算是重点）1.6推理理论（重点）推理理论（重点）联结词与复合命题联结词与复合命题(小结小结)n联结词优先级:(),n同级按从左到右的顺序进行p q p pq pq pq pq0010011011011010001001101111基本复合命题的真值基本复合命题的真值1.3命题逻辑等值演算命题逻辑等值演算等值式等值式定义定义：(AB1)(AB)（重点）（重点）基本等值式基本等值式(重点重点)双重否定律双重否定律:AA等幂律等幂律：A AA,A AA交换律交换律:A BB A,A BB A结合律结合律:(A B)CA(B C)(A B)CA(B C)分配律分配律:A(B C)(A B)(A C)A(B C)(A B)(A C)德德摩根律摩根律:(A B)AB(A B)AB基本等值式基本等值式（续）吸收律吸收律:A(A B)A,A(A B)A零律零律:A 11,A 00同一律同一律:A 0A,A 1A排中律排中律:AA1矛盾律矛盾律:AA0蕴涵等值式蕴涵等值式:ABA B等价等值式等价等值式:AB(AB)(BA)假言易位假言易位:ABBA等价否定等值式等价否定等值式:ABAB归谬论归谬论:(AB)(AB)A1.4复合联结词（重要的非重点）复合联结词（重要的非重点）与非式与非式:p q(p q)；或非式或非式:p q(p q)习题习题1.14，1.10(4)(5)异或：异或：p q p q(pq)pq pqnAp1 p2 pn,偶数个命题变项赋值为偶数个命题变项赋值为1 (A(A0),奇数个命题变项赋值为奇数个命题变项赋值为1(A(A1);nBq1q2qn,偶数个命题变项赋值为偶数个命题变项赋值为0(A(A1),奇数个命题变项赋值为奇数个命题变项赋值为0(A(A0).n习题习题1.221.5主范式（重点）主范式（重点）n成真赋值成真赋值i对应主析取范式的极小项对应主析取范式的极小项mi；n成假赋值成假赋值j对应主合取范式的极大项对应主合取范式的极大项Mj。n命题公式有几个成真赋值，主析取范式就是几命题公式有几个成真赋值，主析取范式就是几个极小项相或个极小项相或()；n命题公式有几个成假赋值，主合取范式就是几命题公式有几个成假赋值，主合取范式就是几个极大项相与个极大项相与()。例。例1.31，1.32n分配律分配律BjBj(pi pi)(Bj pi)(Bj pi)nBjBj(pi pi)(Bj pi)(Bj pi)n习题习题1.12(1),1.13(1)。五。五71.6 命题逻辑推理（重点）命题逻辑推理（重点）“推理正确推理正确”定义定义：(AB1)(AB)（重点）（重点）A(A B)附加律附加律(A B)A化简律化简律(AB)AB假言推理假言推理(AB)B A拒取式拒取式(A B)BA析取三段论析取三段论(AB)(BC)(AC)假言三段论假言三段论(AB)(BC)(AC)等价三段论等价三段论(AB)(CD)(A C)(B D)构造性二难构造性二难(AB)(AB)(AA)B构构造造性性二二难难(特特殊殊形形式式)(AB)(CD)(BD)(AC)破坏性二难破坏性二难习题习题1.18,1.21,1.17(2)。六。六1注意事项注意事项1：命题：命题只有能确定真假(但不能可真可假)的陈陈述述句句才是命命题题.不管是正确的观点,还是错误的观点,都是命题.猜想猜想和预言预言是命题,如哥德巴赫猜想.感叹句,祈使句,疑问句都不是命题.陈述句中的悖悖论论以及判断结果不惟一确定的也不是命题.有些简单命题貌似复合命题,要注意区分.题1(15)注意事项注意事项2：蕴涵联结词蕴涵联结词“”pq 的逻辑关系:p为q的充分条件，q为p的必要条件.“如果p,则q”的多种表述方式：(1)若p,就q.(2)只要p,就q.(3)p仅当q.(4)只有q 才p.(5)除非q,才p.(6)除非q,否则非p.pq为假当且仅当为假当且仅当p 为真为真q 为假，即为假，即当p为假时，pq为真(不管q为真,还是为假);当q为真时，pq为真(不管p为真,还是为假).习题习题1.5(6)(7)了解概念、掌握方法n真值表、命题公式类型真值表、命题公式类型n所有等值的含所有等值的含n个命题变项的公式对应同一个命题变项的公式对应同一个个n元真值函数元真值函数F:0,1n0,1；哑元n最小联结词组最小联结词组n对偶式与对偶原理对偶式与对偶原理n简单析取式、简单合取式简单析取式、简单合取式n析取范式与合取范式析取范式与合取范式n附加前提证明法、附加前提证明法、反证法反证法第第2章章一阶逻辑一阶逻辑2.1一阶逻辑基本概念（量词是关键）一阶逻辑基本概念（量词是关键）2.2一阶逻辑公式、解释及分类一阶逻辑公式、解释及分类2.3一阶逻辑等值式、前束范式（重点）一阶逻辑等值式、前束范式（重点）2.4一阶逻辑推理理论（重点）一阶逻辑推理理论（重点）一阶逻辑与命题逻辑关系一阶逻辑与命题逻辑关系n一阶逻辑将命题一阶逻辑将命题(公式公式)拆分为个体词、谓词、拆分为个体词、谓词、量词量词(、)。谓词是核心，没有谓词，不。谓词是核心，没有谓词，不构成命题；量词是关键。构成命题；量词是关键。n个体词（元素）个体词（元素）分为分为个体常项个体常项和和个体变项个体变项.个体域（集合）个体域（集合）:个体变项的取值范围个体变项的取值范围.全总个体域全总个体域:宇宙间一切事物组成宇宙间一切事物组成n一阶逻辑一阶逻辑命题逻辑命题逻辑+量词量词n xF(x)x F(x),xF(x)x F(x);n xF(x)x F(x),xF(x)x F(x)2.3一阶逻辑等值式一阶逻辑等值式基本等值式基本等值式（重点）（重点）:命题逻辑中命题逻辑中16组基本等值式的代换实例组基本等值式的代换实例消去量词等值式消去量词等值式设设D=a1,a2,an xA(x)A(a1)A(a2)A(an)xA(x)A(a1)A(a2)A(an)量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式x(A(x)B)xA(x)Bx(A(x)B)xA(x)B x(A(x)B)xA(x)Bx(BA(x)BxA(x)量词分配等值式量词分配等值式 x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)x(A(x)B)xA(x)Bx(A(x)B)xA(x)B x(A(x)B)xA(x)Bx(BA(x)BxA(x)注意事项注意事项1：前束范式：前束范式（重点）（重点）n设设A为一个一阶逻辑公式为一个一阶逻辑公式,若若A具有如下形式具有如下形式Q1x1Q2x2QkxkB,则称则称A为为前束范式前束范式,其中其中Qi(1 i k)为为 或或，B为不含量词的公式为不含量词的公式.n1）对对 无分配律，无分配律，对对 无分配律无分配律n xA(x)xB(x)x y(A(x)B(y)n x y(A(x)B(y)xA(x)xB(x)n2）变量冲突，有一个要换名）变量冲突，有一个要换名.n3）x(A(x)B)xA(x)B x(A(x)B)xA(x)Bn习题习题2.21,2.15(1),2.14(1)。四。四102.4一阶逻辑推理理论（重点）一阶逻辑推理理论（重点）n重要的推理定律重要的推理定律第一组第一组命题逻辑推理定律代换实例命题逻辑推理定律代换实例第二组第二组由基本等值式生成（由基本等值式生成（置换规则）置换规则）第三组第三组 xA(x)xB(x)x(A(x)B(x)x(A(x)B(x)xA(x)xB(x)(12)全称量词消去规则（简记为UI规则或UI）(13)全称量词引入规则（简记为UG规则或UG）(14)存在量词引入规则（简记为EG规则或EG）(15)存在量词消去规则（简记为EI规则或EI）注注:必须先消去存在量词,后消去全称量词.七1第三版第三版:习题习题2.22,2.16,2.19,2.17(1),2.23；例；例2.18注意事项2：一阶逻辑中命题符号化一阶逻辑中命题符号化无特别要求，用全总个体域无特别要求，用全总个体域量词顺序一般不要随便颠倒量词顺序一般不要随便颠倒 x yA(x,y)y xA(x,y)全称量词全称量词 一般对应一般对应“”存在量词存在量词 一般对应一般对应“”习题习题2.3(2)(5)(6)了解有有限限个个体体域域,无无限限个个体体域域;谓谓词词常常项项,谓谓词词变变项项,一一元元谓谓词词,多元谓词多元谓词(n元谓词元谓词,n 2),0元谓词元谓词,原子公式原子公式;项项字字母母表表包包含含：1)个个体体常常项项,2)个个体体变变项项,3)函函数数符符号号,4)谓谓词词符符号号,5)量量词词符符号号(,),6)联联结结词词符符号号(,),7)括号与逗号括号与逗号.指导变元指导变元，辖域辖域，约束出现约束出现，自由出现自由出现闭式闭式:不含自由出现的个体变项的公式不含自由出现的个体变项的公式.解释解释I包含：包含：(a)非空个体域非空个体域DI,(b)DI中一些特定元素中一些特定元素集集,(c)DI上特定函数集上特定函数集,(d)DI上特定谓词集上特定谓词集.n闭式在任何解释下都是命题，闭式在任何解释下都是命题，n不是闭式的公式在某些解释下也可能是命题不是闭式的公式在某些解释下也可能是命题.公式类型公式类型.换名规则与代替规则换名规则与代替规则第第3章章集合的基本概念和运算集合的基本概念和运算n3.1集合的基本概念集合的基本概念n3.2集合的基本运算（重点）集合的基本运算（重点）n3.3集合中元素的计数（容斥原理是重点）集合中元素的计数（容斥原理是重点）3.1集合的基本概念集合的基本概念n元素x与集合A的关系：属于属于x A，不属于不属于x An集合A与集合B的关系：习题习题3.2,3.8,3.12,3.16包含包含(子集子集)A B,不包含不包含A B 相等相等A=B,不相等不相等A B 真包含真包含A B,不真包含不真包含A Bn重要概念：重要概念：集合A的幂集的幂集P(A)=x|x A。如果如果|A|=n，则，则|P(A)|=2n.习题习题3.14(4),3.18n习题习题3.3,3.9,3.113.2集合的基本运算（重点）集合的基本运算（重点）集合运算符集合运算符，分别对应分别对应联结词联结词,，A B=A B=A(A B)A B=(A B)(B A)=(A B)(A B)A B A A BA BA B=BA B=A A B=A B=A B=A习题习题3.17,3.16；例；例3.17，3.18。四。四3，4；六；六4集合运算的集合运算的文氏图表示文氏图表示习题习题3.4,3.15(2)集合运算的算律集合运算的算律（重点）（重点）交交换换A B=B AA B=B AA B=B A结结合合(A B)C=A(B C)(A B)C=A(B C)(A B)C=A(B C)幂幂等等A A=AA A=A 与与 与与 分配分配A(B C)=(A B)(A C)A(B C)=(A B)(A C)A(B C)=(A B)(A C)吸收吸收A(A B)=AA(A B)=A吸收律的前提：吸收律的前提：、可交换可交换集合运算的算律集合运算的算律（续）D.M 律律A(B C)=(A B)(A C)A(B C)=(A B)(A C)(B C)=BC(B C)=BC双重否定双重否定A=AE补补元律元律AA=AA=E零律零律A=A E=E同一律同一律A=AA E=A否定否定=E E=3.3集合中元素的计数集合中元素的计数容斥原理及其推论（重点）容斥原理及其推论（重点）习题习题3.6,3.18,3.19。五。五10注意1）0是自然数是自然数.2）对于任何集合）对于任何集合A 和元素和元素x(可以是集合可以是集合)，x A和和x A两者成立其一，且仅成立其两者成立其一，且仅成立其一一.3）和和 是不同层次的问题是不同层次的问题.4）空集）空集是任何集合的子集是任何集合的子集.5）在给定问题中，全集）在给定问题中，全集E包含任何集合，即包含任何集合，即 A(A E)了解概念、掌握方法了解概念、掌握方法n1）集合的表示法：）集合的表示法：列元素法列元素法A=a,b,c,dn谓词表示法谓词表示法B=x|P(x).习题习题3.10(4)n2）文氏图与文氏图法）文氏图与文氏图法.习题习题3.6n3）集合）集合A的基数的基数cardA=|A|=nn4）证明）证明 X Yq命题演算法命题演算法q包含传递法包含传递法q等价条件法等价条件法q反证法反证法q并交运算法并交运算法n5）证明）证明X=Yq命题演算法命题演算法q等式代入法等式代入法q反证法反证法q运算法运算法第第4章章二元关系与函数二元关系与函数n4.1集合的笛卡儿积与二元关系集合的笛卡儿积与二元关系n4.2关系的运算（重点）关系的运算（重点）n4.3关系的性质（基础）关系的性质（基础）n4.4关系的闭包关系的闭包n4.5等价关系和偏序关系（重点）等价关系和偏序关系（重点）n4.6函数的定义和性质函数的定义和性质n4.7函数的复合和反函数函数的复合和反函数4.1集合的笛卡儿积和二元关系集合的笛卡儿积和二元关系n1）重要概念：集合集合A与与B 的的笛卡儿积笛卡儿积A B=|x A y B.若若|A|=m,|B|=n,则则|A B|=mnn分配律分配律A(B C)=(A B)(A C)n(B C)A=(B A)(C A)nA(B C)=(A B)(A C)n(B C)A=(B A)(C A)nA=B=n(A C=B D)(A,B,C,D非空非空)(A=B)(C=D)n2）从）从A到到B的二元关系的二元关系R A B.AB的子集有的子集有2mn 个，个，所以所以A到到B有有2mn个不同的二元关系个不同的二元关系.n注：笛卡儿积注：笛卡儿积不适合交换律不适合交换律和和结合律结合律.n如如R,可记作可记作xRy.A上重要关系上重要关系n从从A到到A的二元关系的二元关系叫做叫做A上的二元关系上的二元关系.n空关系空关系是是A 上的关系上的关系n全域关系全域关系EA=|xAyA=AA恒等关系恒等关系IA=|xAn小于等于关系小于等于关系LA=|x,yAxy,A Rn整除关系整除关系DA=|x,yAx整除整除y,A Zn包含关系包含关系R=|x,yAx y,A是集合族是集合族.n类似的还可以定义大于等于关系类似的还可以定义大于等于关系,小于关系小于关系,大大于关系于关系,真包含关系等等真包含关系等等.4.2关系的运算关系的运算n逆逆R 1=|Rn合成合成R S=|y(S R)n(1)(F G)H=F(G H)n(2)(F G)1=G 1 F 1.n幂运算幂运算(1)R0=|xA=IAn (2)Rn+1=Rn Rn习题习题4.13。五。五14.3关系的性质（基础，重中之重）关系的性质（基础，重中之重）n(1)若若 xA,R,则称则称R在在A上是上是自反自反的的.n(2)若若 xA,R,称称R在在A上是上是反自反反自反的的.n(3)若若 x y(x,yARR),则称则称R为为A上上对称对称的关系的关系.n(4)若若 x,yA,RRx=y,则则称称R为为A上的上的反对称反对称关系关系.n(5)若若 x,y,zA,RRR,则称则称R是是A上的上的传递传递关系关系.n习题习题4.4关系性质判别关系性质判别自反自反反自反反自反对称对称反对称反对称传递传递表达式表达式 IA RRIA=R=R 1RR 1 IA R R R关系关系矩阵矩阵主对主对角线角线元素元素全是全是1主对角主对角线元素线元素全是全是0矩阵是对称矩阵是对称矩阵矩阵若若rij1,且且ij,则则rji0对对M2中中1所在位置所在位置,M中相应中相应位置都是位置都是1关系图关系图 每个每个顶点顶点都有都有环环每个顶每个顶点都没点都没有环有环如果两个顶如果两个顶点之间有边点之间有边,是一对方是一对方向相反的边向相反的边(无单边无单边)如果两点如果两点之间有边之间有边,是一条有是一条有向边向边(无双无双向边向边)如果顶点如果顶点 xi 连通到连通到xk,则从则从 xi到到 xk 有边有边恒等关系恒等关系IA既是等价关系既是等价关系,又是篇序关系。又是篇序关系。运算与性质的关系（了解）运算与性质的关系（了解）自反自反性性反自反反自反性性对对称称性性反反对对称称性性传递传递性性R1 1R1R2R1R2R1 R2R1 R24.5等价关系和偏序关系（重点）等价关系和偏序关系（重点）n(1)等价关系、等价类、商集、划分、等价关系、等价类、商集、划分、自然映射自然映射n等价关系等价关系:同时满足自反、对称和传递的关系同时满足自反、对称和传递的关系.n若若等价关系等价关系R,称称x 等价于等价于y,记做记做xy.nx(xA)关于集合关于集合A上等价关系上等价关系R 的的等价类等价类xR=y|yAxRy.n以集合以集合A上的等价关系上的等价关系R的所有等价类为元素的的所有等价类为元素的集合称为集合称为A关于关于R的的商集商集,记做记做A/R.n商集商集A/R 就是就是A 的一个划分的一个划分;n等价关系与商集、划分一一对应等价关系与商集、划分一一对应.n习题习题4.5，4.15，4.24。五。五2；六；六14(2)偏序关系偏序关系,覆盖覆盖,偏序集与哈斯图偏序集与哈斯图n偏序关系偏序关系：同时满足自反、反对称和传递的关：同时满足自反、反对称和传递的关系系,记作记作.如果如果偏序关系偏序关系,则记作则记作x y.nx y且不存在且不存在z A 使得使得x z y,则称则称y 覆盖覆盖x.n集合集合A和和A上的偏序关系上的偏序关系 一起叫做一起叫做偏序集偏序集,记作记作.习题习题4.6，4.16。五。五3n哈斯图哈斯图：简化关系图。特点（注意）：每个结：简化关系图。特点（注意）：每个结点没有环，位置低的元素的顺序在前，具有覆点没有环，位置低的元素的顺序在前，具有覆盖关系的两个结点之间才连边盖关系的两个结点之间才连边.n特定元素：区分最小特定元素：区分最小(大大)元与极小元与极小(大大)元；元；n下界、上界、下确界、上确界下界、上界、下确界、上确界注意事项注意事项：特定元素：特定元素n对于有穷集，极小元和极大元必存在，可能存在多个对于有穷集，极小元和极大元必存在，可能存在多个.n最小元和最大元不一定存在，如果存在一定惟一最小元和最大元不一定存在，如果存在一定惟一.n最小元一定是极小元最小元一定是极小元;最大元一定是极大元最大元一定是极大元.反之不对反之不对.n孤立结点既是极小元，也是极大元孤立结点既是极小元，也是极大元.n下界、上界、下确界、上确界不一定存在下界、上界、下确界、上确界不一定存在.n下界、上界存在不一定惟一下界、上界存在不一定惟一.n下确界、上确界如果存在，则惟一下确界、上确界如果存在，则惟一.n集合的最小元就是它的下确界，最大元就是它的上确集合的最小元就是它的下确界，最大元就是它的上确界；反之不对界；反之不对.4.6函数函数n xdomF 都存在都存在唯一唯一的的yranF 使使xFy 成成立立,则称二元关系则称二元关系F 为为函数函数.对于函数对于函数F,如果如果有有xFy,则记作则记作y=F(x),并称并称y 为为F 在在x 的的值值.n所有从所有从A 到到B 的函数的集合记作的函数的集合记作BA,读作读作“B上上A”，符号化表示为，符号化表示为BA=f|f：AB n函数函数f：AB，domF=A，|f|=|A|，ranF B.n计数：计数：|A|=m,|B|=n,且且m,n0,|BA|=nm.nB=.A,则则A=.n恒等函数恒等函数IA(x)=xn习题习题4.22了解n有序对有序对，有序有序n元组元组.n关系矩阵、关系图关系矩阵、关系图;关系的关系的定义域定义域、值域值域和和域域.习题习题4.2关系关系F 在集合在集合A上的上的限制限制F A=|xFy x A F.A在在F下的下的像像FA=ran(F A)ranF.习题习题4.3R的自反闭包的自反闭包r(R)=RR0,对称闭包对称闭包s(R)=RR 1,传递闭传递闭包包t(R)=RR2R3。习题。习题4.14nMr=M+E，Ms=M+M，Mt=M+M2+M3+n(不不)可比。可比。全序全序(线序线序)关系关系：所有元素可比；良序集：所有元素可比；良序集n单射单射,满射满射,双射；双射；常函数、单调函数；特征函数常函数、单调函数；特征函数.ng(a)=a是从是从A 到商集到商集A/R 的的自然映射自然映射.习题习题4.10,4.18n函数复合与反函数函数复合与反函数n良序集良序集：任意非空子集都有最小元素的全序集任意非空子集都有最小元素的全序集第第5章章代数系统的一般性质代数系统的一般性质n5.1二元运算及其性质（基础）二元运算及其性质（基础）n5.2代数系统及其子代数和积代数代数系统及其子代数和积代数n（重要概念积代数）（重要概念积代数）n5.3代数系统的同态与同构（重点）代数系统的同态与同构（重点）5.1一、二元运算一、二元运算,代数系统代数系统,封闭性封闭性n函数函数f：SSS 称为集合称为集合S 上的二元运算上的二元运算,也称也称S 对对f 封闭封闭;即即 x,yS,f(x,y)S.n函数函数f：SS 称为集合称为集合S 上的一元运算上的一元运算;即即 xS,f(x)S.n函数的性质：运算结果唯一性运算结果唯一性.n非空集合非空集合S 和和S 上上k 个一元或二元运算个一元或二元运算f1,f2,fk 组成的系统称为一个组成的系统称为一个代数系统代数系统,简简称称代数代数，记做，记做 V=.n习题习题5.8，5.7二元运算可能的性质二元运算可能的性质n x,y,zS(1)交换律交换律：x y=y x.n(2)结合律结合律：(x y)z=x (y z).n(3)幂等律幂等律：x x=x.n(4)消去律消去律：若：若x y=x z,且且x不是零元不是零元,则则y=z;若若y x=z x,且且x 不是零元不是零元，则，则y=z.无零因子无零因子：(x y=x=y=)消去律消去律.n(1)运算对运算对 运算满足运算满足分配律分配律：z (x y)=(z x)(z y).n(2)和和 运算满足运算满足吸收律吸收律(前提前提 和和 都可交换都可交换)：x (x y)=x；x (x y)=x.一些二元运算的性质一些二元运算的性质集合集合运算运算交交换换律律结结合律合律 幂幂等律等律消去律消去律Z,Q,R,C普通加法普通加法+有有有有无无有有普通乘法普通乘法 有有有有无无有有Mn(R)矩矩阵阵加法加法+有有有有无无有有矩矩阵阵乘法乘法 无无有有无无无无P(B)0,1并并(或或)有有有有有有无无交交(与与)有有有有有有无无对对称差称差(,)有有有有无无有有AA函数复合函数复合 无无有有无无无无Zn模乘模乘 有有有有无无无无Z+lcm,gcd有有有有有有无无0,1与非与非,或非或非 有有无无无无无无一些二元运算的性质一些二元运算的性质集合集合运算运算分配律分配律吸收律吸收律Z,Q,R,CMn(R)普通加法普通加法+与乘法与乘法 矩矩阵阵加法加法+与乘法与乘法 对对+可分配可分配无无+对对 不分配不分配 P(B)0,1并并 与交与交(或或和与和与)对对 可分配可分配有有 对对 可分配可分配交交 与与对对称差称差(与与和排斥或和排斥或)对对 可分配可分配无无 对对 不分配不分配Zn模加 与与模乘模乘 对对 可分配可分配无 对对 不分配不分配全集全集E并并 与笛卡儿与笛卡儿积积 对对 可分配可分配无无交交 与笛卡儿与笛卡儿积积 对对 可分配可分配Z+lcm与与gcd有有有有二元运算可能的特异元素二元运算可能的特异元素n xS,(e x=x)(x e=x),称称e为为单位元单位元(幺元幺元)(惟一性惟一性).xS,(x=)(x =),称称是是零元零元(惟一性惟一性).注注:只有左或右单位元只有左或右单位元(零元零元),不称为有单位元不称为有单位元(零元零元).n(y x=e)(x y=e),称称y为为x的的逆元逆元,并称并称x是是可可逆逆元素元素.注注:逆元的存在以幺元的存在为前提逆元的存在以幺元的存在为前提.ne-1=e.对于可结合的二元运算对于可结合的二元运算,可逆元素可逆元素x只只有惟一的逆元有惟一的逆元,记作记作x 1.n习题习题5.14，5.15，5.3，5.12，5.2一些二元运算的特异元素一些二元运算的特异元素集合集合运算运算幺元幺元e零元零元逆元逆元x-1(e-1=e)Z,Q,R,C普通加法普通加法+0无无 x普通乘法普通乘法 101/x(x0)Mn(R)矩矩阵阵加法加法+0阵阵无无 x矩矩阵阵乘法乘法 单单位位阵阵In0阵阵x 1(逆逆阵阵,x可逆可逆)P(B)0,1并并(或或)(0)B(1)-1=(0-1=0)交交(与与)B(1)(0)B-1=B(1-1=1)()(0)无无xAA函数复合函数复合 IA无无双射逆元双射逆元=反函数反函数Zn模乘模乘 10 x,n互互质质,x有逆元有逆元模加 0无无n x(0-1=0)Z+lcm1无无1-1=1gcd无无1无无0,1等价等价1无无x由运算表判别算律的一般方法由运算表判别算律的一般方法n交换律：运算表关于主对角线对称交换律：运算表关于主对角线对称n幂等律：主对角线元素排列与表头顺序一致幂等律：主对角线元素排列与表头顺序一致n消去律：所在的行与列中没有重复元素消去律：所在的行与列中没有重复元素n单位元单位元:所在行与列的元素排列都与表头一致所在行与列的元素排列都与表头一致n零元：元素的行与列都由该元素自身构成零元：元素的行与列都由该元素自身构成nA 的可逆元：的可逆元：a 所在的行中某列所在的行中某列(比如第比如第j 列列)元素为元素为e，且第，且第j 行行 i 列的元素也是列的元素也是e，那么，那么a与第与第j 个元素互逆个元素互逆n结合律：除了单位元、零元之外，要对所有结合律：除了单位元、零元之外，要对所有3个元素的组合验证表示结合律的等式是否成立个元素的组合验证表示结合律的等式是否成立n习题习题5.1，5.95.2代数系统及其子代数和积代数代数系统及其子代数和积代数n重要概念：重要概念：和和是代数系统，是代数系统，积代数积代数有有：=.题题5.10(1)若若o和和 运算是可交换的，那么运算是可交换的，那么运算也是可交运算也是可交换的的(2)若若o和和 运算是可结合的，那么运算是可结合的，那么运算也是可运算也是可结合的合的(3)若若o和和 运算是幂等的，那么运算是幂等的，那么运算也是运算也是幂等的等的(4)若若 o 和和 运算分别具有单位元运算分别具有单位元 e1和和e2，那么，那么运算运算也具有也具有单位元位元(5)若若o和和 运算分别具有零元运算分别具有零元 1和和 2，那么，那么运算运算也具有零元也具有零元(6)若若x 关于关于 o 的逆元为的逆元为x 1,y 关于关于 的逆元为的逆元为y 1，那，那么么关于关于运算也具有逆元运算也具有逆元5.3代数系统的同态与同构代数系统的同态与同构(重点重点)nV1=和和V2=是代数系统是代数系统,f:S1S2,x,yS1,f(x y)=f(x)f(y),则称则称f为为V1到到V2的的同态同态(映射映射).n如果同态如果同态f是满射，则称为是满射，则称为满同态满同态，这时称，这时称V2是是V1的的同态像同态像，记作，记作V1 V2；n如果同态如果同态f是双射，则称为是双射，则称为同构同构，记作，记作V1 V2.n习题习题5.6，5.5。六。六13，15满同态保持运算的算律及特异元素满同态保持运算的算律及特异元素V1=和和V2=是代数系统是代数系统，f：V1V2是是满同同态，那么，那么(1)若若o运算是可交运算是可交换的（可的（可结合、合、幂等的），等的），则o运算运算也是可交也是可交换的（可的（可结合、合、幂等的）等的）.(2)若若o运算运算对 运算是可分配的，运算是可分配的，则o运算运算对 运算也是运算也是可分配的；若可分配的；若o 和和 运算是可吸收的，运算是可吸收的，则o和和 运算也运算也是可吸收的。是可吸收的。(3)若若e为o 运算的运算的单位元，位元，则f(e)为o运算的运算的单位元位元.(4)若若 为o 运算的零元，运算的零元，则f()为o运算的零元运算的零元.(5)设u V1，若，若u 1是是 u关于关于o运算的逆元，运算的逆元，则f(u 1)是是 f(u)关于关于o运算的逆元。运算的逆元。注意事项注意事项n1）集合集合S 上的二元运算就是上的二元运算就是SSS的二元函的二元函数数.集合集合S 上的一元运算就是上的一元运算就是SS的一元函数的一元函数.n2）e-1=e.当当|S|2，单位元与零元是不同的，单位元与零元是不同的，零元无逆元；当零元无逆元；当|S|=1时，这个元素既是单位时，这个元素既是单位元也是零元元也是零元.n3）子代数）子代数B 和原代数和原代数S 含有相同的代数常数含有相同的代数常数n4）同态映射保持运算的算律及特异元素）同态映射保持运算的算律及特异元素仅在仅在满同态时成立，如果不是满同态，那么相关性满同态时成立，如果不是满同态，那么相关性质在同态像中成立质在同态像中成立.n同态映射不一定能保持消去律成立同态映射不一定能保持消去律成立.了解n运算表n代数系统的代数系统的载体载体，成分，代数常数，成分，代数常数n同类型与同种代数系统同类型与同种代数系统n子代数和原代数是同种的代数系统子代数和原代数是同种的代数系统n最大的子代数最大的子代数就是就是V 本身本身.代数常数代数常数(对运对运算封闭算封闭)构成构成最小的子代数最小的子代数.最大和最小子代最大和最小子代数称为数称为平凡的子代数平凡的子代数.真子代数真子代数.习题习题5.4n零同态零同态、单单(自自)同态同态、(满满)自同态自同态和和自同构自同构.第第6章章几个典型的代数系统几个典型的代数系统n6.1半群与群半群与群n6.2环与域（环与域（“域域”是重点）是重点）n6.3格与布尔代数（格与布尔代数（“布尔代数布尔代数”是重点）是重点）6.1(半半)群群|S|2封闭性结合律含幺所有元有逆元交换律=az消去律含零代数系统半群交换半群独异点群Abel群循环群重要概念：循环群，重要概念：循环群，n元置换群。元置换群。(半半)群群实例实例(1),交换半群交换半群,不含幺不含幺;,交换半群交换半群,含幺含幺半群半群,非群非群;,都是都是交换群交换群;,都是交换半都是交换半群群,含幺半群含幺半群,非群非群;,都都是交换群。是交换群。+是普通加法是普通加法,*是普通乘法是普通乘法.(2)是交换群是交换群;是含幺半是含幺半群群,非交换。非交换。+和和分别表示矩阵加法和乘法分别表示矩阵加法和乘法.(3),为交换半群为交换半群,含幺半含幺半群群,非群非群;为交换群。并为交换群。并,交交,对称差对称差.(4)为交换群为交换群;为交换半群为交换半群,含幺含幺半群半群,非群非群;(n为素数为素数)为交换群。模加为交换群。模加,模乘模乘(5)为含幺半群为含幺半群,非交换非交换,为函数复合为函数复合.n元对称群及其子群元对称群及其子群n元置换群元置换群为为(非交换非交换)群群.注：注：Q*,R*,C*,Zn*不含不含0；Zn=0,1,n 1.习题习题6.2，6.4，6.8掌握重要概念，了解性质掌握重要概念，了解性质设设G为群，为群，aG，令，令H=ak|kZ，则，则H是是G的子群，的子群，称为由称为由a生成的子群，记作生成的子群，记作.设设G是群，若存在是群，若存在aG使得使得G=ak|kZ，则称，则称G是是循环循环群群，记作，记作G=，称，称a为为G的的生成元生成元.习题习题6.5，6.9(1)若若G=是无限循环群，则是无限循环群，则G只有只有a和和a 1两个生成元两个生成元.(2)若若G=是是n阶循环群，则阶循环群，则ar是是G的生成元当且仅当的生成元当且仅当r是小于等于是小于等于n且与且与n互质的正整数互质的正整数.(1)设设G=是循环群，则是循环群，则G的子群仍是循环群的子群仍是循环群.(2)若若G=是无限循环群，则是无限循环群，则G的子群除的子群除e以外都是无以外都是无限循环群限循环群.(3)若若G=是是n阶循环群，则对阶循环群，则对n的每个正因子的每个正因子d，G恰恰好含有一个好含有一个d阶子群阶子群.6.2环与域环与域含幺所有元素有逆元交换律分配律消去律|S|2环*是半群+是Abel群域整环交换环*是交换半群含幺环*是独异点除环无零因子环*(除外)n为素数为素数是是域域环与域的实例环与域的实例(1)整数集、有理数集、实数集和复数集关于普通整数集、有理数集、实数集和复数集关于普通加法和乘法构成环，分别称为加法和乘法构成环，分别称为整数环整数环Z(整环整环)、有理数环有理数环Q(域域)、实数环实数环R(域域)和和复数环复数环C(域域).(2)n(n2)阶实矩阵的集合阶实矩阵的集合Mn(R)关于矩阵的加法和关于矩阵的加法和乘法构成环，称为乘法构成环，称为n阶实矩阵环阶实矩阵环(含幺环含幺环).(3)幂集幂集P(B)关于对称差和交运算构成环关于对称差和交运算构成环(交换环交换环,含幺环含幺环).(4)Zn0,1,.,n1，和和 分别表示模分别表示模n加法和乘加法和乘法，法，构成环，称为构成环，称为模模n的整数环的整数环(交换交换环环,含幺环含幺环)；n为素数为素数是域是域.习题习题6.6。六。六56.3格与布尔代数格与布尔代数(“布尔代数布尔代数”是重点是重点)结合律交换律幂等律吸收律封闭性幺元e零元 格1001布尔格=有补分配格幂集格(|P|=2n)有界格钻石格和五角格是有补格，非分配格钻石格和五角格是有补格，非分配格。是链是链;链是分配格链是分配格,中间元素无补中间元素无补。6.3格与布尔代数格与布尔代数1）设）设是偏序集，如果是偏序集，如果 x,y S，x,y都有最小上都有最小上界和最大下界，则称界和最大下界，则称S关于偏序关于偏序 作成一个作成一个格格.Sn是是n的正因子的集合的正因子的集合.D为整除关系为整除关系,则偏序集则偏序集构构成成分配分配格格.n分解为素数的单次幂相乘时分解为素数的单次幂相乘时,Sn是布尔格是布尔格.为为B的的幂集格幂集格布尔格.是链；是链；任何一条链任何一条链(中间元素无补元中间元素无补元)都是分配格都是分配格.2）定理定理设设L是格是格,则则L是分配格当且仅当是分配格当且仅当L不含有与钻石不含有与钻石格或五角格同构的子格格或五角格同构的子格.小于五元的格都是分配格小于五元的格都是分配格.3）格）格L 若存在全下界若存在全下界0或全上界或全上界1,一定是惟一的一定是惟一的.ab=0和和ab=1成立成立,则称则称b 是是a 的的补元补元.0,1互补互补.有界分配格有界分配格L中元素中元素a若存在补元若存在补元,则存在惟一的补元则存在惟一的补元.4）有限布尔代数）有限布尔代数(布尔格=有补分配格)L含有含有2n个元素个元素.习题习题6.13，6.12，6.3，6.14，6.7；例；例6.13。七。七2；四；四8注意事项1）两个）两个n 元置换的元置换的乘法乘法就是函数的复合运算就是函数的复合运算nn元置换的求元置换的求逆逆就是求反函数就是求反函数.题题6.10。五。五9.所有的所有的n元置换构成集合元置换构成集合Sn，Sn关于置换乘法关于置换乘法构成构成n元对称群元对称群.恒等置换恒等置换(1)是单位元，逆是单位元，逆置换置换 1是是的逆元的逆元.n元对称群的子群称为元对称群的子群称为n元置换群元置换群.2）x 的加法逆元为的加法逆元为负元负元，记作，记作 x.3）全下界）全下界0与全上界与全上界1互补互补.了解n幂运算幂运算n子半群与子独异点子半群与子独异点;子群子群,真子群真子群,平凡子群平凡子群;子格子格n积半群与积独异点积半群与积独异点n半群和独异点的同态，格同态半群和独异点的同态，格同态.习题习题6.11nKlein四元群四元群n有限群有限群，无限群无限群.群群G的基数称为群的基数称为群G的的阶阶|G|.元素元素x的的阶阶(或周期或周期)|x|=k，称，称x为为k阶元阶元.无限阶元无限阶元.子群判定定理；子群判定定理；群群G的中心的中心C.k 阶轮换与对换阶轮换与对换格的对偶命题与对偶原理格的对偶命题与对偶原理第四部分第四部分图论图论n图论基本定理图论基本定理握手定理握手定理n任意无向图和有向图的所有顶点度数之和都等于边数的2倍,并且有向图的所有顶点入度之和等于出度之和等于边数.n推论推论 在任何无向图和有向图中，奇度顶点的个数必为偶数.n不存在具有奇数个面且每个面都具有奇数条棱的多面体.n习题习题7.1,7.14,7.19,7.5,7.6;例例7.8(六六3)。五。五6第第7章章图的基本概念图的基本概念7.1无向图及有向图无向图及有向图(握手定理、自补图是重点握手定理、自补图是重点)7.2通路、回路、图的连通性通路、回路、图的连通性(割集是重点割集是重点)7.3图的矩阵表示图的矩阵表示(由有向图的邻接矩阵求通路数和回路数是重点由有向图的邻接矩阵求通路数和回路数是重点)7.4最短路径最短路径(Dijkstra标号法标号法)与关键与关键(最长最长)路径路径7.1无向图及有向图无向图及有向图重要概念：重要概念：1）设）设G1=,G2=为两个无向图为两个无向图(有向图有向图),若存在双射函数若存在双射函数f:V1V2,使得对于任意的使得对于任意的vi,vj V1,(vi,vj)E1（E1）当且仅当）当且仅当(f(vi),f(vj)E2（E2），并且），并且,(vi,vj)（）与）与(f(vi),f(vj)（）的重数相同，则称的重数相同，则称G1与与G2是是同构同构的，记作的，记作G1 G2.同构的必要条件同构的必要条件,但它们都不是充分条件但它们都不是充分条件:边数相同，顶点数相同边数相同，顶点数相同度数列相同度数列相同(不计度数的顺序不计度数的顺序)对应顶点的关联集及邻域的元素个数相同对应顶点的关联集及邻域的元素个数相同.2）既无平行边也无环的图称为）既无平行边也无环的图称为简单图简单图.题题7.13n阶无向完全图阶无向完全图Kn:边数边数m=n(n-1)/2,=n-1.题题7.7n阶有向完全图阶有向完全图:边数边数m=n(n-1),=2(n-1),+=+=-=-=n-1.习题习题7.93）若）若G G 且且V =V，则称，则称G 为为G的的生成子图生成子图.4）设）设G=为为n阶无向简单图，以阶无向简单图，以V为顶点集为顶点集,所有使所有使G成为完全图成为完全图Kn的添加边组成的集合为边的添加边组成的集合为边集的图，称为集的图，称为G的的补图补图，记作，记作.习题习题7.8n若若G,则称则称G是是自补图自补图.习题习题7.20，7.12n习题习题7.12，7.10；例；例7.107.1无向图及有向图无向图及有向图(自补图是重点自补图是重点)7.2通路、回路、图的连通性通路、回路、图的连通性(了解了解)1）区分初级通路）区分初级通路(路径路径)与与简单通路简单通路,初级回路初级回路(圈圈)与与简单回路简单回路.2）u v(连通连通,不一定直通不一定直通).规定规定u与自身总连通与自身总连通.四四6，11，12连通关系连通关系R=|u,v V且且u v是是V上的等价关系上的等价关系连通图连通图:平凡图平凡图,任意两点都连通的图任意两点都连通的图.G是连通图是连通图p(G)=1连连 通通 分分 支支:V关关 于于 R的的 等等 价价 类类 的的 导导 出出 子子 图图.设设V/R=V1,V2,Vk,GV1,GV2,GVk是是G的的连连通通分分支支,其个数记作其个数记作p(G)=k.3）D弱连通弱连通(连通连通):基图为无向连通图基图为无向连通图.D单向连通单向连通:u,v V，u可达可达v或或v可达可达u.D强连通强连通:u,v V，u与与v相互可达相互可达强连通强连通单向连通单向连通弱连通弱连通.习题习题7.21，7.16(强强连连通通判判别别法法)D强强连连通通当当且且仅仅当当D中中存存在在经经过过每每个个顶顶点点至至少少一一次次的的回回路路.(单单向向连连通通判判别别法法)D单单向向连连通通当当且且仅仅当当D中中存存在经过每个顶点至少一次的通路在经过每个顶点至少一次的通路割集（重点）割集（重点）记记G v:从从G中中删删除除顶顶点点v及及关关联联的的边边.G V:从从G中中删删除除V 中中所所有有顶顶点点及及关关联联的的边边.G e:从从G中中删删除除边边e.G E:从从G中删除中删除E 中所有边中所有边.设设 无无 向向 图图 G=,VV,若若 p(G V)p(G)且且 V V,p(G V)=p(G),称称V 为为G的的点点割割集集.若若v为为点点割割集集,称称v为为割割点点.V 为为点点割割集集且且V V V V 非非点割集点割集.设设 无无 向向 图图 G=,EE,若若 p(G E)p(G)且且 E E,p(G E)=p(G),称称E 为为G的的边边割割集集.若若e为为 边边 割割 集集,称称 e为为 割割 边边 或或 桥桥.E 为为 边边 割割 集集 且且E E E E 非非边割集边割集.Kn无点割集无点割集.n阶零图既无点割集，也无边割集阶零图既无点割集，也无边割集.若若G连通，连通，E 为边割集，则为边割集，则p(G E)=2.例例7.11若若G连通，连通，V 为点割集，则为点割集，则p(G V)2.习题习题7.177.3图的矩阵表示图的矩阵表示n有向图有向图D=,V=v1,v2,vn,E=e1,e2,em,令令aij(1)为顶点为顶点vi邻接到顶点邻接到顶点vj边的条边的条数数,称称(aij(1)m n为为D的邻接矩阵的邻接矩阵,记作记作A(D),简记为简记为A.有向图的邻接矩阵（重点）有向图的邻接矩阵（重点）定理定理设设A为为n阶有向图阶有向图D的邻接矩阵的邻接矩阵,则则Al(l 1)中中元素元素为为D中中vi到到vj长度为长度为l 的通路数，的通路数，为为vi到自身长度为到自身长度为l 的回路数，的回路数，为为D中长度为中长度为l 的通路总数，的通路总数，为为D中长度为中长度为l 的回路总数的回路总数.习题习题7.18推论推论设设Bl=A+A2+Al(l 1),则则Bl中元素中元素为为D中长度小于或等于中长度小于或等于l 的通路数，的通路数，为为D中长度小于或等于中长度小于或等于l 的回路数的回路数.7.4最短路径与关键最短路径与关键(最长最长)路径路径n带权图；带权图；最短路径与最短路径与Dijkstra标号法标号法.习题习题7.22。五。五4nPERT图图(计划评审技术图计划评审技术图)与关键路径与关键路径.关键路径关键路径:PETR图中从始点到终点的最长路径图中从始点到终点的最长路径vi的最早完成时间的最早完成时间TE(vi):从始点从始点v1沿最长路径到沿最长路径到vi所需的所需的时间时间.TE(v1)=0TE(vi)=maxTE(vj)+wji|vj -(vi),i=2,3,nvi的最晚完成时间的最晚完成时间TL(vi):在保证终点在保证终点vn的最早完成的最早完成时间不增加的条件下时间不增加的条件下,从始点从始点v1最迟到达最迟到达vi的时间的时间 TL(vn)=TE(vn)TL(vi)=minTL(vj)-wij|vj +(vi),i=n-1,n-2,1vi的缓冲时间的缓冲时间TS(vi)=TL(vi)-TE(vi),i=1,2,nvi在关键路径上在关键路径上TS(vi)=0.习题习题7.23了解了解n 阶图阶图:n个顶点的图个顶点的图.有限图有限图:V,E都是有穷集的图都是有穷集的图.零图零图:E=.平凡图平凡图:1阶零图阶零图.空图空图:V=.端点端点(始点始点,终点终点),关联次数关联次数,环环,孤立点孤立点,相邻相邻,邻接邻接.n邻域邻域(先驱元集先驱元集后继元集后继元集),闭邻域闭邻域,关联集关联集.v的的度度数数d(v)=出出度度d+(v)+入入度度d(v);悬悬挂挂顶顶点点,悬悬挂挂边边;G的的最最大大度度(G),最最小小度度(G);D的的最最大大出出度度+(D),最最小小出出度度+(D),最最大大入入度度 (D),最最小小入入度度 (D);度度数数列列,出出度度列列,入入度度列列;平平行行边边,重重数数,多多重重图图;n阶阶k正正则图则图;子图子图,母图母图,真子图真子图,导出子图导出子图;连通度连通度.可达矩阵可达矩阵P(D)主对角线上的元素全为主对角线上的元素全为1.关联矩阵关联矩阵.D强连通当且仅当可达矩阵强连通当且仅当可达矩阵P(D)的元素全为的元素全为1.第第8章章一些特殊的图一些特殊的图图图的的类类型型(二二部部图图,欧欧拉拉图图,哈哈密密顿顿图图,平平面面图图,树树)判别是重点判别是重点.习题8.18,8.21;例8.28.5.四148.1二部图（了解匹配）二部图（了解匹配）8.2欧拉图（前提连通）欧拉图（前提连通）8.3哈密顿图（前提连通）哈密顿图（前提连通）8.4平面图（欧拉公式是重点，了解自对偶图）平面图（欧拉公式是重点，了解自对偶图）8.1二部图二部图设设 无无 向向 图图 G=,若若 能能 将将 V分分 成成 V1和和 V2(V1 V2=V,V1 V2=),使使得得G中中的的每每条条边边的的两两个个端端点点都都一一个个属属于于V1,另另一一个个属属于于V2,则则称称G为为二二部部图图,记记为为,称称V1和和V2为为互互补补顶顶点点子子集集.又又若若G是是简简单单图图,且且V1中中每每个个顶顶点点均均与与V2中中每每个个顶顶点点都都相相邻邻,则则称称G为为完完全全二二部部图图,记记为为Kr,s,其中其中r=|V1|,s=|V2|.注注:n阶零图为二部图阶零图为二部图.题题8.2,8.3定理定理无向图无向图G=是二部图当且仅当是二部图当且仅当G中无奇圈中无奇圈.二部图无环；二部图无环；平行边不影响图的二部性平行边不影响图的二部性.n匹配匹配(边独立集边独立集):任任2条边均不相邻的边子集条边均不相邻的边子集.习题习题8.4极大匹配极大匹配,最大匹配最大匹配,匹配数匹配数 1,(非非)饱和点饱和点,完美匹配完美匹配.注：匹配不限于二部图；注：匹配不限于二部图；完备匹配完