离散数学教程课件

离散数学数学与信息科学学院离散数学数学与信息科学学院1第一部分数理逻辑第二部分集合论第三部分图论第四部分抽象代数离散数学第一部分数理逻辑离散数学2第一部分数理逻辑数理逻辑是用数学方法研究推理中前提和结论之间的形式关系的学科。推理是由一个或几个判断推出一个新判断的思维形式。数学方法是指建立一套表意符号体系，对具体事物进行抽象的形式研究的方法。第一部分数理逻辑数理逻辑是用数学方法研究推理中前提和推理3第一章命题逻辑第二章一阶谓词逻辑第一部分数理逻辑第一章命题逻辑第一部分数理逻辑41.1命题和命题联结词1.2命题公式及其赋值1.3等值演算与联结词完备集1.4析取范式与合取范式1.5推理的形式结构1.6自然推理系统P第一章命题逻辑1.1命题和命题联结词第一章命题逻辑51.命题：能判断真假的陈述句。包含两层意思：（1）必须是陈述句。（2）能够确定（分辨）其真值。1.1命题和命题联结词1.命题：能判断真假的陈述句。包含两层意思：（1）必须是陈61.1命题和命题联结词1.1命题和命题联结词72.命题的真值：判断结果注意：此处不纠缠具体命题的真假问题，只是将其作为数学概念来处理。真值：真用T或1表示，假用F或0表示。3.命题和真值的符号化1.1命题和命题联结词2.命题的真值：判断结果注意：此处不纠缠具体命题的真假问题81.1命题和命题联结词1.1命题和命题联结词9原子命题：不能被分解为更简单的陈述句复合命题：原子命题通过联结词联结而成例：2是有理数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数。p：2是有理数，q：2是偶数，r：2是素数，s：3是素数，t：4是素数。1.1命题和命题联结词原子命题：不能被分解为更简单的陈述句例：2是有理数是不对的；104、命题联结词ppTFFT1.1命题和命题联结词4、命题联结词ppTFFT1.1命题和命题联结词11pqpqFFFFTFTFFTTT王化不但成绩好而且品德好。p∧q：1.1命题和命题联结词pqpqFFFFTFTFFTTT王化不但成绩好而且品德好12pqpqFFFFTTTFTTTT1.1命题和命题联结词开关坏了或灯泡坏了。p∨q：pqpqFFFFTTTFTTTT1.1命题和命题13例：1.张晓婧爱唱歌或爱听音乐。2.张晓婧是内蒙人或是陕西人。3.张晓婧只能挑选202或203房间。1.1命题和命题联结词注意：当排斥或两边的情况实际根本不可能同时发生的时候，排斥或也可抽象为∨。但为了方便起见一般不这样抽象。例：1.张晓婧爱唱歌或爱听音乐。1.1命题和命题联结词14pqpqFFTFTTTFFTTT有位父亲对儿子说：“如果我去书店，就一定给你买电脑报“。问：在什么情况下，父亲算失信呢？1.1命题和命题联结词pqpqFFTFTTTFFTTT有位父亲对儿子说：“如15注意：①“只要p，就q‘，’因为p，所以q”，“p仅当q”，‘只有q，才p“，”除非q才p“，”除非q，否则非p“都可抽象为p→q。②p，q可以没有任何内在联系。例：1.如果3＋3＝6，那么雪是白的。2.除非我能工作完成了，我才去看电影。3.只要天下雨，我就回家。4.我回家仅当天下雨。p→q的逻辑关系为q是p的必要条件或p是q的充分条件。1.1命题和命题联结词注意：①“只要p，就q‘，’因为p，所以q”，“p仅当q”，16pqpqFFTFTFTFFTTT1.1命题和命题联结词pq的逻辑关系为p与q互为充要条件例：1.3是有理数当且仅当加拿大位于亚洲。2.两圆的面积相等，则他们的半径相等，反之亦然。pqpqFFTFTFTFFTTT1.1命题和命题17pqpqFFFFTTTFTTTF1.1命题和命题联结词例：今天第一节课上离散数学或数据结构。pqpqFFFFTTTFTTTF1.1命题和命18例：p：北京比天津人口多q：2＋2＝4r：乌鸦是黑色的1.1命题和命题联结词例：p：北京比天津人口多q：2＋2＝4195、语句形式化1.1命题和命题联结词例：2是有理数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数。p：2是有理数，q：2是偶数，r：2是素数，s：3是素数，t：4是素数。p不对；q且r；r或t；如果r，则s；r当且仅当s。5、语句形式化1.1命题和命题联结词例：2是有理数是不201.1命题和命题联结词1.1命题和命题联结词21命题常元：表示具体确定内容的命题。命题变元：表示不确定具体内容的命题。1.2命题公式及其赋值命题常元：表示具体确定内容的命题。1.2命题公式及其赋221.2命题公式及其赋值同时约定：（1）最外层的括号可以省去。（2）不影响运算次序的括号也可以省去。1.2命题公式及其赋值同时约定：（1）最外层的括号可以231.2命题公式及其赋值1.2命题公式及其赋值241.2命题公式及其赋值1.2命题公式及其赋值251.2命题公式及其赋值1.2命题公式及其赋值261.2命题公式及其赋值1.2命题公式及其赋值271.2命题公式及其赋值1.2命题公式及其赋值281.3命题公式的等值式1.3命题公式的等值式29基本等值式（A，B，C为任意命题公式）1.3命题公式的等值式基本等值式（A，B，C为任意命题公式）1.3命题公式的等值301.3命题公式的等值式1.3命题公式的等值式31因A，B，C可以代入任意的命题公式，故以上等值式称为等值式模式。由已知的等值式推演出另外一些等值式的过程为等值演算。1.3命题公式的等值式因A，B，C可以代入任意的命题公式，故以上等值式称为等值式模32等值演算的应用：1.验证等值式2.判定公式的类型3.解决工作生活中的判断问题1.3命题公式的等值式甲、已、丙3人根据口音对王教授是哪人进行了判断：甲说：王教授不是苏州人，是上海人已说：王教授不是上海人，是苏州人丙说：王教授既不是上海人，也不是杭州人结果3人中有一人全对，一人对一半，一人全错。问王教授是哪人？等值演算的应用：1.3命题公式的等值式甲、已、丙3人根据口33联结词的完备集n个命题变元可以形成22n个不同的真值函数对于每个真值函数，都可以找到许多与之等值的命题公式，而每个命题公式对应唯一的与之等值的真值函数。定义.设S是一个联结词集合，如果任何n（n≥1）元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。联结词的完备集n个命题变元可以形成22n个不同的真值函数对于34联结词的完备集联结词的完备集351.4析取范式与合取范式定义：命题变元及其否定统称为文字。仅由有限个文字构成的析取式称为简单（质）析取式。仅由有限个文字构成的合取式称为简单（质）合取式。注意：单个文字既是简单析取式又是简单合取式。讨论：设A为含n个文字的简单析取式若A中同时含pi和﹁pi，则？若A为永真式，则？1.4析取范式与合取范式定义：命题变元及其否定统称为文字。36若A为永真式，则A中必同时含有pi和﹁pi，反之亦然。同理有，若A为简单合取式，A为永假式的充要条件是A中同时含有pi和﹁pi。定理1.①一个简单析取式是重言式当且仅当它同时含有某个命题变元及其他的否定。②一个简单合取式是矛盾式当且仅当它同时含有某个命题变元及其他的否定。1.4析取范式与合取范式若A为永真式，则A中必同时含有pi和﹁pi，反之亦然。同理有37定义：①由有限个简单合取式构成的析取式称为析取范式。②由有限个简单析取式构成的合取式称为合取范式。③析取范式与合取范式称为范式。注意：单个文字、简单析取式、简单合取式都既是析取范式又是合取范式。1.4析取范式与合取范式定理2.①一个析取范式是矛盾式当且仅当它的每个简单合取式为矛盾式。②一个合取范式是重言式当且仅当它的每个简单析取式为重言式。定义：①由有限个简单合取式构成的析取式称为析取范式。注意：单38定理3.任一命题公式都存在与之等值的析取范式和合取范式。范式的求法：①消去公式中的蕴涵、等价和异或联结词②使用双重否定律和德摩根律，将公式中出现的否定词移到命题变元之前。③利用分配律、结合律将公式化为合（析）取范式。范式形式不唯一。1.4析取范式与合取范式定理3.任一命题公式都存在与之等值的析取范式和合取范式。范式39定义：在含有n个命题变元的简单合（析）取式中，若每个命题变元和它的否定式不同时出现，而二者之一必出现且仅出现一次，且第i个命题变元或它的否定是出现在从左算起的第i位上（字典序），称这样的简单合（析）取式为极小（大）项。性质：①n个变元可以形成2n个极小（大）项；②每个极小（大）项有且仅有一个成真（假）赋值；③每组赋值下仅有一个极小（大）项为真（假）；④所有极小（大）项的析（合）取为真（假）；1.4析取范式与合取范式定义：在含有n个命题变元的简单合（析）取式中，若每个性质：①40将极小项的成真赋值对应的二进制数转化为十进制数为i，将对应的极小项记为mi。将极大项的成假赋值对应的二进制数转化为十进制数为i，将对应的极大项记为Mi。定义：设由n个命题变元构成的析（合）取范式中所有的简单合（析）取式都是极小（大）项，则称该析取范式为主析（合）取范式。1.4析取范式与合取范式定理.任何命题公式都存在与之等值的主析取范式和主合取范式，并且是唯一的。将极小项的成真赋值对应的二进制数转化为十进制数为i，定义：设411.4析取范式与合取范式公式法：①求析取范式②用同一律补进未出现的命题变元③消去永假或重复出现的变元和极小项④将极小项按下标从小到大排列真值表法：列出公式及各极小项的真值表，将每组赋值下公式及极小项真值都为真的极小项进行析取。主析取范式的求法：1.公式法2.真值表法1.4析取范式与合取范式公式法：①求析取范式真值表法：列出421.4析取范式与合取范式应用：1.求公式的成真、成假赋值成真赋值为析取范式中所含极小项的编码的二进制数成假赋值为合取范式中所含极大项的编码的二进制数由主析取范式可以直接求主合取范式：1>求出主析取范式中未包含的极小项2>求出与1>中求出的极小项下标相同的极大项3>做2>中极大项之合取1.4析取范式与合取范式应用：1.求公式的成真、成假赋值由431.4析取范式与合取范式3.判断两公式是否等值若A，B共含有n个命题变元，按n个命题变元求出A与B的主析取范式A’、B’，若A’＝B‘，则A

B.2.判断公式的类型设A含有n个命题变元①A为重言式当且仅当A的主析取范式含全部2n个极小项；②A为矛盾式当且仅当A的主析取范式不含任何极小项，此时记为0；③A为可满足式当且仅当A的主析取范式中至少含一个极小项。1.4析取范式与合取范式3.判断两公式是否等值2.判断公式44例：要在A，B，C中挑选2名出国进修，选派时满足下列条件：①若A去，则C同去②若B去，则C不能去③若C不去，则A或B可以去问有几种选派方案，分别是什么？4.解决实际问题1.4析取范式与合取范式例：要在A，B，C中挑选2名出国进修，选派时满足下列条件：4451.5推理的形式结构注意：①推理正确实际是排除前提真结论假的情况②推理是否正确与前提的排列顺序无关③推理正确并不能保证B一定为真1.5推理的形式结构注意：461.5推理的形式结构推理的形式结构1.5推理的形式结构推理的形式结构471.5推理的形式结构1.5推理的形式结构48例：若下午温度超过30度，则王晓燕必去游泳。若她去游泳，她就不会去看电影。所以若王晓燕没去看电影，下午温度必超过了30度。p：温度超过30度q：王晓燕去游泳r：王晓燕去看电影1.5推理的形式结构例：若下午温度超过30度，则王晓燕必去游泳。若她去游p：温度491.5推理的形式结构1.5推理的形式结构50注意：①以上都是蕴含式模式②若某推理的形式结构与某定律一致，则推理正确③成立的等值式可产生两条定律④推理定律可产生相应的推理规则1.5推理的形式结构注意：1.5推理的形式结构511.6自然推理系统P定义.一个形式系统I由以下4部分组成：

①非空的字母表，记作A(I)②A(I)中符号构成的合式公式集，记作E(I)③E(I)中特殊的公式组成的公理集，记作Ax(I)

④推理规则集，记作R(I)任给的前提，应用规则得到结论（可能真）任给的公理，应用规则得到结论（永真）1.6自然推理系统P定义.一个形式系统I由以下4部分组成：任521.6自然推理系统P1.6自然推理系统P531.6自然推理系统P1.6自然推理系统P54例：若小王是理科生，则他的数学成绩一定很好。如果小王不是理科生，他一定是文科生。小王的数学成绩不好。所以小王是文科生。p：小王是理科生q：小王是文科生r：小王的数学成绩很好1.6自然推理系统P例：若小王是理科生，则他的数学成绩一定很好。如果p：小王是理55例：如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。p：小张去看电影q：小王去看电影r：小李去看电影s：小赵去看电影1.6自然推理系统P例：如果小张和小王去看电影，则小李也去看电影。小赵p：小张去562.归谬法将结论的否定作为前提引入，能推出矛盾来，则推理正确例：如果马会飞或羊不吃草，则母鸡就会是飞鸟。如果母鸡是飞鸟，那么烤熟的鸭子还会跑。烤熟的鸭子不会跑。所以羊吃草。p：马会飞q：羊吃草r：母鸡是飞鸟s：烤熟的鸭子会跑1.6自然推理系统P2.归谬法例：如果马会飞或羊不吃草，则母鸡就会是飞鸟。如果母57所有的人总是要死的。苏格拉底是人。所以苏格拉底是要死的。p:q:r:第二章谓词逻辑所有的人总是要死的。p:第二章谓词逻辑58第二章谓词逻辑2.1一阶逻辑命题符号化2.2一阶逻辑公式及解释2.3一阶逻辑等值式与置换规则2.4一阶逻辑前束范式2.5一阶逻辑的推理理论第二章谓词逻辑2.1一阶逻辑命题符号化592.1一阶逻辑命题符号化1.个体词所研究对象中可以独立存在的具体的或抽象的客体（事物）表示具体的或特定的客体表示抽象或泛指的客体个体变项的取值范围称为个体域，用D表示宇宙间一切事物组成的称为全总个体域2.1一阶逻辑命题符号化1.个体词所研究对象中可以独立存在的602.谓词用来刻划个体词性质及个体词之间相互关系的词2是有理数x是无理数小王与小李同岁x与y具有关系L……是有理数……是无理数……与……同岁……与……具有关系LF：G：H：L：2.1一阶逻辑命题符号化2.谓词用来刻划个体词性质及个体词之间相互关系的词2是有理数613.量词：个体词之间的数量关系（1）全称量词“一切的”，“所有的”，“每一个”，“任意的”，“凡”，“都”记作4.符号化①确定个体域②确定个体词、量词和谓词③确定联结词2.1一阶逻辑命题符号化3.量词：个体词之间的数量关系（1）全称量词4.符号化①62例：所有的人都是要死的。有的人用左手写字。注意：①全称量词的特性谓词必须作为蕴涵式的前件引入②存在量词的特性谓词必须作为合取式的合取项引入③同一命题，不同的个体域符号化的形式可能不同④未指明个体域即为全总个体域2.1一阶逻辑命题符号化例：所有的人都是要死的。注意：2.1一阶逻辑命题符号化63例：在美国留学的学生未必都是亚洲人。有的兔子比所有的乌龟跑的快。对任意的整数x，都存在整数y使得x＋y＝10。注意：①多个量词出现时，顺序一般不能随便换②有些命题符号化形式不唯一2.1一阶逻辑命题符号化例：在美国留学的学生未必都是亚洲人。注意：2.1一阶逻辑命题642.2一阶逻辑公式及解释2.2一阶逻辑公式及解释652.2一阶逻辑公式及解释2.2一阶逻辑公式及解释66合式公式也称谓词公式，简称公式2.2一阶逻辑公式及解释合式公式也称谓词公式，简称公式2.2一阶逻辑公式及解释672.2一阶逻辑公式及解释2.2一阶逻辑公式及解释682.2一阶逻辑公式及解释2.2一阶逻辑公式及解释692.2一阶逻辑公式及解释2.2一阶逻辑公式及解释70定理.闭式在任何解释下都变成命题。2.2一阶逻辑公式及解释定理.闭式在任何解释下都变成命题。2.2一阶逻辑公式及解释712.2一阶逻辑公式及解释2.2一阶逻辑公式及解释72定理.重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。2.2一阶逻辑公式及解释定理.重言式的代换实例都是永真式，矛盾式的代换2.2一阶逻辑732.3一阶逻辑等值式与置换规则第一组

命题逻辑中等值式模式的代换实例都是一阶逻辑的等值式模式第二组一阶逻辑中特殊的等值式2.3一阶逻辑等值式与置换规则第一组命题逻辑中等值式模式742.3一阶逻辑等值式与置换规则2.3一阶逻辑等值式与置换规则75D=N，F(x)：x是奇数G(x)：x是偶数2.3一阶逻辑等值式与置换规则D=N，F(x)：x是奇数G(x)：x是偶数2.3一阶762.3一阶逻辑等值式与置换规则2.3一阶逻辑等值式与置换规则772.3一阶逻辑等值式与置换规则2.3一阶逻辑等值式与置换规则782.4一阶逻辑前束范式为了方便使用谓词公式进行定理证明和逻辑推理，需要把谓词公式变换为便于使用的规范形式，就是范式。2.4一阶逻辑前束范式为了方便使用谓词公式进行定理证明和逻辑79定理1：任一谓词公式都可以化成为与之等值的前束范式。2.4一阶逻辑前束范式定理1：任一谓词公式都可以化成为与之等值的前束范式。2.4一802.4一阶逻辑前束范式2.4一阶逻辑前束范式812.5一阶逻辑的推理理论在一阶逻辑中，称永真的蕴涵式为推理定律。若一个推理的形式结构正是某条推理定律，则该推理显然是正确的。第一组命题逻辑推理定律的代换实例第二组由基本等值式生成的推理定律第三组以下重要定律2.5一阶逻辑的推理理论在一阶逻辑中，称永真的蕴涵式为推理定82第四组消去量词和引入量词的推理规则1、全称量词消去规则（UI）2.5一阶逻辑的推理理论第四组消去量词和引入量词的推理规则1、全称量词消去规则（83UI规则成立的条件：（1）取代x的y应为任意不在A(x)中约束出现的个体变项；（2）用y取代A(x)中自由出现的x时，必须将所有的自由出现x都取代；（3）自由变元y也可替换为个体域中任意的个体常元c，c为任意不在A(x)中出现过的个体常项。2.5一阶逻辑的推理理论UI规则成立的条件：84含义：如果个体域的所有个体都具有性质A，则个体域中的任一个个体都具有性质A。2、存在量词消去规则（EI）含义：如果个体域存在有性质A的个体，则个体域中必有某一个个体具有性质A。2.5一阶逻辑的推理理论含义：如果个体域的所有个体都具有性质A，则个体域中2、存在量85ES规则成立的条件：（1）c是个体域中使A为真的特定的个体常项；（2）c不曾在A(x)或前面的推导公式中出现过；（3）A（x）中除x外还有其他自由变元时，不能用此规则2.5一阶逻辑的推理理论ES规则成立的条件：863、全称量词引入规则（UG）UG规则成立的条件：（1）y在A（y）中自由出现，且y取任何值时A均为真；（2）x不在A（y）中约束出现。含义：如果个体域的任意个体都具有性质A，则个体域中的所有个体都具有性质A。2.5一阶逻辑的推理理论3、全称量词引入规则（UG）UG规则成立的条件：874、存在量词引入规则（EG）EG规则成立的条件：（1）c是个体域中某个确定的个体；（2）代替c的x不在A（c）中出现过。含义：如果个体域有某一个个体c具有性质A，则个体域中必存在具有性质A的个体。2.5一阶逻辑的推理理论4、存在量词引入规则（EG）EG规则成立的条件：88定义.一阶逻辑自然推理系统F的定义1.字母表：同一阶语言的字母表2.合式公式：同一阶语言合式公式的定义3.推理规则a.前提引入规则b.结论引入规则c.置换规则d.假言推理规则e.附加规则f.化简规则g.拒取式规则h.假言三段论规则i.析取三段论规则j.构造性二难规则k.合取引入规则l.UI，EI，UG，EG2.5一阶逻辑的推理理论定义.一阶逻辑自然推理系统F的定义2.5一阶逻辑的推理理论89例7：证明逻辑三段论所有的人总是要死的。苏格拉底是人。所以苏格拉底是要死的。2.5一阶逻辑的推理理论例7：证明逻辑三段论2.5一阶逻辑的推理理论902.5一阶逻辑的推理理论例10：如果一个人怕困难就不会获得成功。每一个人或者获得成功或者是失败的。有些人未曾失败过，所以有些人不怕困难。（个体域是人的集合）判断这个推理是否正确。例9：根据前提集合：同事之间总是有工作矛盾的，张平和李明没有工作矛盾，能得出什么结论？2.5一阶逻辑的推理理论例10：如果一个人怕困难就不会获得成91第二部分集合论第三章集合代数第四章二元关系第五章函数第二部分集合论第三章集合代数92第三章集合代数3.1集合的基本概念3.2集合的运算3.3集合恒等式第三章集合代数3.1集合的基本概念93一、集合的概念

集合（set)的含义：一个集合是作为整体识别的、确定的、互相区别的一些事物的聚集（全体或总体等)。 构成一个集合的每个事物，成为这个集合中的元素或成员。集合一般用A、B、C……表示，集合中的元素用a、b、c……表示。但这不是绝对的，因为一个集合可以作为另一个集合的元素。 如果x是集合s的一个元素,记作 ;y不是集合s的元素，记作

3.1集合的基本概念一、集合的概念3.1集合的基本概念94例1：1.偶素数集合。 2.二进制的基数集合。 3.英文字母的集合。 4.全体实数的集合。 5.自然数集合。 6.整数集合。 7.有理数集合。 8.素数集合。3.1集合的基本概念例1：1.偶素数集合。3.1集合的基本概念953.1集合的基本概念集合的表示方法:1.列举法（枚举法、外延法） 把集合的所有元素（元素较少时）写在一个花括号内;列出足够多的元素（元素很多或无穷时）以反映集合中元素的特征。 如例1中的1、2、3、5可分别表示为： {2} {0，1} {a，b，c……z，A，B，C……Z} {1，2，3……}3.1集合的基本概念集合的表示方法:963.1集合的基本概念2.描述法（概括法） 将集合中的元素的性质用一个谓词公式来描述，S={X|P(X)},意义为:集合S由且仅由满足为此公式P(X)的对象组成，即 ，当且仅当p(a)为真。如例1中的4、6、7可表示为：3.文氏图用图形图像直观的描述集合之间的相互关系和有关运算。3.1集合的基本概念2.描述法（概括法）3.文氏图973.1集合的基本概念几个常见集合的表示符号：N：自然数集合，N={0，1，2，3……}；I：整数集合；P：素数或质数集合；Q：有理数集合；R：实数集合；C：复数集合；3.1集合的基本概念几个常见集合的表示符号：983.1集合的基本概念集合的特性:A.互异性：一个集合的个元素是可以区分开的，即每一 元素只出现一次。B.无序性：集合中元素排列顺序无关紧要，即集合表示 形式的不唯一性。例2：{a，b，c}={b，c，a}={c，a，b}={a，c，b}= {b，a，c}={c，b，a}3.1集合的基本概念集合的特性:993.1集合的基本概念C.确定性：任一事物是否属于某一集合，回答是确定的。例3：“好书”的全体，这不构成集合。注意：一个集合是已知的，指的是对任一元素，利用某种方法可以判断它是否是这个集合的元素，而不是把集合的每一个元素都给出来。3.1集合的基本概念C.确定性：任一事物是否属于某一集合，回1003.1集合的基本概念集合的元素可以是任何具体或抽象的事物，包括别的集合，但不能是本集合自身。例4：在一个住着一些人家的偏僻孤岛上，岛上 只有一个理发师a，a给且只给岛上所有不 能自己理发的人理发。问谁给a理发？3.1集合的基本概念集合的元素可以是任何具体或抽象的事物，包101定义1.设A和B是两个集合，若A中的每一个元素都是B的元素，则称A是B的子集，也称B包含A,记作3.1集合的基本概念定义2.设A和B是任意两个集合，若A包含B且B包含A， 则称A与B相等，记作A=B.即，二、集合的关系定义1.设A和B是两个集合，若A中的每一个元素都是B的元素，1023.1集合的基本概念定义3.若A是B的子集且 ，则称A为B的真子集，或称B真包含A，记作 ，B称为A的超集。3.1集合的基本概念定义3.若A是B的子集且 ，则称103集合的相等关系的性质：设A,B,C为3个集合，集合的包含关系的性质:3.1集合的基本概念集合的相等关系的性质：设A,B,C为3个集合，3.1集合的基104定义4.不包含任何元素的集合称为空集，记作 或{}3.1集合的基本概念三、特殊集合定义4.不包含任何元素的集合称为空集，记作 或{}3.1集合105定义4：在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集，记作E。定义5.集合中元素的个数称为基数或势，用|A|表示。基数是有限数的集合称为有限集，否则称为无限集。 全集是相对的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集。3.1集合的基本概念定义4：在一定范围内，如果所有集合均为某一集合的子集，则称该1063.1集合的基本概念含n个元素的集合简称n元集，其含有k(k<n)个元素的子集称为它的k元子集。定义6.由集合S的所有子集组成的集合，称为集合S的幂 集，记作P（S）。表示为：有限集S，|P（S）|=2|S|例：A＝{a，{b，c}，d，{c}}3.1集合的基本概念含n个元素的集合简称n元集，其含有k(k1073.2 集合的运算一、集合的基本运算3.2 集合的运算一、集合的基本运算1083.2 集合的运算定义5.设A为集合，A的元素的元素构成的集合称为A的广义并，记作∪A。3.2 集合的运算定义5.设A为集合，A的元素的1093.2 集合的运算∪A＝{x|∃z(z∈A∧x∈z)}若A＝{A1,A2,……，An}，则∪A＝A1∪A2∪……∪An

定义6.设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记作∩A。∩A＝{x|∀z(z∈A→x∈z)}若A＝{A1,A2,……，An}，则∩A＝A1∩

A2∩

……∩

An

例：A＝{{a，b，c}，{a，b}，e}B={{a}}C={a，{c，d}}3.2 集合的运算∪A＝{x|∃z(z∈A∧x110集合运算的优先级：高级：广义并、广义交、绝对补、求幂集；同级按从右向左的顺序进行低级：并、交、相对补和对称差；同级按从左向右的顺序进行3.2 集合的运算集合运算的优先级：3.2 集合的运算1113.2 集合的运算文氏图可以用来描述集合间的关系及其运算.在文氏图中,全集用矩形表示,子集用圆形表示,阴影部分表示运算结果的集合.二、文氏图ABBABABA3.2 集合的运算文氏图可以用来描述集合间的关系及其运1123.2 集合的运算A3.2 集合的运算A1133.3 集合恒等式一、集合运算定律以下列出集合性质中最主要的几条基本定律，对于全集E的任意子集A，B，C，有：3.3 集合恒等式一、集合运算定律以下列出集合性质中最主要的1143.3 集合恒等式3.3 集合恒等式1151、基本定义法根据集合相等的充要条件等式两边互为子集或由定义进行等价推理。2、公式法利用已证明过的恒等式去证明另外的恒等式。若表达式中出现形为A-B的差集时，用功能完备律先将运算“-”转化为运算“”和“~”。二、集合恒等式证明3.3 集合恒等式1、基本定义法根据集合相等的充要条件等式两边互为子集或由定义1163.3 集合恒等式3.3 集合恒等式1173.3 集合恒等式3.3 集合恒等式1183.3 集合恒等式3.3 集合恒等式119小结集合的概念集合的特性集合的表示方法:列举法、描述法、文氏图集合的运算：并、交、补、差、求幂集合间的关系：包含、相等集合恒等式的证明：定义法、公式法、成员表法小结集合的概念120第四章 二元关系4.1有序对与笛卡儿积4.2二元关系4.3关系的运算4.4关系的性质4.5关系的闭包4.6划分和等价关系4.7偏序关系第四章 二元关系4.1有序对与笛卡儿积121定义1.由两个具有固定次序的个体a，b组成的序列,称为序偶,记作<a,b>.其中a,b称为序偶的分量.定义2.设<a,b>和<c,d>是两个序偶,若a=c且b=d,则称这两个序偶相等,记作<a,b>=<c,d>.区别:集合{a,b}={b,a}<a,b>=<b,a>(a=b)4.1有序对与笛卡儿积定义1.由两个具有固定次序的个体a，b组成的序列,称为序偶,122例3:设A={a,b,c},B={1,0},则4.1有序对与笛卡儿积定义3.设集合A，B，以A的元素作为第一元素，B的元算作为第二元素的有序对构成的集合称为A与B的笛卡儿积，记作A×B，符号化为A×B={<x,y>|x∈A∧y∈B}性质1.A×Ф=Ф，Ф×A=Ф例3:设A={a,b,c},B={1,0},则4.1有序对123例4:设A={a,b},B={0,1},C={u,v}则4.1有序对与笛卡儿积例4:设A={a,b},B={0,1},C={u,v}则4.1244.1有序对与笛卡儿积4.1有序对与笛卡儿积1254.1有序对与笛卡儿积4.1有序对与笛卡儿积126性质5.若A⊆C∧B⊆D，则A×B⊆C×D。4.1有序对与笛卡儿积其逆命题不成立。①A=B=Ф，成立；②A≠Ф，B≠Ф，成立；③A=Ф且

B≠Ф，不成立；④A≠Ф且B=Ф，不成立。性质5.若A⊆C∧B⊆D，则A×B⊆C×D。4.1有127定义4.由n个具有给定次序的个体a1，a2，……，an组成的序列，称为有序n元组，记作<a1，a2，……，an>，其中ai称为第i个分量。<a1，a2，……，an>=<b1，b2，……，bn>当且仅当ai=bi（i=1，2，3，……，n）。有序n元组仍然是序偶，即<a1，a2，……，an>=<<a1，a2，……，an-1>，an>。4.1有序对与笛卡儿积定义4.由n个具有给定次序的个体a1，a2，……，an组成的128定义5.设A1，A2，……，An是任意的n个集合，所有有序n元组<a1，a2，……，an>组成的集合，称为集合A1，A2，……，An的笛卡儿积，并用表示。其中（i=1，2，……，n）4.1有序对与笛卡儿积定义5.设A1，A2，……，An是任意的n个集合，所有有序1294.2二元关系定义1.若一个集合满足以下条件之一：（1）集合非空，且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系。一、关系的定义4.2二元关系定义1.若一个集合满足以下条件之一：一、关系1304.2二元关系例2:任意两个集合A,B,若|A|=n,|B|=m,求A到B共有多少不同的二元关系?4.2二元关系例2:任意两个集合A,B,若|A|=n,|B1314.2二元关系二、特殊关系4.2二元关系二、特殊关系132例5.设A={2,3,4},B={2,3,4,5,6},定义A到B的二元关系R:aRb当且仅当a整除b.求R,MRR={<2，2>，<2，4>，<2，6>，<3，3>，<3，6>，<4，4>}4.2二元关系三、关系的表示方法例5.设A={2,3,4},B={2,3,4,5,6},定义1334.2二元关系一个有限集合A上的关系R还可以用一个称为R的关系图来表示。4.2二元关系一个有限集合A上的关系R还可以用一个称为R的1344.2二元关系aaaadabcde例6：设A={a，b，c，d，e}，A上关系R={<a，d>，<b，a>，<b，b>，<c，c>}，则R的关系图为：4.2二元关系aaaadabcde例6：设A={a，b135例3:设A={1,2,3,4,5,6},B={a,b,c,d},R={<2,a>,<2,b>,<3,b>,<4,d>,<6,d>},求domR,ranR.解:domR={2,3,4,6}ranR={a,b,d}4.3关系的运算例3:设A={1,2,3,4,5,6},B={a,b,c,d136例:1.Z上的关系<的逆是关系>.3.空关系的逆是空关系.例3中R的逆关系R-1={<a,2>,<b,2>,<b,3>,<d,4>,<d,6>}4.3关系的运算例:1.Z上的关系<的逆是关系>.3.空关系的逆是空关系.例1374.3关系的运算例：1.R1={……是……的兄弟}，R2={……是……的父亲}2.A={1，2，3，4，5}，R，S是A上的二元关系R={<1，2>，<3，4>，<2，2>}S={<4，2>，<2，5>，<3，1>，<1，3>}4.3关系的运算例：1.R1={……是……的兄弟}，R21384.3关系的运算关系是以序偶为元素的集合，故可对关系进行集合的运算以产生新的关系。作为关系，绝对补运算是对全关系而言的。4.3关系的运算关系是以序偶为元素的集合，故可对关系进行集1394.3关系的运算2.A={1，2，3，4，5}，R，S是A上的二元关系R={<1，2>，<3，4>，<2，2>}S={<4，2>，<2，5>，<3，1>，<1，3>}由此可知，合成关系不满足交换律，满足结合律。4.3关系的运算2.A={1，2，3，4，5}，R，S1404.3关系的运算4.3关系的运算141定理8.关系矩阵的乘法满足结合律，即MR1（MR2MR3）=（MR1MR2）MR34.3关系的运算定理9.设R1是一个由A1到A2的关系，R2是一个由A2到A3的关系，……，Rn是一个由An到An+1的关系（Ai都是有限集）。它们的关系矩阵分别是MR1，MR2，……，MRn，则合成关系R1R2……Rn的关系矩阵MR1R2……Rn=MR1MR2……MRn。定理8.关系矩阵的乘法满足结合律，即MR1（MR2MR3）=142定义5.设R为A上的关系，n为自然数，则R的n次幂定义为：①R0={<x,x>|x∈A}=IA②Rn+1=Rn∙R4.3关系的运算幂运算的求解：①若R是列举法表示，可进行多次右复合；例：A={a，b，c，d}，R={<a，b>，<c，b>，<b，c>，<c，d>}定义5.设R为A上的关系，n为自然数，则R的n次幂定义为：4143例：设A={a，b，c，d}，R={<a，b>，<c，b>，<b，c>，<c，d>}，则R0，R2，R3，R4。R0={<a，a>，<b，b>，<c，c>，<d，d>}R2={<a，c>，<c，c>，<b，b>，<b，d>}R3={<a，b>，<a，d>，<c，b>，<c，d>，<b，c>}R4={<a，c>，<c，c>，<b，b>，<b，d>}4.3关系的运算例：设A={a，b，c，d}，R={<a，b>，<c，b>，144②若R用关系矩阵M表示，则Rn的关系矩阵是Mn；③若R是用关系图G表示的，则可由G得Rn的关系图G’。G’与G的顶点集合相同，考察G中每个顶点x，若在G中从x出发经过n步长的路径到达顶点y，则在G’中加一条从x到y的边。当把所有顶点都考察完后，就得到G’。4.3关系的运算②若R用关系矩阵M表示，则Rn的关系矩阵是Mn；③若R是用关1454.3关系的运算定理10.幂运算满足指数定律：Rn∙Rm=Rn+m（Rn）m=Rmn幂运算的性质：定理11.设A为n元集，R是A上的关系，则存在s、t∈N，使得Rs=Rt。4.3关系的运算定理10.幂运算满足指数定律：Rn∙R1464.4关系的性质定义1.设R⊆A×A，①若∀x(x∈A→<x,x>∈R)，则称R是自反的；②若∀x(x∈A→<x,x>R)，则称R是反自反的；③若∃x(x∈A∧<x,x>∈R)∧∃y(y∈A∧<y,y>R)，则称R是非自反的。定义2.设R⊆A×A，①若∀x∀y

(x,y∈A∧<x,y>∈R→<y,x>∈R)，则称R是A上的对称关系；②若∀x∀y

(x,y∈A∧

<x,y>∈R∧

<y,x>R→x=y)，则称R是A上的反对称关系；③否则，则称R是A上的非对称关系。4.4关系的性质定义1.设R⊆A×A，定义2.设R⊆A×147空关系既是对称的又是反对称的.非空集合上的空关系是反自反的、对称的、反对称的、可传递的。空集合上的空关系则是自反的、反自反的、对称的、反对称的和可传递的。4.4关系的性质空关系既是对称的又是反对称的.非空集合上的空关系是反自反的、148非空集合上的全关系是自反的、对称的、和可传递的。例2.S={a，b，c}，S上的关系R1={<a，a>，<b，b>，<c，c>，<b，c>}，R2={<a，b>，<b，a>}，R3={<b，b>，<c，c>}例3.在集合S={a，b，c，d}上的关系R：{<b，c>，<c，c>,<c，d>，<d，c>}，判断R的性质。4.4关系的性质定理.设R是A上的二元关系，那么R是传递的当且仅当R∙R⊆R。非空集合上的全关系是自反的、对称的、和可传递的。例2.S={1494.4关系的性质根据定义可证明下面几个定理是成立的。4.4关系的性质根据定义可证明下面几个定理是成立的。1504.4关系的性质4.4关系的性质1514.4关系的性质4.4关系的性质152可能有某种关系，既是对称的，又是反对称的。例4.S={a，b，c}，S上的关系R={<a，a>，<b，b>，<c，c>}某种关系，既不是对称的，也不是反对称的。例5.S上的关系Q={<a，b>，<a，c>，<c，a>}定理5.设R在A上是反自反的和可传递的，则R必是反对称的。4.4关系的性质可能有某种关系，既是对称的，又是反对称的。例4.S={a，b153例6.设A={1，2，3}，A上的关系R={<1，2>}和S={<2，3>}都是A上的传递关系。传递性对并运算不一定保持。4.4关系的性质例6.设A={1，2，3}，A上的关系R={<1，2>}和S154关系的闭包运算是关系上的一元运算，他把给出的关系R扩充成一新关系Rc，使Rc具有一定的性质，且进行的扩充又是最小的。4.5关系的闭包关系的闭包运算是关系上的一元运算，他把给出的关系R扩充成一新155该定义表明，r（R）（s（R），t（R））是包含R的最小自反（对称，传递）关系。必要性：R=r（R），由定义1（1）知，r（R）是自反的，故R是自反的。4.5关系的闭包该定义表明，r（R）（s（R），t（R））是包含R的必要性：1564.5关系的闭包4.5关系的闭包1574.5关系的闭包4.5关系的闭包1584.5关系的闭包4.5关系的闭包1594.5关系的闭包4.5关系的闭包1604.5关系的闭包4.5关系的闭包1614.5关系的闭包3.IA的自反、对称和传递闭包是什么？4.空关系的自反、对称和传递闭包是什么？例：A={a，b，c，d}，R={<a，b>，<c，b>，<b，c>，<c，d>}4.5关系的闭包3.IA的自反、对称和传递闭包是什么？4162设R、r(R)、s(R)、t(R)的关系矩阵分别为M、Mr、Ms、Mt，则Mr=M+EMs=M+M’Mt=M+M2+M3+……设R、r(R)、s(R)、t(R)的关系矩阵分别为G、Gr、Gs、Gt，则①考察G中的每个顶点，若没有环就加上一个，得到Gr；②考察G中每条边，若有xi到xj的单向边（i≠j），则加xj到xi的反向边，得Gs；③考察G中每个顶点xi，找出从xi出发的所有2步、3步……n步长的路径（n为G中的顶点数）。设路径的终点为xj1、xj2、……、xjk，若没有从xi到xjl（l=1，2……，k)的边，就加上这条边。考察完所有的顶点后，得到Gt。4.5关系的闭包设R、r(R)、s(R)、t(R)的关系矩阵分别为M、Mr、1634.5关系的闭包4.5关系的闭包1644.5关系的闭包4.5关系的闭包1654.5关系的闭包4.5关系的闭包1664.6等价关系与划分例：A={1,2,3,4,5,6,7,8}，R={<x,y>|x,y∈A∧x≡y(mod3)}4.6等价关系与划分例：A={1,2,3,4,5,6,7,1674.6等价关系与划分4.6等价关系与划分1684.6等价关系与划分4.6等价关系与划分169一个集合的划分往往不是唯一的。4.6等价关系与划分一个集合的划分往往不是唯一的。4.6等价关系与划分1704.6等价关系与划分等价关系与划分一一对应。4.6等价关系与划分等价关系与划分一一对应。1714.7偏序关系4.7偏序关系1724.7偏序关系由以上定义可知，在具有偏序关系的集合中任取x、y，有x<y、x＝y、x与y不可比例：A={1,2,3}，≤是A上的整除关系。4.7偏序关系由以上定义可知，在具有偏序关系的集合中任取x173盖住关系的关系图称哈斯图.求法:1.省略关系图中每个结点处的自环.2.若x<y且y盖住x,将代表y的结点放在代表x的结点之上,并在x与y之间连线,省去有向边的箭头.4.7偏序关系若x<y但y不盖住x，则省去x与y之间的连线。盖住关系的关系图称哈斯图.求法:1.省略关系图中每个结点处的1744.7偏序关系4.7偏序关系1754.7偏序关系4.7偏序关系1764.7偏序关系B的最小元一定是B的下界，同时也是B的最大下界。B的最大元一定是B的上界，同时也是B的最小上界。4.7偏序关系B的最小元一定是B的下界，同时也是B的最大下177一般的调度问题可以描述为：给定有穷的任务集T和m台机器，T上存在偏序关系≤。如果t1<t2,那么t1完成以后t2才能开始工作。∀t∈T，l(t):表示完成任务t所需的时间d(t):表示任务t的截止时间。l(t),d(t)∈Z+设开始时间为0，σ：T→{0,1,2,……，D}表示对任务集T的一个调度方案。σ(t)：表示任务t的开始时间；D：表示完成所有任务的最终时间4.7偏序关系一般的调度问题可以描述为：∀t∈T，l(t):表示完成任务t178假设每项任务都可以在任何一台机器上进行加工，如果σ满足下述三个条件，则称其为可行调度①∀t∈T，σ（t）＋l(t)≤d(t)②∀i,0≤i≤D,|{t|t∈T∧σ（t）≤i≤σ（t）＋l(t)}|≤m③∀t,t’∈T,t<t’⇔σ（t）＋l(t)≤σ(t’)4.7偏序关系假设每项任务都可以在任何一台机器上进行加工，如果σ满足4.7179第五章函数5.1函数的定义与性质5.2函数的复合与反函数第五章函数5.1函数的定义与性质1805.1函数的定义与性质例1：F1={<a,x>,<b,y>,<c,z>}F2={<a,x>,<a,y>}定义2.设F、G为函数，则F=G⇔F⊆G∧G⊆F.即满足条件：①domF=domG②∀x∈domF，都F(x)=G(x).5.1函数的定义与性质例1：F1={<a,x>,<b,y>1815.1函数的定义与性质5.1函数的定义与性质1825.1函数的定义与性质5.1函数的定义与性质1835.1函数的定义与性质5.1函数的定义与性质1845.1函数的定义与性质5.1函数的定义与性质1855.1函数的定义与性质定义75.1函数的定义与性质定义7186单调函数可以定义于一般的偏序集上。每个子集对应一个特征函数，不同的子集则对应不同的特征函数。故而可用特征函数来标记不同的子集。给定集合A和A上的等价关系R，就可以确定一个自然映射，不同的等价关系将确定不同的自然映射。5.1函数的定义与性质单调函数可以定义于一般的偏序集上。5.1函数的定义与性质187算法的评价标准：时间复杂度、空间复杂度估计复杂度的方法是：选择一个基本运算，对于给定规模为n的输入，计算算法所做基本运算的次数，将这个次数表示为输入规模的函数。最坏情况下的复杂度w（n）平均情况下的复杂度A（n）算法分析的主要工作就是估计复杂度函数的阶。阶越高，增长越快，算法复杂度越高，效率越低。5.1函数的定义与性质算法的评价标准：时间复杂度、空间复杂度5.1函数的定义与性1885.1函数的定义与性质5.1函数的定义与性质1895.2函数的复合与反函数5.2函数的复合与反函数1905.2函数的复合与反函数5.2函数的复合与反函数1915.2函数的复合与反函数5.2函数的复合与反函数1925.2函数的复合与反函数5.2函数的复合与反函数193第四部分图论第六章图的基本概念第七章一些重要的图第四部分图论第六章图的基本概念194第六章图的基本概念6.1图6.2通路、回路6.3图的连通性6.4图的矩阵表示6.5图的运算第六章图的基本概念6.1图195用点表示事物，用点之间是否有连线表示事物之间是否有某种关系，这样构成的图，就是图论中的图。二元关系的关系图就是图，与几何学中的图形有本质区别。因此，先看无序积。定义1.设A，B为集合，称{{a，b}|a∈A∧b∈B}为A与B的无序积，记作A&B。为方便，将{a，b}记为（a，b）6.1图用点表示事物，用点之间是否有连线表示事物之间是否定义1.设A196定义2.图G=<V，E>是有序二元组，其中V(G)是有限非空集；V中元素称为G的顶点或结点，V称为G的顶点集。E(G)是V(G)中诸顶点之间边或弧的集合，E称为G的边集。图G的边可以是无方向的，用{vi，vj}表示，称为无向边，只由无向边构成的图G称为无向图。图G的边可以是有方向的，用<vi，vj>表示，称为有向边，只由有向边构成的图D称为有向图。6.1图定义2.图G=<V，E>是有序二元组，其中V(G)是有限非空197如果图G中既有有向边，又有无向边，则称图G为混合图。6.1图如果图G中既有有向边，又有无向边，则称图G为混合图。6.1198D=<V,E>,ek=<vi,vj>∈E,称vi为ek的起点，vj为ek的终点，并称vi邻接到vj或vj邻接于vi。若ek的终点是el的起点，则ek、el相邻。6.1图定义4.在无向图中，关联一对顶点的无向边若多于1条，则称这些边为平行边，平行边的条数为重数。在D中，关联一对顶点的有向边若多于1条，且始点、终点相同，则称这些边为平行边。含平行边的图为多重图，不含平行边、环的图为简单图。D=<V,E>,ek=<vi,vj>∈E,称vi为ek的起点1996.1图6.1图2006.1图6.1图2016.1图必要条件：①阶数相同②边数相同③度数相同的顶点数相同6.1图必要条件：①阶数相同2026.1图6.1图2036.1图6.1图2046.1图6.1图2056.2通路与回路6.2通路与回路206定理1.在n阶图G中，若从顶点vi到vj（vi≠vj）存在通路，则从vi到vj存在长度小于或等于（n-1）的通路。推论：在n阶图G中，若从顶点vi到vj（vi≠vj）存在通路，则从vi到vj一定存在长度小于或等于（n-1）的初级通路。定理2.在n阶图G中，若存在从顶点vi到自身的回路，则一定存在长度小于或等于n的回路。推论：在n阶图G中，若存在从顶点vi到自身的简单回路，则一定存在长度小于或等于n的初级回路。6.2通路与回路定理1.在n阶图G中，若从顶点vi到vj（vi≠vj）存在通207无向图顶点间的连通关系是V上的一个等价关系，他的所有等价类构成V的一个划分。任意两个顶点vi,vj属于同一个等价类当且仅当他们有路连接。6.3图的连通性无向图顶点间的连通关系是V上的一个等价关系，他的所6.3图2086.3图的连通性6.3图的连通性2096.3图的连通性6.3图的连通性210当{v}是G的点割集，则称v是G的割点。若v是连通图G的一个割点，那么G-v就是不连通或平凡图。6.3图的连通性当{v}是G的点割集，则称v是G的割点。若v是连通图G的一个2116.3图的连通性6.3图的连通性2126.3图的连通性6.3图的连通性2136.3图的连通性6.3图的连通性214定理3.一个有向图D是强连通图的充要条件是D中存在至少经过每个顶点一次的回路。6.3图的连通性定理4.设D是n阶有向图，D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路。定理3.一个有向图D是强连通图的充要条件是D中存在至少6.32156.3图的连通性极大路径法：设G=<V,E>为n阶无向图，E≠Φ。设Γl为G中一条路径。若此路径的始点或终点与通路外的顶点相邻，就将它们扩充到通路中来，继续这一过程，直到最后得到的通路的两个端点不与通路外的顶点相邻为止。设最后得到的路径为Γl+k，称其为极大路径。称使用此种方法证明问题的方法为极大路径法。6.3图的连通性极大路径法：设G=<V,E>为n216邻接矩阵A的阶就是G的顶点数n。6.4图的矩阵表示图的表示方法：（1）用边的集合和边的集合表示，如G=<V，E>（2）用图形表示，顶点用小圆圈表示，边用线段或弧表示（3）用矩阵表示邻接矩阵A的阶就是G的顶点数n。6.4图的矩阵表示图的表示217邻接矩阵依赖于V中个元素的给定次序，对于V中各元素的不同给定次序，可以得到同一个图G的不同邻接矩阵。这些矩阵可以通过交换另一个矩阵的某些行或对应的列而得到。如果两个图有这样的邻接矩阵，则这两个图是同构的。6.4图的矩阵表示若主对角线某元素不为0，则表示该对应顶点上有自环。零矩阵对应的图为零图。邻接矩阵依赖于V中个元素的给定次序，对于V中各元素6.4图2186.4图的矩阵表示6.4图的矩阵表示2196.4图的矩阵表示6.4图的矩阵表示2206.4图的矩阵表示6.4图的矩阵表示2216.4图的矩阵表示6.4图的矩阵表示2226.4图的矩阵表示6.4图的矩阵表示2236.4图的矩阵表示6.4图的矩阵表示2246.5图的运算6.5图的运算2256.5图的运算6.5图的运算226第七章欧拉图与哈密顿图7.1欧拉图7.2哈密顿图7.3二部图7.4平面图7.5树第七章欧拉图与哈密顿图7.1欧拉图227定义1.通过图G的每条边一次且仅一次行遍图中所有顶点的通路称为欧拉通路。通过图G的每条边一次且仅一次行遍图中所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图。具有欧拉通路而无欧拉回路的图为半欧拉图。定理1.无向图G为欧拉图当且仅当G是连通图，且G中所有顶点的度数都是偶数。

定理2.如果G是欧拉图，那么G可分成若干个边不重的回路。7.1欧拉图定义1.通过图G的每条边一次且仅一次行遍图中所有顶点的定理1228定理3.具有一条连接顶点vi和vj的欧拉通路的充要条件是Vi和vj是G中仅有的具有奇数度的顶点。定理4.设连通图G=<V,E>有k个度为奇数的顶点，则E(G)可划分为k/2条简单通路。定理5.有向连通图D为欧拉图的充要条件是每个顶点的入度等于出度。7.1欧拉图定理3.具有一条连接顶点vi和vj的欧拉通路的充要条件是定理229定理6.有向连通图D存在一条欧拉通路的充要条件是恰有两个奇度数顶点，其中的一个入度比出度大1，另一个的出度比入度大1，而其余顶点的入度等于出度。7.1欧拉图定理6.有向连通图D存在一条欧拉通路的充要条件是恰有7.12307.1欧拉图7.1欧拉图231定义1.通过图G的每个顶点一次且仅一次的回路称为哈密顿回路.哈密顿通路是通过图G的每个顶点一次且仅一次的通路.具有哈密顿回路的图称为哈密顿图.具有哈密顿通路而不具有哈密顿回路的图称为哈密顿图.平凡图是哈密顿图。性质:1.连通,度大于等于22.哈密顿通路是度为n-1的基本通路,其回路长为n7.2哈密顿图定义1.通过图G的每个顶点一次且仅一次的回路称为性质:1.连2327.2哈密顿图7.2哈密顿图2337.2哈密顿图例：在某次国际会议的预备会中，共有8人参加，他们来自不同的国家。已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于8。问能否将这8人排在圆桌旁，使任何人都能与两边的人交谈。定理4.若D为n（n≥2）阶竞赛图，则D中具有哈密顿通路。7.2哈密顿图例：在某次国际会议的预备会中，共有8人参加，234带权图与货郎担问题货郎担问题：设有n个城市，城市之间均有道路，道路的长度均大于或等于0。一个旅行商从某个城市出发，要经过每个城市一次且仅一次，最后回到出发的城市。问他如何走，才能使路线最短？带权图与货郎担问题货郎担问题：设有n个城市，城市之间均有道2357.5树7.5.1无向树及其性质7.5.2生成树7.5.3根树及其应用7.5树7.5.1无向树及其性质236定义1.连通无回路的无向图称为无向树，简称树，用T表示。若无向图F至少有两个连通分图都是树，称F为森林。仅有一个顶点的树称为平凡树。悬挂点称为树叶。定理1.设G=<V,E>是n阶m条边的无向图，下列各命题等价；（1）G是树；（2）G的任意两个顶点之间有唯一路径；7.5.1无向树及其性质定义1.连通无回路的无向图称为无向树，简称树，用T定理1.设237（3）G中无回路且m=n-1；（4）G是连通且m=n-1；（5）G是连通的，且G中任何边均是割边；