离散数学考点复习.ppt

1、复 习,离散数学的构成,数理逻辑,集 合 论,图 论,命题逻辑,谓词逻辑,集合,关系,图的基本概念,几个特殊图,离散数学,函数,图的连通性,集合,主要内容：集合的基本概念，集合的表示方法，一些特殊的集合，集合的运算及其运算性质。 要求： 了解: 无限集合的基本概念；理解可数集合与不可数集合的证明方法； 熟练掌握: 集合、子集、包含、幂集的概念及求法、集合的表示法、集合的运算及其运算性质、集合恒等式的证明方法。,学习要求,集合的表示方法,集合是由它包含的元素完全确定的，为了表示一个集合，通常有： 枚举法（显示法） 隐式法（叙述法） 归纳法 递归指定 文氏图,1、互异性集合中的元素都是不同的，凡是

2、相同的 元素，均视为同一个元素； 1,1,2=1,2 2、确定性能够明确加以“区分的”对象； 3、无序性集合中的元素是没有顺序的。 2,1=1,2,一、集合的三大特征,幂集,定义1.2.7 设A为任意集合，把A的所有不同子集构成的集合叫做A的幂集(power set)，记为P(A)或2A。其符号化表示为 P(A)x|一切xA 该集合又称为集族(family of set)。,对集族的研究在数学方面、知识库和表处理语言以及人工智能等方面都有十分重要的意义。,显然，若集合有个元素，则集合共有2|A|个子集，即：|P(A)| 2|A|。,集合的运算,定义1.2.8 设A、B是两个集合， (1)并集

3、AB=x|xA或xB (2)交集 AB=x|xA且xB (3)差集 A-B=x|xA且xB (4)补集 =U-A=x|xU且xA (,AC) (5)对称差集 AB=x|(xA)且(xB)或(xB)且(xA),容斥原理,定理2.4.5 设A1, A2, , An是任意n个有限集合，则 推论2.4.6 设U为全集，A1, A2, , An是任意n个有限集合，则,定理2.4.5,若有n只鸽子住进m(nm)个鸽笼，则存在一个鸽笼至少住进 只鸽子。这里， 表示小于等于x的最大整数。,例：如果一个图书馆里3本离散数学书，共有1203页，那么必然有一本离散数学书至少有401页。,分析：将1203页书看成12

4、03只鸽子，3本离散数学书看成鸽笼即可,第二篇 数理逻辑,主要内容,1、命题逻辑 命题与命题联结词，命题公式，公式的等价与蕴涵，基本等价式，基本蕴涵式，公式的范式，推理理论。,2、谓词逻辑 谓词与量词，谓词公式，公式的等价与蕴涵，前束范式，推理理论。,要求,了解:命题演算在逻辑电路、开关电路和程序设计中的应用、五个基本联结词之外的其它联结词；理解基本等价公式和基本蕴含公式的逻辑意义； 熟练掌握：命题的概念及其真值的判定、五个基本联结词的概念及用法、语句符号化方法、命题公式类型的判定、公式等价的概念、基本等价式、范式的概念及求范式的方法、公式蕴涵的概念及基本蕴涵式、命题逻辑推理方法。,要求,了解

5、:复杂的演绎推理、前束范式；理解含量词的基本等价公式和基本蕴含公式的逻辑意义； 熟练掌握：谓词、量词、公式及其解释的概念、语句符号化方法、公式在解释下求真值的方法、公式的等价与蕴涵的概念、含量词的基本等价公式和基本蕴含蕴涵式、简单的演绎推理。,命题逻辑学习要求,定义3.2.1 具有确切真值的陈述句称为命题。,命题公式,定义3.3.2 (命题公式) 命题变元本身是一个公式； 如G是公式，则(G)也是公式； 如G，H是公式，则(GH)、(GH)、(GH)、(GH)也是公式； 命题公式是仅由有限步使用规则1-3后产生的结果。该公式常用符号G、H、等表示。,公式G、H等价（G=H）的充要条件是GH是永

6、真公式,设G，H，S是任何的公式，则：,基本等价公式,1：G(HS)(GH)S(结合律) 2: G(HS)(GH)S 3：GHHG (交换律) 4：GHHG 5：GGG (幂等律) 6：GGG 7：G(GH) G (吸收律) 8：G(GH) G,9：G(HS)(GH)(GS)(分配律） 10：G(HS)(GH)(GS) 11：GG(同一律) 12：GG 13：G(零律) 14：G 15：GG (排中律) 16：GG (矛盾律),基本等价公式（续）,基本等价公式（续）,17：(G)G(双重否定律) 18：(GH)GH(De MoRGan定律) 19：(GH)GH 20: (GH)(GH)(HG)

7、(等价式) 21：(GH)(GH)(蕴涵式) E22：G G(假言易位) E23：G G(等价否定等式) E24：(G ) (G)G(归谬论),设G(P1,P2,Pn)是一个命题公式，其中：P1、P2、Pn是命题变元，G1(P1,P2,Pn)、G2(P1,P2,Pn)、.、Gn(P1,P2,Pn)为任意的命题公式，分别用G1、G2、Gn取代G中的P1、P2、Pn后得到新的命题公式：G(G1,G2,Gn)G(P1,P2,Pn) 若G是永真公式（或永假公式），则G也是一个永真公式（或永假公式）。,定理3.3.2(代入定理),公式的标准型范式,3.5.1 析取范式和合取范式 定义3.5.1 （1）命

8、题变元或命题变元的否定称为文字 （2）有限个文字的析取称为析取式(也称为子句） （3）有限个文字的合取称为合取式(也称为短语） （4）P与 P称为互补对。,（1）有限个短语的析取式称为析取范式 （2）有限个子句的合取式称为合取范式,范式的求解方法,定理3.5.1 对于任意命题公式，都存在与其等价的析取范式和合取范式。,转换方法： （1）利用等价公式中的等价式和蕴涵式将公式中的、用联结词 、来取代，这可利用如下等价关系： () = ()； () = ()() = ()()。,范式的求解方法(续),（2）重复使用德摩根定律将否定号移到各个命题变元的前端，并消去多余的否定号，这可利用如下等价关系：(

9、) =； () = ； () = 。,（3）重复利用分配定律，可将公式化成一些合取式的析取，或化成一些析取式的合取，这可利用如下等价关系：() = ()()； () = ()()。,主析取范式和主合取范式,1. 极小项和极大项,定义 3.5.3 在含有n个命题变元P1、P2、P3、Pn的短语或子句中，若每个命题变元与其否定不同时存在，但二者之一恰好出现一次且仅一次，则称此短语或子句为关于P1、P2、P3、Pn的一个极小项或极大项。,对于n个命题变元，可构成2n个极小项和2n个极大项,任意两个不同极小项的合取必为假； 任意两个不同极大项的析取必为真； 极大项的否定是极小项； 极小项的否定是极大项

10、； 所有极小项的析取为永真公式； 所有极大项的合取是永假公式。,mimj=F, ij,极小项和极大项的性质,Mi=mi,MiMj=T, ij,Mi= mi,定理3.5.2,任何一个公式都有与之等价的主析取范式和主合取范式。,证明：（1）利用定理3.5.1先求出该公式所对应的析取范式和合取范式； （2）在析取范式的短语和合取范式的子句中，如同一命题变元出现多次，则将其化成只出现一次； （3）去掉析取范式中所有永假式的短语和合取范式中所有永真式的子句，即去掉含有形如PP子公式的短语和含有形如PP子公式的子句；,证明（续1）,（4）若析取范式的某一个短语中缺少该命题公式中所规定的命题变元，则可用公式

11、： ()Q = Q 将命题变元P补进去，并利用分配律展开，然后合并相同的短语，此时得到的短语将是标准的极小项； 若合取范式的某一个子句中缺少该命题公式中所规定的命题变元，则可用公式： ()Q = Q 将命题变元P补进去，并利用分配律展开，然后合并相同的子句，此时得到的子句将是标准的极大项；,证明（续2）,（5）利用幂等律将相同的极小项和极大项合并，同时利用交换律进行顺序调整，由此可转换成标准的主析取范式和主合取范式。,求主析取范式和主合取范式的方法,真值表技术,列出公式对应的真值表，选出公式的真值结果为真的所有的行，在这样的每一行中，找到其每一个解释所对应的极小项，将这些极小项进行析取即可得到

12、相应的主析取范式。 列出公式对应的真值表，选出公式的真值结果为假的所有的行，在这样的每一行中，找到其每一个解释所对应的极大项，将这些极大项进行合取即可得到相应的主合取范式。,主析取范式中必须且只能包含使得公式真值为真的那些解释对应的极小项。,主合取范式中必须且只能包含使得公式真值为假的那些解释对应的极大项。,例3.5.4,利用真值表技术求公式G = ()的主析取范式和主合取范式。,例3.5.4(续1),（1）求主析取范式 找出真值表中其真值为真的行： 2. 0 0 1； 4. 0 1 1； 5. 1 0 0； 6. 1 0 1； 8. 1 1 1。 这些行所对应的极小项分别为： P， P，P，

13、 P，P。,例3.5.4(续2),将这些极小项进行析取即为该公式G的主析取范式。 G = () = (P)(P) (P)(P)(P),例3.5.4(续3),（2）求主合取范式 找出真值表中其真值为假的行： 10 0 0； 30 1 0； 71 1 0。 这些行所对应的极大项分别为： P、P 、 将这些极大项进行合取即为该公式G的主合取范式： G = () =(P)(P)(),例3.5.5,设=()()()，求其对应的主析取范式和主合取范式。,解 = ()()( ) =()() ()， = ()()() ()()() = ()()() ()()() = m0m1m3m4m6m7 主析取范式,例3

14、.5.5（续）,= m2m5 = (m2m5)m2m5= M2M5 =()() 主合取范式,5.2.2 判断有效结论的常用方法,1、真值表技术,设P1,P2,Pn是出现在前提G1,G2,Gn和结论H中的一切命题变元，如果将P1,P2,Pn中所有可能的解释及G1,G2,Gn，H的对应真值结果都列在一个表中，根据“”的定义，则有判断方法如下：,对所有G1,G2,Gn都具有真值T的行(表示前提为真的行),如果在每一个这样的行中，H也具有真值T，则H是G1,G2,Gn的逻辑结果。 对所有H具有真值为F的行(表示结论为假的行),如果在每一个这样的行中，G1,G2,Gn中至少有一个公式的真值为F(前提也为

15、假),则H是G1,G2,Gn的逻辑结果。,推理规则,规则P（称为前提引用规则）：在推导的过程中，可随时引入前提集合中的任意一个前提； 规则T（逻辑结果引用规则）：在推导的过程中，可以随时引入公式S，该公式S是由其前的一个或多个公式推导出来的逻辑结果。 规则CP（附加前提规则）：如果能从给定的前提集合与公式P推导出S，则能从此前提集合推导出PS。,P()(P)， P()等价于(P),谓词逻辑,全称量词与存在量词,定义4.2.4 称(x)为全称量词（Universal Quantifier），(x)为存在量词（Existential Quantifier），其中的x称为作用变量（Function

16、Variable）。一般将其量词加在其谓词之前，记为(x)F(x)，(x)F(x)。此时，F(x)称为全称量词和存在量词的辖域(Scope)。,谓词逻辑符号化的两条规则,统一个体域为全总个体域，而对每一个句子中个体变量的变化范围用一元特性谓词刻划之。这种特性谓词在加入到命题函数中时必定遵循如下原则：,（1）对于全称量词(x)，刻划其对应个体域的特性谓词作为蕴涵式之前件加入。,（2）对于存在量词(x)，刻划其对应个体域的特性谓词作为合取式之合取项加入。,谓词演算中的有效公式,（1）E25：(x)G(x) = (y)G(y)； (改名规则) E26：(x)G(x) = (y)G(y)； （2）E2

17、7： (x)G(x) = (x)G(x)； E28：(x)G(x) = (x)G(x)； (量词转换律/量词否定等值式) （3）E29：(x)(G(x)S) = (x)G(x)S； E30：(x)(G(x)S) = (x)G(x)S； E31：(x)(G(x)S) = (x)G(x)S； E32：(x)(G(x)S) = (x)G(x)S； (量词辖域的扩张与收缩律),谓词演算中的有效公式（续）,（4）E33：(x)(G(x)H(x) =(x)G(x)(x)H(x)； E34：(x)(G(x)H(x) =(x)G(x)(x)H(x)； (量词分配律) （5）E35：(x)G(x)(x)H(x)

18、 =(x)(y)(G(x)H(y)； E36：(x)G(x)(x)H(x) =(x)(y)(G(x)H(y)；,一、推理规律,（1）I16：(x)G(x) (x)G(x)； （2）I17：(x)G(x)(x)H(x) (x)(G(x)H(x)； I18：(x)(G(x)H(x) (x)G(x)(x)H(x)； （3）I19：(x)(G(x)H(x) (x)G(x)(x)H(x)； I20：(x)(G(x)H(x) (x)G(x)(x)H(x)。,推理规律（续）,（4）I21：(x)(y)G(x,y) (y)(x)G(x,y)； I22：(x)(y)G(x,y) (y)(x)G(x,y)； I2

19、3：(y)(x)G(x,y) (x)(y)G(x,y)； I24：(y)(x)G(x,y) (x)(y)G(x,y)； I25：(x)(y)G(x,y) (y)(x)G(x,y)； I26：(y)(x)G(x,y) (x)(y)G(x,y)；,量词关系图,E38,E37,(x)(y),(y)(x),I22,I23,(y)(x),(x)(y),I24,I21,(x)(y),(y)(x),I25,I26,(y)(x),(x)(y),二、推理规则,1、US（全称特指规则，Universal SPecify）： (x)G(x) G(y) 其中G(x)对y是自由的 推广：(x)G(x) G(c) 其中c

20、为任意个体常量 2、ES（存在特指规则， Existential SPecify ）： (x)G(x) G(c) 其中c为使G(c)为真的特定个体常量；若G(x)中还有除x以外的自由变量时，则必须用这些变量的函数符号来取代。,推理规则（续）,3、UG（全称推广规则， Universal Generalize ）： G(y) (x)G(x) 其中G(y)对x是自由的且G(y)中无自由变量x 4、EG（存在推广规则，Existential Generalize）： G(c) (x)G(x) 其中G(c)对x是自由的且G(c)中无自由变量x 推广：G(y) (x)G(x) 其中G(y)对x是自由的且

21、G(y)中无自由变量x,二元关系与函数,主要内容： 有序对与笛卡尔积，二元关系及其表示法，关系的运算，关系的性质及闭包运算; 等价关系与偏序关系，函数（映射）及其性质。,要求,了解:复合映射与逆映射的性质；理解等价关系与偏序关系在计算机科学中的应用； 重点掌握： 关系的有关概念、逆关系及复合关系的概念及其求法、关系的自反性、反自反性、对称性、反对称性及传递性的定义与判定、闭包的计算; 等价关系与偏序关系的概念与判定、偏序集中的特殊元的确定; 函数（映射）的概念、单射、满射、双射的概念及判定。,定义6.2.7 设A,B为两个非空集合，称AB的任何子集R为从A到B的二元关系，简称关系(Relati

22、on)。如AB，则称R为A上的二元关系。 这里，A称为R的前域，B称为R的后域。 令Cx|RA， Dy|RB， 称C为R的定义域，记为CdomR；称D为R的值域，记DranR；并称fldRDC为R的域。,二元关系,注意 当集合A,B都是有限集时，AB共有2|A|B|个不同 的子集，即从A到B的不同关系共有2|A|B|个。,关系的表示法,集合表示法（枚举法和叙述法） 关系图法 （1）AB （2)A=B 关系矩阵,必须先对集合A,B中的元素排序 A中元素序号对应矩阵元素的行下标， B中元素序号对应矩阵元素的列下标； 关系矩阵是0-1矩阵，称为布尔矩阵。,注意,关系的复合运算,定义6.3.1 设A,

23、B,C是三个集合，R是从A到B的关系 (R：AB)，S是从B到C的关系(S：BC)，则R与S 的复合关系(合成关系)(Composite)RS是从A到C的 关系，并且： RS|xAzC (y)(yBxRyySz) 运算“”称为复合运算(CompositeOperation)。,R和S是可复合的R的后域和S的前域完全相同； RoS的前域是R的前域A，后域是S的后域C； RoS对任意xA和zC，不存在yB，使得xRy和ySz同时成立； oRRo 。,定义6.3.2 设A，B是两个集合，R是A到B的关系，则从B到A的关系 R-1|R 称为R的逆关系(InverseRelation)， 运算“-1”称

24、为逆运算(InverseOperation) 。,6.3.2 关系的逆运算,注意：关系是一种集合，逆关系也是一种集合，因此，如果R是一个关系，则R-1和都是关系，但R-1和是完全不同的两种关系，千万不要混淆。 若RAB，则 ABRAB，R-1BA。,由定义： (R-1)-1=R； -1=。,设R，S是从集合A到集合B的关系，则有 (RS)-1R-1S-1；(分配性) (RS)-1R-1S-1； (R-S)-1R-1-S-1； ()-1 ；(可换性) (AB)-1(BA)； SR S-1R-1；(单调性),定理6.3.4,定义6.3.3设R是集合A上的关系，则R的n次幂，记为Rn，定义如下： R

25、0IA|aA； R1R； Rn+1RnRRRn。,6.3.3 关系的幂运算,由于关系的复合运算满足结合律，Rn即为n个R的复合，也是A上的二元关系。显然，RmRnRm+n，(Rm)nRmn。,设A是有限集合，且|A|n，R是A上的二元关系，则：,定理6.3.5,6.4.1 关系性质的定义,1、自反性和反自反性 定义6.4.1 设R是集合A上的关系， 如果对任意xA，都有R，那么称R在A上是自反的(Reflexive)，或称R具有自反性(Reflexivity)； 例如：自然数集上的大于等于关系。 如果对任意xA，都有 R，那么称R在A上是反自反的(Antireflexive)，或称R具有反自反

26、性(Antireflexivity)。 例如：父子关系。,2、对称性和反对称性,定义6.4.2 设R是集合A上的关系。 对任意x,yA，如果R，那么 R，则称关系R是对称的(Symmetric)，或称R具有对称性(Symmetry)； 对任意x,yA，如果R且R，那么xy（或者如果xy且R，那么 R），则称关系R是反对称的(Antisymmetric)，或称R具有反对称性(Antisymmetry)。,3、传递性,定义6.4.3 设R是集合A上的关系。对任意x,y,zA，如果R且R，那么R，则称关系R是传递的(Transitive)，或称R具有传递性(Transitivity)。 将定义6.4

27、.3符号化为： R在A上是传递的 (x)(y)(z)(xA)(yA)(zA) (R)(R)(R)=1。 R在A上不是传递的 (x)(y)(z)(xA)(yA)(zA) (R)(R)( R)=1。,总结,6.5.1关系的闭包,定义6.5.1 设R是定义在A上的关系，若存在A上的另一个关系R，满足： （1）R是自反的(对称的、或传递的)； （2）对任何自反的(对称的、或传递的)关系R，如果R R，就有R R，则称为R的自反闭包(ReflexiveClosure)(对称闭包(SymmetricClosure)、或传递闭包(TransitiveClosure)，分别记为r(R)(s(R)或t(R)。

28、从定义6.5.1可以看出，关系的闭包是增加最少元素，使其具备所需性质的扩充。,设R是集合A上的二元关系，则： （1）r(R)RIA。 （2）s(R)RR-1。 （3）t(R) ，若|A|n，则t(R) 。,定理6.5.1,7.2 等价关系,定义7.2.1 设R是定义在非空集合A上的关系，如果R是自反的、对称的、传递的，则称R为A上的等价关系。,由定义7.2.1知： （1）关系R是等价关系当且仅当R同时具备自反性、对称性和传递性； （2）关系R不是等价关系当且仅当R不具备自反性或对称性或传递性。,以n为模的同余关系,上述R称为Z上以n为模的同余关系(Congruence Relation)，记x

29、Ry为 xy(mod n) 称为同余式。如用resn(x)表示x除以n的余数，则 xy(mod n) resn(x)resn(y)。 此时，R将Z分成了如下n个子集： ,-3n,-2n,-n,0,n,2n,3n, ,-3n+1,-2n+1,-n+1,1,n+1,2n+1,3n+1, , -3n+2,-2n+2,-n+2,2,n+2,2n+2,3n+2, ,-2n-1,-n-1,-1,n-1,2n-1,3n-1,4n-1,集合的划分,定义7.2.2 给定非空集合A，设有集合S=S1,S2,S3,Sm。如果满足 SiA且Si，i1,2,m； SiSj，ij，i,j1,2,m； 。,则集合S称作集合

30、A的一个划分(Partition)，而S1, S2,Sm叫做这个划分的块(Block)或类(Class)。,等价类与商集,定义7.2.3 设R是非空集合A上的等价关系，对任意xA，称集合 xRy|yAR 为x关于R的等价类(equivalence class)，或叫作由x生成的一个R等价类，其中x称为xR的生成元(或叫代表元，或典型元)(generator) 。,定义7.2.4 设R是非空集合A上的等价关系，由R确定的一切等价类的集合，称为集合A关于R的商集(Quotient Set)，记为A/R，即 A/RxR|(xA),次序关系,定义7.3.1 设R是非空集合A上的关系，如果R是反自反和传

31、递的，则称R是A上的拟序关系(Quasi-Order Relation)，简称拟序，记为“”，读作“小于”，并将“”记为“ab”。序偶称为拟序集(Quasi-Order Set)。,定义7.3.2 设R是非空集合A上的关系，如果R是自反的、反对称的和传递的，则称R是A上的偏序关系(Partial Order Relation)，简称偏序，记为“”，读作“小于等于”，并将“”记为ab。序偶称为偏序集(PartialOrder Set)。 常将ab且ab记为ab。,哈斯图,用小圆圈或点表示A中的元素，省掉关系图中所有的环； （因自反性) 对任意x,yA，若xy，则将x画在y的下方，可省掉关系图中所

32、有边的箭头；（因反对称性） 对任意x,yA，若xy，且不存在zA，使得 xz, zy，则x与y之间用一条线相连，否则 无线相连。（因传递性）,特殊元:最大(小)元 与极大(小)元,定义7.3.3 设是偏序集，B是A的任何一个子集，若存在元素bB，使得对任意xB， 都有xb，则称b为B的最大元素，简称最大元； 都有bx，则称b为B的最小元素，简称最小元； 满足bx x=b，则称b为B的极大元素，简称极大元； 满足xb x=b，则称b为B的极小元素，简称极小元。,在B中找最大(小)元、极大(小)元,上(下)界与上(下)确界,设是偏序集，B是A的任何一个子集。若存在元素aA，使得 对任意xB，都有x

33、a，则称a为B的上界； 对任意xB，都有ax，则称a为B的下界； 若元素aA是B的上界，元素aA是B的任何一个上界，若均有aa，则称a为B的最小上界或上确界。记a=SupB； 若元素aA是B的下界，元素aA是B的任何一个下界，若均有aa，则称a为B的最大下界或下确界。记a=InfB。,在A中找上(确)界、下(确)界,定理7.3.1,设是一偏序集，B是A的子集。则： b是B的最大元 b是B的极大元、上界、上确界； b是B的最小元 b是B的极小元、下界、下确界； a是B的上确界且aB a是B的最大元； a是B的下确界且aB a是B的最小元。,7.3.3 全序关系,定义7.3.5 设为偏序集，若对任

34、意x,yA，总有xy或yx，二者必居其一，则称关系“”为全序关系(Total Order Relation)，简称全序，或者线序关系，简称线序。称为全序集(Total Order Set)，或者线序集，或者链(Chain)。 从定义7.3.5可以看出： 全序关系是偏序关系，反之则不然。,定义7.3.6 设是一偏序集，若A的任何一个非空子集都有最小元素，则称“”为良序关系，简称良序，此时称为良序集。,8.函数,函数的概念。注意函数与关系的区别和联系； 单射、满射和双射函数的概念，数学描述形式； 特殊函数的基本概念； 函数的复合运算，逆运算及运算性质。,定义,定义8.2.1 设f是集合A到B的关系

35、，如果对每个xA，都存在惟一的yB，使得f，则称关系f为A到B的函数(Function)(或映射(Mapping)、变换(Transform)，记为f:AB。 A为函数f的定义域，记为domf=A； f(A)为函数f的值域，记为ranf。 当f时，通常记为y=f(x)，这时称x为函数f的自变量，y为x在f下的函数值(或象)， 也称x为y在f下的原象 。,分类,定义8.2.2 设f是从A到B的函数， 对任意x1,x2A，如果x1x2，有f(x1)f(x2)， 则称f为从A到B的单射（不同的x对应不同的y)； 如果ranfB，则称f为从A到B的满射； 若f是满射且是单射，则称f为从A到B的双射。

36、若AB，则称f为A上的函数；当A上的函数f是双射时，称f为一个变换。,定理8.2.1: 设A，B是有限集合，且|A|=|B|，f是A到B的函数，则f是单射当且仅当f是满射。,图论,主要内容： 图的概念，顶点的度数，子图与补图，图的同构，通路与回路，图的连通性，图的矩阵表示. 树，生成树，最小生成树，有向树， 欧拉图、哈密尔顿图，偶图与匹配，平面图与欧拉公式。,学习要求,了解:图的环和运算、边（点）割集的有关概念、图的连通度及有关概念、图的可达矩阵概念与求法,同构图的判定，基本回路系统的概念，有向树，匹配的有关概念、图知识在通信与计算机科学中的应用. 理解:涉及图的哈密尔顿性的几个定理的证明方.

37、,熟练掌握：,图、简单图、完全图、平凡图、子图、生成子图的概念，结点的度数与边数的关系，关联矩阵与邻接矩阵，通路的有关概念及图的连通性; 树及其性质，生成树与最小生成树的求法;根树及其性质,树的遍历; 欧拉图与哈密尔顿图的概念与判定，偶图与平面图的概念与判定，欧拉公式。,图的表示,1.集合表示:对于一个图G，将其记为G = ，并写出V和E的集合表示。 2.图形表示:用小圆圈表示V中的结点，用由u指向v的有向线段或曲线表示有向边，无向线段或曲线表示无向边(u, v)。,3.矩阵表示:设图G = ，其中V = v1, v2, , vn，并假定结点已经有了从v1到vn的次序，则n阶方阵AG = (a

38、ij)nxn称为G的邻接矩阵(Adjacency Matrix)，其中,图的操作,定义9.2.3 设图G = 。 设eE，用G-e表示从G中去掉边e得到的图，称为删除边e。又设EE，用G-E表示从G中删除E中所有边得到的图，称为删除E。 设vV，用G-v表示从G中去掉结点v及v关联的所有边得到的图，称为删除结点v。又设VV，用G-V 表示从G中删除V中所有结点及关联的所有边得到的图，称为删除V。 设e = (u, v)E，用Ge表示从G中删除e，将e的两个端点u, v用一个新的结点w代替，使w关联除e外的u和v关联的一切边，称为边e的收缩。一个图G可以收缩为图H，是指H可以从G经过若干次边的收

39、缩而得到。 设u, vV(u, v可能相邻，也可能不相邻)，用G(u, v)表示在u, v之间加一条边(u, v)，称为加新边。,图的分类,边方向,权,平行边,子图与补图,定义9.2.8 设有图G = 和图G1 = 。 若V1 V，E1 E，则称G1是G的子图(Subgraph)，记为G1 G。 若G1 G，且G1G(即V1 V或E1 E)，则称G1是G的真子图(Proper Subgraph)，记为G1 G。 若V1 = V，E1 E，则称G1是G的生成子图(Spanning Subgraph)。 设V2 V且V2，以V2为结点集，以两个端点均在V2中的边的全体为边集的G的子图，称为V2导出

40、的G的子图，简称V2的导出子图(Induced Subgraph)。,完全图,设G = 为一个具有n个结点的无向简单图，如果G中任意两个结点间都有边相连，则称G为无向完全图(Undirected Complete Graph)，简称G为完全图(Complete Graph)，记为Kn。 设G = 为一个具有n个结点的有向简单图，如果G中任意两个结点间都有两条方向相反的有向边相连，则称G为有向完全图(directed Complete Graph)，在不发生误解的情况下，也记为Kn。 对于完全图来说，其邻接矩阵除主对角元为0外，其它元素均为1。,无向完全图Kn的边数为 有向完全图Kn的边数为,结

41、点的度数与握手定理,定义9.2.11 （1）图G = 中以结点vV为端点的边数(有环时计算两次)称为结点v的度数(Degree)，简称度，记为deg(v)。 （2）有向图G = 中以结点v为始点的边数称为v的出度(Out-Degree)，记为deg+(v)；以结点v为终点的边数称为v的入度(In-Degree)，记为deg-(v)。显然，deg(v) = deg+(v)+deg-(v)。 （3）对于图G = ，度数为1的结点称为悬挂结点(Hanging Point)，以悬挂结点为端点的边称为悬挂边(Hanging Edge)。,定理9.2.1(握手定理),图中结点度数的总和等于边数的二倍，即设

42、图G = ，则有,推论9.2.1 图中度数为奇数的结点个数为偶数。,定理9.2.2 有向图中各结点的出度之和等于各结点的入度之和，等于边数，即设有向图G = ，则有,通路与回路,定义9.3.1:给定图G=中结点和边相继交错出现的序列=v0e1v1e2v2ekvk。 若中边ei的两端点是vi-1和vi（G是有向图时要求vi-1与vi分别是ei的始点和终点），i=1,2,k，则称为结点v0到结点vk的通路(Entry)。 v0和vk分别称为此通路的始点和终点，统称为通路的端点。 通路中边的数目k称为此通路的长度(Length)。 当v0=vn时，此通路称为回路(Circuit)。,若通路中的所有边

43、互不相同，则称此通路为简单通路(Simple Entry)或一条迹；若回路中的所有边互不相同，则称此回路为简单回路(Simple Circuit)或一条闭迹。 若通路中的所有结点互不相同（从而所有边互不相同），则称此通路为基本通路(Basic Entry)或者初级通路、路径；若回路中除v0=vk外的所有结点互不相同（从而所有边互不相同），则称此回路为基本回路(Basic Circuit)或者初级回路、圈。,定理9.3.1,设G = 为线图，V = v1, v2, , vn，A = (aij)nxn为G的邻接矩阵，Am=( )nxn。则 (1) 为从结点vi到结点vj长度为m的通路数目； (2)

44、 为结点vi到自身的长度为m的回路数目； (3) 为G中长度为m的通路（含回路）总数。,定义9.3.2,在图G = 中，vi, vjV。 如果从vi到vj存在通路，则称vi到vj是可达的，否则称vi到vj不可达。规定：任何结点到自己都是可达的。 如果vi到vj可达，则称长度最短的通路为从vi到vj的短程线(Geodesic)； 从vi到vj的短程线的长度称为从vi到vj的距离(Distance)，记为d(vi, vj)。如果vi到vj不可达，则通常记为d(vi, vj) = 。,无向图的连通性,定义9.3.4 若无向图G中的任何两个结点都是可达的，则称G是连通图(Connected Graph

45、)，否则称G是非连通图(Unconnected Graph)或分离图(Separated Graph)。 无向完全图Kn（n1）都是连通图，而多于一个结点的零图都是非连通图。 利用邻接矩阵A和可达性矩阵P，显然有： 非平凡无向线图G是连通图当且仅当它的可达性矩阵P的所有元素均为1。,无向图G=中结点之间的可达关系R的每个等价类导出的子图都称为G的一个连通分支(Connected Component)。用p(G)表示G中的连通分支个数。 显然，无向图G是连通图当且仅当p(G) = 1；每个结点和每条边都在且仅在一个连通分支中。,有向图的连通性,定义9.3.5 设G = 是一个有向图， 略去G中所

46、有有向边的方向得无向图G，如果无向图G是连通图，则称有向图G是连通图或称为弱连通图(Weakly Connected Graph)。否则称G是非连通图； 若G中任何一对结点之间至少有一个结点到另一个结点是可达的，则称G是单向连通图(Unilaterally Connected Graph)； 若G中任何一对结点之间都是相互可达的，则称G是强连通图(Strongly Connected Graph)。,定理9.3.7 有向图G是强连通图的充分必要条件是G中存在一条经过所有结点的回路。,树,连通而不含回路的无向图称为无向树(Undirected Tree)，简称树(Tree)，常用T表示树。 树中

47、度数为1的结点称为叶(Leaf)；度数大于1的结点称为分支点(Branch Point)或内部结点(Interior Point) 每个连通分支都是树的无向图称为森林(Forest)。 平凡图称为平凡树(Trivial Tree)。 树中没有环和平行边，因此一定是简单图;在任何非平凡树中，都无度数为0的结点。,树的性质,定理10.2.1 设无向图G = ，|V| = n，|E| = m，下列各命题是等价的： G连通而不含回路(即G是树)； G中无回路，且m = n-1； G是连通的，且m = n-1； G中无回路，但在G中任二结点之间增加一条新边，就得到惟一的一条基本回路； G是连通的，但删除

48、G中任一条边后，便不连通；(n2) G中每一对结点之间有惟一一条基本通路。(n2),生成树,定义10.2.2 给定图G = ，若G的某个生成子图是树，则称之为G的生成树(Spanning Tree)，记为TG。生成树TG中的边称为树枝(Branch)；G中不在TG中的边称为弦(Chord)；TG的所有弦的集合称为生成树的补(Complement)。 定理10.2.3 一个图G = 存在生成树TG = 的充分必要条件是G是连通的。,算法,算法10.2.1 求连通图G = 的生成树的破圈法： 每次删除回路中的一条边，其删除的边的总数为m-n+1。 算法10.2.2 求连通图G = 的生成树的避圈法

49、： 每次选取G中一条与已选取的边不构成回路的边，选取的边的总数为n-1。 由于删除回路上的边和选择不构成任何回路的边有多种选法，所以产生的生成树不是惟一的。,最小生成树,定义10.2.3 设G = 是连通的赋权图，T是G的一棵生成树，T的每个树枝所赋权值之和称为T的权(Weight)，记为w(T)。G中具有最小权的生成树称为G的最小生成树(Minimal Spanning Tree)。,算法10.2.3 Kruskal算法,（1）在G中选取最小权边e1，置i = 1。 （2）当i = n-1时，结束，否则转(3)。 （3）设已选取的边为e1, e2, , ei，在G中选取不同于e1, e2,

50、, ei的边ei+1，使e1, e2, , ei, ei+1中无回路且ei+1是满足此条件的最小权边。 （4）置i = i+1，转(2)。,算法10.2.5 Prim算法,（1）在G中任意选取一个结点v1，置VT = v1, ET = ，k = 1； （2）在V-VT中选取与某个viVT邻接的结点vj，使得边(vi, vj)的权最小，置VT = VTvj, ET = ET(vi, vj)，k = k+1； （3）重复步骤2，直到k = |V|。,根树,一棵非平凡的有向树，如果恰有一个结点的入度为0，其余所有结点的入度均为1，则称之为根树(Root Tree)或外向树(Outward Tree)

51、。 入度为0的结点称为根(Root)；出度为0的结点称为叶(Leaf)；入度为1，出度大于0的结点称为内点(Interior Point)；又将内点和根统称为分支点(Branch Point)。 在根树中，从根到任一结点v的通路长度，称为该结点的层数(Layer Number)；称层数相同的结点在同一层上；所有结点的层数中最大的称为根树的高(Height)。,在根树T中， 若每个分支点至多有k个儿子，则称T为k元树(k-ary Tree)； 若每个分支点都恰有k个儿子，则称T为k元完全树(k-ary Complete Tree)； 若k元树T是有序的，则称T为k元有序树(k-ary Order

52、ed Tree)； 若k元完全树T是有序的，则称T为k元有序完全树(k-ary Ordered Complete Tree)。,k元完全树中分支点与叶结点数目之间的关系 : 定理10.3.1 在k元完全树中，若叶数为t，分支点数为i，则下式成立： (k-1)i = t-1,遍历算法,二元树的先根次序遍历算法： 访问根； 按先根次序遍历根的左子树； 按先根次序遍历根的右子树。 二元树的中根次序遍历算法： 二元树的后根次序遍历算法：,最优树算法10.3.6 哈夫曼算法：,初始：令S = W1, W2, , Wt； 从S中取出两个最小的权Wi和Wj，画结点vi，带权Wi，画结点vj，带权Wj。画vi

53、和vj的父亲v，连接vi和v，vj和v，令v带权Wi+Wj； 令S = (S -Wi, Wj)Wi+Wj； 判断S是否只含一个元素？若是，则停止，否则转2。,欧拉图,设G是无孤立结点的图，若存在一条通路(回路)，经过图中每边一次且仅一次，则称此通路(回路)为该图的一条欧拉通路(回路)(Eulerian Entry/Circuit)。具有欧拉回路的图称为欧拉图(Eulerian Graph)。 规定：平凡图为欧拉图。 以上定义既适合无向图，又适合有向图。,欧拉通路和欧拉回路的特征,欧拉通路是经过图中所有边的通路中长度最短的通路，即为通过图中所有边的简单通路； 欧拉回路是经过图中所有边的回路中长度

54、最短的回路，即为通过图中所有边的简单回路。 如果仅用边来描述，欧拉通路和欧拉回路就是图中所有边的一种全排列。,欧拉图的判定,定理11.2.1 无向图G = 具有一条欧拉通路，当且仅当G是连通的，且仅有零个或两个奇度数结点。 推论11.2.1 无向图G = 具有一条欧拉回路，当且仅当G是连通的，并且所有结点的度数均为偶数。,欧拉图的判定,定理11.2.2 有向图G具有一条欧拉通路，当且仅当G是连通的，且除了两个结点以外，其余结点的入度等于出度，而这例外的两个结点中，一个结点的入度比出度大1，另一个结点的出度比入度大1。 推论11.2.2 有向图G具有一条欧拉回路，当且仅当G是连通的，且所有结点的

55、入度等于出度。,11.2.4 欧拉图的应用,1、一笔画问题 所谓“一笔画问题”就是画一个图形，笔不离纸，每条边只画一次而不许重复，画完该图。 “一笔画问题”本质上就是一个无向图是否存在欧拉通路(回路)的问题。如果该图为欧拉图，则能够一笔画完该图，并且笔又回到出发点；如果该图只存在欧拉通路，则能够一笔画完该图，但笔回不到出发点；如果该图中不存在欧拉通路，则不能一笔画完该图。,2、蚂蚁比赛问题,例11.2.4 甲、乙两只蚂蚁分别位于图的结点A、B处，并设图中的边长度相等。甲、乙进行比赛：从它们所在的结点出发，走过图中所有边最后到达结点C处。如果它们的速度相同，问谁先到达目的地？,解 图中仅有两个度

56、数为奇数的结点B、C，因而存在从B到C的欧拉通路，蚂蚁乙走到C只要走一条欧拉通路，边数为9条，而蚂蚁甲要想走完所有的边到达C，至少要先走一条边到达B，再走一条欧拉通路，因而它至少要走10条边才能到达C，所以乙必胜。,哈密顿图,定义11.3.1 经过图中每个结点一次且仅一次的通路(回路)称为哈密顿通路(回路)(Hamiltonian Entry/circuit)。存在哈密顿回路的图称为哈密顿图(Hamiltonian Graph)。 规定：平凡图为哈密顿图。 以上定义既适合无向图，又适合有向图。,哈密顿通路和哈密顿回路的特征,哈密顿通路是经过图中所有结点的通路中长度最短的通路，即为通过图中所有结

57、点的基本通路； 哈密顿回路是经过图中所有结点的回路中长度最短的回路，即为通过图中所有结点的基本回路。 仅用结点来描述: 哈密顿通路就是图中所有结点的一种全排列 哈密顿回路就是图中所有结点的一种全排列再加上该排列中第一个结点的一种排列。,哈密顿图的判定,定理11.3.1 设无向图G = 是哈密顿图，V1是V的任意非空子集，则 p(G-V1) |V1| 其中p(G-V1)是从G中删除V1后所得到图的连通分支数。,推论11.3.1 设无向图G = 中存在哈密顿通路，则对V的任意非空子集V1，都有 p(G-V1) |V1| + 1,定理11.3.2 设G = 是具有n个结点的简单无向图。如果对任意两个

58、不相邻的结点u, vV，均有 deg(u)+deg(v)n-1 则G中存在哈密顿通路。,推论11.3.2 设G = 是具有n个结点的简单无向图。如果对任意两个不相邻的结点u, vV，均有 deg(u)+deg(v)n 则G中存在哈密顿回路。,推论11.3.3 设G = 是具有n个结点的简单无向图，n3。如果对任意vV，均有deg(v) n/2，则G是哈密顿图。,例11.3.3,某地有5个风景点，若每个风景点均有2条道路与其他点相通。问游人可否经过每个风景点恰好一次而游完这5处？ 解 将5个风景点看成是有5个结点的无向图，两风景点间的道路看成是无向图的边，因为每处均有两条道路与其他结点相通，故每

59、个结点的度数均为2，从而任意两个不相邻的结点的度数之和等于4，正好为总结点数减1。故此图中存在一条哈密顿通路，因此游人可以经过每个风景点恰好一次而游完这5处。,定理11.3.3,设G = 是有n(n2)个结点的一些简单有向图。如果忽略G中边的方向所得的无向图中含生成子图Kn，则有向图G中存在哈密顿通路。,在右图中，它所对应的无向图中含完全图K5，由定理11.3.3知，图中含有哈密顿通路。事实上，通路v3v5v4v2v1为一条哈密顿通路。,偶图,11.4.1 偶图的定义 定义11.4.1 若无向图G = 的结点集V能够划分为两个子集V1, V2，满足V1V2 = ，且V1V2 = V，使得G中任意一条边的两个端点，一个属于V1，另一个属于V2，则称G为偶图(Bipartite Graph)或二分图(Bigraph)。V1和V2称为互补结点子集，偶图通常记为G=。 偶图没有自回路(环)。 平凡图