離散數(shù)學(xué)教程ppt.ppt

1、離散數(shù)學(xué),數(shù)學(xué)與信息科學(xué)學(xué)院,第一部分 數(shù)理邏輯 第二部分 集合論 第三部分 圖論 第四部分 抽象代數(shù),離散數(shù)學(xué),第一部分 數(shù)理邏輯,數(shù)理邏輯是用數(shù)學(xué)方法研究推理中前提和 結(jié)論之間的形式關(guān)系的學(xué)科。,推理是由一個(gè)或幾個(gè)判斷推出一個(gè)新判斷的思維形式。,數(shù)學(xué)方法是指建立一套表意符號(hào)體系，對(duì)具體 事物進(jìn)行抽象的形式研究的方法。,第一章 命題邏輯 第二章 一階謂詞邏輯,第一部分 數(shù)理邏輯,1.1 命題和命題聯(lián)結(jié)詞 1.2 命題公式及其賦值 1.3 等值演算與聯(lián)結(jié)詞完備集 1.4 析取范式與合取范式 1.5 推理的形式結(jié)構(gòu) 1.6 自然推理系統(tǒng)P,第一章 命題邏輯,1. 命題：能判斷真假的陳述句。,包含

2、兩層意思：,（1）必須是陳述句。,（2）能夠確定（分辨）其真值。,1.1 命題和命題聯(lián)結(jié)詞,1.1 命題和命題聯(lián)結(jié)詞,2. 命題的真值：判斷結(jié)果,注意：此處不糾纏具體命題的真假問(wèn)題，只是將其作為數(shù)學(xué)概念來(lái)處理。,真值：真用T或1表示，假用F或0表示。,3.命題和真值的符號(hào)化,1.1 命題和命題聯(lián)結(jié)詞,1.1 命題和命題聯(lián)結(jié)詞,原子命題：不能被分解為更簡(jiǎn)單的陳述句 復(fù)合命題：原子命題通過(guò)聯(lián)結(jié)詞聯(lián)結(jié)而成,例：2是有理數(shù)是不對(duì)的；2是偶素?cái)?shù)；2或4是素?cái)?shù)；如果2是素?cái)?shù)，則3也 是素?cái)?shù)；2是素?cái)?shù)當(dāng)且僅當(dāng)3也是素?cái)?shù)。,p：2是有理數(shù)，q：2是偶數(shù)，r：2是素?cái)?shù)，s：3是素?cái)?shù)，t：4是素?cái)?shù)。,1.1 命題

3、和命題聯(lián)結(jié)詞,4、命題聯(lián)結(jié)詞,1.1 命題和命題聯(lián)結(jié)詞,王化不但成績(jī)好而且品德好。,pq：,1.1 命題和命題聯(lián)結(jié)詞,1.1 命題和命題聯(lián)結(jié)詞,開(kāi)關(guān)壞了或燈泡壞了。,pq：,例：1.張曉婧愛(ài)唱歌或愛(ài)聽(tīng)音樂(lè)。 2.張曉婧是內(nèi)蒙人或是陜西人。 3.張曉婧只能挑選202或203房間。,1.1 命題和命題聯(lián)結(jié)詞,注意：當(dāng)排斥或兩邊的情況實(shí)際根本不可能同時(shí)發(fā)生的時(shí)候，排斥或也 可抽象為。但為了方便起見(jiàn)一般不這樣抽象。,有位父親對(duì)兒子說(shuō)：“如果我 去書(shū)店，就一定給你買電腦 報(bào)“。問(wèn)：在什么情況下， 父親算失信呢？,1.1 命題和命題聯(lián)結(jié)詞,注意：“只要p，就q，因?yàn)閜，所以q”，“p僅當(dāng)q”， 只有q，才

4、p“，”除非q才p“，”除非q，否則非p“都可 抽象為pq。 p，q可以沒(méi)有任何內(nèi)在聯(lián)系。,例：1.如果336，那么雪是白的。 2.除非我能工作完成了，我才去看電影。 3.只要天下雨，我就回家。 4.我回家僅當(dāng)天下雨。,pq的邏輯關(guān)系為q是p的必要條件或p是q的充分條件。,1.1 命題和命題聯(lián)結(jié)詞,1.1 命題和命題聯(lián)結(jié)詞,p q的邏輯關(guān)系為p與q互為充要條件,例：1.3是有理數(shù)當(dāng)且僅當(dāng)加拿大位于亞洲。 2.兩圓的面積相等，則他們的半徑相等， 反之亦然。,1.1 命題和命題聯(lián)結(jié)詞,例：今天第一節(jié)課上離散數(shù)學(xué)或數(shù)據(jù)結(jié)構(gòu)。,例：p：北京比天津人口多 q：224 r：烏鴉是黑色的,1.1 命題和命題

5、聯(lián)結(jié)詞,5、語(yǔ)句形式化,1.1 命題和命題聯(lián)結(jié)詞,例：2是有理數(shù)是不對(duì)的；2是偶素?cái)?shù)；2或4是素?cái)?shù)；如果2是素?cái)?shù)，則3也 是素?cái)?shù)；2是素?cái)?shù)當(dāng)且僅當(dāng)3也是素?cái)?shù)。,p：2是有理數(shù)，q：2是偶數(shù)，r：2是素?cái)?shù)，s：3是素?cái)?shù)，t：4是素?cái)?shù)。,p不對(duì)；q且r；r或t；如果r，則s；r當(dāng)且僅當(dāng)s。,1.1 命題和命題聯(lián)結(jié)詞,命題常元：表示具體確定內(nèi)容的命題。 命題變?cè)罕硎静淮_定具體內(nèi)容的命題。,1.2 命題公式及其賦值,1.2 命題公式及其賦值,同時(shí)約定：（1）最外層的括號(hào)可以省去。 （2）不影響運(yùn)算次序的括號(hào)也可以省去。,1.2 命題公式及其賦值,1.2 命題公式及其賦值,1.2 命題公式及其賦值,1

6、.2 命題公式及其賦值,1.2 命題公式及其賦值,1.3 命題公式的等值式,基本等值式（A，B，C為任意命題公式）,1.3 命題公式的等值式,1.3 命題公式的等值式,因A，B，C可以代入任意的命題公式，故以上等值式稱為等值式模式。,由已知的等值式推演出另外一些等值式的過(guò)程為等值演算。,1.3 命題公式的等值式,等值演算的應(yīng)用： 1.驗(yàn)證等值式 2.判定公式的類型 3.解決工作生活中的判斷問(wèn)題,1.3 命題公式的等值式,甲、已、丙3人根據(jù)口音對(duì)王教授是哪人進(jìn)行了判斷： 甲說(shuō)：王教授不是蘇州人，是上海人 已說(shuō)：王教授不是上海人，是蘇州人 丙說(shuō)：王教授既不是上海人，也不是杭州人 結(jié)果3人中有一人全

7、對(duì)，一人對(duì)一半，一人全錯(cuò)。問(wèn)王教授是哪人？,聯(lián)結(jié)詞的完備集,n個(gè)命題變?cè)梢孕纬?2n個(gè)不同的真值函數(shù),對(duì)于每個(gè)真值函數(shù)，都可以找到許多與之等值的命題公式， 而每個(gè)命題公式對(duì)應(yīng)唯一的與之等值的真值函數(shù)。,定義.設(shè)S是一個(gè)聯(lián)結(jié)詞集合，如果任何n（n1）元真值 函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則 稱S是聯(lián)結(jié)詞完備集。,聯(lián)結(jié)詞的完備集,1.4 析取范式與合取范式,定義：命題變?cè)捌浞穸ńy(tǒng)稱為文字。 僅由有限個(gè)文字構(gòu)成的析取式稱為簡(jiǎn)單（質(zhì)）析取式。 僅由有限個(gè)文字構(gòu)成的合取式稱為簡(jiǎn)單（質(zhì)）合取式。,注意：?jiǎn)蝹€(gè)文字既是簡(jiǎn)單析取式又是簡(jiǎn)單合取式。,討論：設(shè)A為含n個(gè)文字的簡(jiǎn)單析取式 若A中同時(shí)

8、含pi和pi，則？,若A為永真式，則？,若A為永真式，則A中必同時(shí)含有pi和pi，反之亦然。,同理有，若A為簡(jiǎn)單合取式， A為永假式的充要條件是A中同時(shí)含有pi和pi。,定理1. 一個(gè)簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含有某 個(gè)命題變?cè)捌渌姆穸ā?一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含有某 個(gè)命題變?cè)捌渌姆穸ā?1.4 析取范式與合取范式,定義：由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式稱為析取范式。 由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式稱為合取范式。 析取范式與合取范式稱為范式。,注意：?jiǎn)蝹€(gè)文字、簡(jiǎn)單析取式、簡(jiǎn)單合取式都既是析取范 式又是合取范式。,1.4 析取范式與合取范式,定理2. 一個(gè)析取范式是矛

9、盾式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合 取式為矛盾式。 一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析 取式為重言式。,定理3.任一命題公式都存在與之等值的析取范式和合取范式。,范式的求法：消去公式中的蘊(yùn)涵、等價(jià)和異或聯(lián)結(jié)詞 使用雙重否定律和德摩根律，將公式中出現(xiàn) 的否定 詞移到命題變?cè)啊?利用分配律、結(jié)合律將公式化為合（析）取 范式。,范式形式不唯一。,1.4 析取范式與合取范式,定義：在含有n個(gè)命題變?cè)暮?jiǎn)單合（析）取式中，若每個(gè) 命題變?cè)?它的否定式不同時(shí)出現(xiàn)，而二者之一必 出現(xiàn)且僅出現(xiàn)一次，且第 i個(gè)命題變?cè)蛩姆穸ㄊ?出現(xiàn)在從左算起的第i位上（字典序），稱這樣的簡(jiǎn) 單合（析）取式為極?。ù螅?/p>

10、項(xiàng)。,性質(zhì)：n個(gè)變?cè)梢孕纬?n個(gè)極?。ù螅╉?xiàng)； 每個(gè)極小（大）項(xiàng)有且僅有一個(gè)成真（假）賦值； 每組賦值下僅有一個(gè)極小（大）項(xiàng)為真（假）； 所有極小（大）項(xiàng)的析（合）取為真（假）；,1.4 析取范式與合取范式,將極小項(xiàng)的成真賦值對(duì)應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為i， 將對(duì)應(yīng)的極小項(xiàng)記為mi。 將極大項(xiàng)的成假賦值對(duì)應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為i， 將對(duì)應(yīng)的極大項(xiàng)記為Mi。,定義：設(shè)由n個(gè)命題變?cè)獦?gòu)成的析（合）取范式中所有的簡(jiǎn) 單合（析）取式都是極小（大）項(xiàng)，則稱該析取范 式為主析（合）取范式。,1.4 析取范式與合取范式,定理.任何命題公式都存在與之等值的主析取范式和主合取范 式，并且是唯一的。,1

11、.4 析取范式與合取范式,公式法：求析取范式 用同一律補(bǔ)進(jìn)未出現(xiàn)的命題變?cè)?消去永假或重復(fù)出現(xiàn)的變?cè)蜆O小項(xiàng) 將極小項(xiàng)按下標(biāo)從小到大排列,真值表法：列出公式及各極小項(xiàng)的真值表，將每組賦值下 公式及極小項(xiàng)真值都為真的極小項(xiàng)進(jìn)行析取。,主析取范式的求法：,1.公式法 2.真值表法,1.4 析取范式與合取范式,應(yīng)用：1.求公式的成真、成假賦值 成真賦值為析取范式中所含極小項(xiàng)的編碼的二進(jìn)制數(shù) 成假賦值為合取范式中所含極大項(xiàng)的編碼的二進(jìn)制數(shù),由主析取范式可以直接求主合取范式： 1求出主析取范式中未包含的極小項(xiàng) 2求出與1中求出的極小項(xiàng)下標(biāo)相同的極大項(xiàng) 3做2中極大項(xiàng)之合取,1.4 析取范式與合取范式,3

12、.判斷兩公式是否等值 若A，B共含有n個(gè)命題變?cè)?，按n個(gè)命題變?cè)蟪鯝與B的 主析取范式A、B，若AB，則AB.,2.判斷公式的類型 設(shè)A含有n個(gè)命題變?cè)?A為重言式當(dāng)且僅當(dāng)A的主析取范式含全部2n個(gè)極小項(xiàng)； A為矛盾式當(dāng)且僅當(dāng)A的主析取范式不含任何極小項(xiàng)，此 時(shí)記為0； A為可滿足式當(dāng)且僅當(dāng)A的主析取范式中至少含一個(gè)極小項(xiàng)。,例：要在A，B，C中挑選2名出國(guó)進(jìn)修，選派時(shí)滿足下列條件： 若A去，則C同去 若B去，則C不能去 若C不去，則A或B可以去 問(wèn)有幾種選派方案，分別是什么？,4.解決實(shí)際問(wèn)題,1.4 析取范式與合取范式,1.5推理的形式結(jié)構(gòu),注意： 推理正確實(shí)際是排除前提真結(jié)論假的情況

13、推理是否正確與前提的排列順序無(wú)關(guān) 推理正確并不能保證B一定為真,1.5推理的形式結(jié)構(gòu),推理的形式結(jié)構(gòu),1.5推理的形式結(jié)構(gòu),例：若下午溫度超過(guò)30度，則王曉燕必去游泳。若她去游 泳，她就不會(huì)去看電影。所以若王曉燕沒(méi)去看電影， 下午溫度必超過(guò)了30度。,p：溫度超過(guò)30度 q：王曉燕去游泳 r：王曉燕去看電影,1.5推理的形式結(jié)構(gòu),1.5推理的形式結(jié)構(gòu),注意： 以上都是蘊(yùn)含式模式 若某推理的形式結(jié)構(gòu)與某定律一致，則推理正確 成立的等值式可產(chǎn)生兩條定律 推理定律可產(chǎn)生相應(yīng)的推理規(guī)則,1.5推理的形式結(jié)構(gòu),1.6自然推理系統(tǒng)P,定義.一個(gè)形式系統(tǒng)I由以下4部分組成： 非空的字母表，記作A(I) A(

14、I)中符號(hào)構(gòu)成的合式公式集，記作E(I) E(I)中特殊的公式組成的公理集，記作Ax(I) 推理規(guī)則集，記作R(I),任給的前提，應(yīng)用規(guī)則得到結(jié)論（可能真）,任給的公理，應(yīng)用規(guī)則得到結(jié)論（永真）,1.6自然推理系統(tǒng)P,1.6自然推理系統(tǒng)P,例：若小王是理科生，則他的數(shù)學(xué)成績(jī)一定很好。如果 小王不是理科生，他一定是文科生。小王的數(shù)學(xué)成績(jī) 不好。所以小王是文科生。,p：小王是理科生 q：小王是文科生 r：小王的數(shù)學(xué)成績(jī)很好,1.6自然推理系統(tǒng)P,例：如果小張和小王去看電影，則小李也去看電影。小趙 不去看電影或小張去看電影。小王去看電影。所以， 當(dāng)小趙去看電影時(shí)，小李也去。,p：小張去看電影 q：小

15、王去看電影 r：小李去看電影 s：小趙去看電影,1.6自然推理系統(tǒng)P,2.歸謬法 將結(jié)論的否定作為前提引入，能推出矛盾來(lái)，則推理正確,例：如果馬會(huì)飛或羊不吃草，則母雞就會(huì)是飛鳥(niǎo)。如果母 雞是飛鳥(niǎo)，那么烤熟的鴨子還會(huì)跑。烤熟的鴨子不會(huì) 跑。所以羊吃草。,p：馬會(huì)飛 q：羊吃草 r：母雞是飛鳥(niǎo) s：烤熟的鴨子會(huì)跑,1.6自然推理系統(tǒng)P,所有的人總是要死的。 蘇格拉底是人。 所以蘇格拉底是要死的。,p: q: r:,第二章 謂詞邏輯,第二章 謂詞邏輯,2.1一階邏輯命題符號(hào)化 2.2一階邏輯公式及解釋 2.3一階邏輯等值式與置換規(guī)則 2.4一階邏輯前束范式 2.5一階邏輯的推理理論,2.1一階邏輯命

16、題符號(hào)化,1.個(gè)體詞,所研究對(duì)象中可以獨(dú)立存在的具體的或抽象的客體（事物）,表示具體的或特定的客體,表示抽象或泛指的客體,個(gè)體變項(xiàng)的取值范圍稱為個(gè)體域，用D表示,宇宙間一切事物組成的稱為全總個(gè)體域,2.謂詞,用來(lái)刻劃個(gè)體詞性質(zhì)及個(gè)體詞之間相互關(guān)系的詞,2是有理數(shù) x是無(wú)理數(shù) 小王與小李同歲 x與y具有關(guān)系L,是有理數(shù) 是無(wú)理數(shù) 與同歲 與具有關(guān)系L,F： G： H： L：,2.1一階邏輯命題符號(hào)化,3.量詞：個(gè)體詞之間的數(shù)量關(guān)系,（1）全稱量詞 “一切的”，“所有的”，“每一個(gè)”，“任意的”，“凡”，“都” 記作,4.符號(hào)化,確定個(gè)體域 確定個(gè)體詞、量詞和謂詞 確定聯(lián)結(jié)詞,2.1一階邏輯命題符

17、號(hào)化,例：所有的人都是要死的。 有的人用左手寫(xiě)字。,注意： 全稱量詞的特性謂詞必須作為蘊(yùn)涵式的前件引入 存在量詞的特性謂詞必須作為合取式的合取項(xiàng)引入 同一命題，不同的個(gè)體域符號(hào)化的形式可能不同 未指明個(gè)體域即為全總個(gè)體域,2.1一階邏輯命題符號(hào)化,例：在美國(guó)留學(xué)的學(xué)生未必都是亞洲人。 有的兔子比所有的烏龜跑的快。 對(duì)任意的整數(shù)x，都存在整數(shù)y使得xy10。,注意： 多個(gè)量詞出現(xiàn)時(shí)，順序一般不能隨便換 有些命題符號(hào)化形式不唯一,2.1一階邏輯命題符號(hào)化,2.2一階邏輯公式及解釋,2.2一階邏輯公式及解釋,合式公式也稱謂詞公式，簡(jiǎn)稱公式,2.2一階邏輯公式及解釋,2.2一階邏輯公式及解釋,2.2一

18、階邏輯公式及解釋,2.2一階邏輯公式及解釋,定理.閉式在任何解釋下都變成命題。,2.2一階邏輯公式及解釋,2.2一階邏輯公式及解釋,定理.重言式的代換實(shí)例都是永真式，矛盾式的代換 實(shí)例都是矛盾式。,2.2一階邏輯公式及解釋,2.3一階邏輯等值式與置換規(guī)則,第一組 命題邏輯中等值式模式的代換實(shí)例都是一階邏 輯的等值式模式,第二組 一階邏輯中特殊的等值式,2.3一階邏輯等值式與置換規(guī)則,D=N，F(xiàn)(x)：x是奇數(shù) G(x)：x是偶數(shù),2.3一階邏輯等值式與置換規(guī)則,2.3一階邏輯等值式與置換規(guī)則,2.3一階邏輯等值式與置換規(guī)則,2.4一階邏輯前束范式,為了方便使用謂詞公式進(jìn)行定理證明和邏輯推理，需

19、要 把謂詞公式變換為便于使用的規(guī)范形式，就是范式。,定理1：任一謂詞公式都可以化成為與之等值的前束范式。,2.4一階邏輯前束范式,2.4一階邏輯前束范式,2.5一階邏輯的推理理論,在一階邏輯中，稱永真的蘊(yùn)涵式為推理定律。若一個(gè)推理 的形式結(jié)構(gòu)正是某條推理定律，則該推理顯然是正確的。,第一組 命題邏輯推理定律的代換實(shí)例,第二組 由基本等值式生成的推理定律,第三組 以下重要定律,第四組 消去量詞和引入量詞的推理規(guī)則,1、全稱量詞消去規(guī)則（UI）,2.5一階邏輯的推理理論,UI規(guī)則成立的條件： （1）取代x的y應(yīng)為任意不在A(x)中約束出現(xiàn)的個(gè)體變項(xiàng)； （2）用y取代A(x)中自由出現(xiàn)的x時(shí)，必須將

20、所有的自由出現(xiàn)x都取代； （3）自由變?cè)獃也可替換為個(gè)體域中任意的個(gè)體常元c，c為任意不在A(x)中出現(xiàn)過(guò)的個(gè)體常項(xiàng)。,2.5一階邏輯的推理理論,含義：如果個(gè)體域的所有個(gè)體都具有性質(zhì)A，則個(gè)體域中 的任一個(gè)個(gè)體都具有性質(zhì)A。,2、存在量詞消去規(guī)則（EI）,含義：如果個(gè)體域存在有性質(zhì)A的個(gè)體，則個(gè)體域中必有 某一個(gè)個(gè)體具有性質(zhì)A。,2.5一階邏輯的推理理論,ES規(guī)則成立的條件： （1）c是個(gè)體域中使A為真的特定的個(gè)體常項(xiàng)； （2）c不曾在A(x)或前面的推導(dǎo)公式中出現(xiàn)過(guò)； （3）A（x）中除x外還有其他自由變?cè)獣r(shí)，不能用此規(guī)則,2.5一階邏輯的推理理論,3、全稱量詞引入規(guī)則（UG）,UG規(guī)則成立

21、的條件： （1）y在A（y）中自由出現(xiàn)，且y取任何值時(shí)A均為真； （2）x不在A（y）中約束出現(xiàn)。,含義：如果個(gè)體域的任意個(gè)體都具有性質(zhì)A，則個(gè)體域中 的所有個(gè)體都具有性質(zhì)A。,2.5一階邏輯的推理理論,4、存在量詞引入規(guī)則（EG）,EG規(guī)則成立的條件： （1）c是個(gè)體域中某個(gè)確定的個(gè)體； （2）代替c的x不在A（c）中出現(xiàn)過(guò)。,含義：如果個(gè)體域有某一個(gè)個(gè)體c具有性質(zhì)A，則個(gè)體域中 必存在具有性質(zhì)A的個(gè)體。,2.5一階邏輯的推理理論,定義.一階邏輯自然推理系統(tǒng)F的定義 1.字母表：同一階語(yǔ)言的字母表 2.合式公式：同一階語(yǔ)言合式公式的定義 3.推理規(guī)則 a.前提引入規(guī)則 b.結(jié)論引入規(guī)則 c.

22、置換規(guī)則 d.假言推理規(guī)則 e.附加規(guī)則 f.化簡(jiǎn)規(guī)則 g.拒取式規(guī)則 h.假言三段論規(guī)則 i.析取三段論規(guī)則 j.構(gòu)造性二難規(guī)則 k.合取引入規(guī)則 l. UI，EI，UG，EG,2.5一階邏輯的推理理論,例7：證明邏輯三段論 所有的人總是要死的。 蘇格拉底是人。 所以蘇格拉底是要死的。,2.5一階邏輯的推理理論,2.5一階邏輯的推理理論,例10：如果一個(gè)人怕困難就不會(huì)獲得成功。每一個(gè)人或 者獲得成功或者是失敗的。有些人未曾失敗過(guò)，所以有 些人不怕困難。（個(gè)體域是人的集合）判斷這個(gè)推理是 否正確。,例9：根據(jù)前提集合：同事之間總是有工作矛盾的， 張平和李明沒(méi)有工作矛盾，能得出什么結(jié)論？,第二部

23、分 集合論,第三章 集合代數(shù) 第四章 二元關(guān)系 第五章 函數(shù),第三章 集合代數(shù),3.1 集合的基本概念 3.2 集合的運(yùn)算 3.3 集合恒等式,一、集合的概念 集合（set)的含義：一個(gè)集合是作為整體識(shí)別的、確定的、互相區(qū)別的一些事物的聚集（全體或總體等)。 構(gòu)成一個(gè)集合的每個(gè)事物，成為這個(gè)集合中的元素或成員。集合一般用A、B、C表示，集合中的元素用a、b、c表示。但這不是絕對(duì)的，因?yàn)橐粋€(gè)集合可以作為另一個(gè)集合的元素。 如果x是集合s的一個(gè)元素,記作 ; y不是集合s的元素，記作,3.1集合的基本概念,例1： 1.偶素?cái)?shù)集合。 2.二進(jìn)制的基數(shù)集合。 3.英文字母的集合。 4.全體實(shí)數(shù)的集合。

24、 5.自然數(shù)集合。 6.整數(shù)集合。 7.有理數(shù)集合。 8.素?cái)?shù)集合。,3.1集合的基本概念,3.1集合的基本概念,集合的表示方法: 1.列舉法（枚舉法、外延法） 把集合的所有元素（元素較少時(shí)）寫(xiě)在一個(gè)花括號(hào)內(nèi);列出足夠多的元素（元素很多或無(wú)窮時(shí)）以反映集合中元素的特征。 如例1中的1、2、3、5可分別表示為： 2 0，1 a，b，cz，A，B，CZ 1，2，3,3.1集合的基本概念,2.描述法（概括法） 將集合中的元素的性質(zhì)用一個(gè)謂詞公式來(lái)描述，S=X|P(X),意義為:集合S由且僅由滿足為此公式P(X)的對(duì)象組成，即 ，當(dāng)且僅當(dāng)p(a)為真。 如例1中的4、6、7可表示為：,3.文氏圖 用圖

25、形圖像直觀的描述集合之間的相互關(guān)系和有關(guān)運(yùn)算。,3.1集合的基本概念,幾個(gè)常見(jiàn)集合的表示符號(hào)： N：自然數(shù)集合，N=0，1，2，3； I：整數(shù)集合； P：素?cái)?shù)或質(zhì)數(shù)集合； Q：有理數(shù)集合； R：實(shí)數(shù)集合； C：復(fù)數(shù)集合；,3.1集合的基本概念,集合的特性: A.互異性：一個(gè)集合的個(gè)元素是可以區(qū)分開(kāi)的，即每一 元素只出現(xiàn)一次。 B.無(wú)序性：集合中元素排列順序無(wú)關(guān)緊要，即集合表示 形式的不唯一性。 例2：a，b，c=b，c，a=c，a，b=a，c，b= b，a，c=c，b，a,3.1集合的基本概念,C.確定性：任一事物是否屬于某一集合，回答是確定的。,例3：“好書(shū)”的全體，這不構(gòu)成集合。,注意：一

26、個(gè)集合是已知的，指的是對(duì)任一元素，利用某種方法可以判斷它是否是這個(gè)集合的元素，而不是把集合的每一個(gè)元素都給出來(lái)。,3.1集合的基本概念,集合的元素可以是任何具體或抽象的事物，包括別的集合，但不能是本集合自身。,例4：在一個(gè)住著一些人家的偏僻孤島上，島上只有一個(gè)理發(fā)師a，a給且只給島上所有不能自己理發(fā)的人理發(fā)。問(wèn)誰(shuí)給a理發(fā)？,定義1.設(shè)A和B是兩個(gè)集合，若A中的每一個(gè)元素都是B的元素，則稱A是B的子集，也稱B包含A,記作,3.1集合的基本概念,定義2.設(shè)A和B是任意兩個(gè)集合，若A包含B且B包含A，則稱A與B相等，記作A=B. 即，,二、集合的關(guān)系,3.1集合的基本概念,定義3.若A是B的子集且

27、，則稱A為B的真子集，或稱B真包含A，記作，B稱為A的超集。,集合的相等關(guān)系的性質(zhì)：,設(shè)A,B,C為3個(gè)集合， 集合的包含關(guān)系的性質(zhì):,3.1集合的基本概念,定義4.不包含任何元素的集合稱為空集，記作或,3.1集合的基本概念,三、特殊集合,定義4：在一定范圍內(nèi)，如果所有集合均為某一集合的子集，則稱該集合為全集，記作E。,定義5.集合中元素的個(gè)數(shù)稱為基數(shù)或勢(shì)，用|A|表示。 基數(shù)是有限數(shù)的集合稱為有限集，否則稱為無(wú)限集。,全集是相對(duì)的，不同的問(wèn)題有不同的全集，即使是同一個(gè)問(wèn)題也可以取不同的全集 。,3.1集合的基本概念,3.1集合的基本概念,含n個(gè)元素的集合簡(jiǎn)稱n元集，其含有k(kn)個(gè)元素的子

28、集稱為它的k元子集。,定義6.由集合S的所有子集組成的集合，稱為集合S的冪 集，記作P（S）。表示為：,有限集S ，|P（S）|=2|S|,例：Aa，b，c，d，c,3.2集合的運(yùn)算,一、集合的基本運(yùn)算,3.2集合的運(yùn)算,定義5.設(shè)A 為集合， A 的元素的元素構(gòu)成的集合稱為A的廣義并，記作A 。,3.2集合的運(yùn)算,A x|z (zA xz),若A A1,A2,，An，則A A1A2 An,定義6.設(shè)A 為非空集合， A 的所有元素的公共元素構(gòu)成的集合稱為A的廣義交，記作A 。,A x|z (zA xz),若A A1,A2,，An，則A A1 A2 An,例：Aa，b，c，a，b，e B=a

29、C=a，c，d,集合運(yùn)算的優(yōu)先級(jí)： 高級(jí)：廣義并、廣義交、絕對(duì)補(bǔ)、求冪集；同級(jí)按從右向左的順 序進(jìn)行 低級(jí)：并、交、相對(duì)補(bǔ)和對(duì)稱差；同級(jí)按從左向右的順序進(jìn)行,3.2集合的運(yùn)算,3.2集合的運(yùn)算,文氏圖可以用來(lái)描述集合間的關(guān)系及其運(yùn)算.在文氏圖中,全集用矩形表示,子集用圓形表示,陰影部分表示運(yùn)算結(jié)果的集合.,二、文氏圖,3.2集合的運(yùn)算,3.3集合恒等式,一、集合運(yùn)算定律,以下列出集合性質(zhì)中最主要的幾條基本定律，對(duì)于全集E的任意子集A，B，C，有：,3.3集合恒等式,1、基本定義法,根據(jù)集合相等的充要條件等式兩邊互為子集或由定義進(jìn)行等價(jià)推理。,2、公式法,利用已證明過(guò)的恒等式去證明另外的恒等式。

30、若表達(dá)式中出現(xiàn)形為 A-B的差集時(shí)，用功能完備律先將運(yùn)算“-”轉(zhuǎn)化為運(yùn)算“ ”和“”。,二、集合恒等式證明,3.3集合恒等式,3.3集合恒等式,3.3集合恒等式,3.3集合恒等式,小 結(jié),集合的概念 集合的特性 集合的表示方法:列舉法、描述法、文氏圖 集合的運(yùn)算：并、交、補(bǔ)、差、求冪 集合間的關(guān)系：包含、相等 集合恒等式的證明：定義法、公式法、成員表法,第四章二元關(guān)系,4.1 有序?qū)εc笛卡兒積 4.2 二元關(guān)系 4.3 關(guān)系的運(yùn)算 4.4 關(guān)系的性質(zhì) 4.5 關(guān)系的閉包 4.6 劃分和等價(jià)關(guān)系 4.7 偏序關(guān)系,定義1.由兩個(gè)具有固定次序的個(gè)體a，b組成的序列,稱為序偶,記作.其中a,b稱為序

31、偶的分量.,定義2.設(shè)和是兩個(gè)序偶,若a=c且b=d,則稱這兩個(gè)序偶相等,記作=.,區(qū)別:集合a,b=b,a = (a=b),4.1 有序?qū)εc笛卡兒積,例3:設(shè)A=a,b,c,B=1,0,則,4.1 有序?qū)εc笛卡兒積,定義3.設(shè)集合A，B，以A的元素作為第一元素，B的元算作為第二元素 的有序?qū)?gòu)成的集合稱為A與B的笛卡兒積，記作AB，符號(hào)化為 AB =|xAyB,性質(zhì)1. A=， A=,例4:設(shè)A=a,b,B=0,1,C=u,v則,4.1 有序?qū)εc笛卡兒積,4.1 有序?qū)εc笛卡兒積,4.1 有序?qū)εc笛卡兒積,性質(zhì)5.若AC BD，則A B CD。,4.1 有序?qū)εc笛卡兒積,其逆命題不成立。 A

32、=B=，成立； A ，B ，成立； A= 且 B ，不成立； A 且B= ，不成立。,定義4.由n個(gè)具有給定次序的個(gè)體a1，a2，an組成的序列，稱為有序n元組，記作，其中ai稱為第i個(gè)分量。 =當(dāng)且僅當(dāng)ai=bi（i=1，2，3，n）。 有序n元組仍然是序偶，即=，an。,4.1 有序?qū)εc笛卡兒積,定義5. 設(shè)A1，A2，An是任意的n個(gè)集合，所有有序n元組組成的集合，稱為集合A1，A2，An的笛卡兒積，并用 表示。其中 （i=1，2，n）,4.1 有序?qū)εc笛卡兒積,4.2 二元關(guān)系,定義1.若一個(gè)集合滿足以下條件之一： （1）集合非空，且它的元素都是有序?qū)?（2）集合是空集 則稱該集合為一

33、個(gè)二元關(guān)系。,一、關(guān)系的定義,4.2 二元關(guān)系,例2:任意兩個(gè)集合A,B,若|A|=n,|B|=m,求A到B共有多少不同的二元關(guān)系?,4.2 二元關(guān)系,二、特殊關(guān)系,例5.設(shè)A=2,3,4,B=2,3,4,5,6,定義A到B的二元關(guān)系R:aRb當(dāng)且僅當(dāng)a整除b.求R,MR,R=，,4.2 二元關(guān)系,三、關(guān)系的表示方法,4.2 二元關(guān)系,一個(gè)有限集合A上的關(guān)系R還可以用一個(gè)稱為R的關(guān)系圖來(lái)表示。,4.2 二元關(guān)系,例6：設(shè)A=a，b，c，d，e，A上關(guān)系R=，則R的關(guān)系圖為：,例3:設(shè)A=1,2,3,4,5,6,B=a,b,c,d, R=,求domR,ranR.,解:domR=2,3,4,6,r

34、anR=a,b,d,4.3 關(guān)系的運(yùn)算,例:1.Z上的關(guān)系.,3.空關(guān)系的逆是空關(guān)系.,例3中R的逆關(guān)系R-1=,4.3 關(guān)系的運(yùn)算,4.3 關(guān)系的運(yùn)算,例：1. R1=是的兄弟，R2=是的父親,2. A=1，2，3，4，5，R，S是A上的二元關(guān)系 R=， S=，,4.3 關(guān)系的運(yùn)算,關(guān)系是以序偶為元素的集合，故可對(duì)關(guān)系進(jìn)行集合的運(yùn)算以產(chǎn)生新的關(guān)系。作為關(guān)系，絕對(duì)補(bǔ)運(yùn)算是對(duì)全關(guān)系而言的。,4.3 關(guān)系的運(yùn)算,2. A=1，2，3，4，5，R，S是A上的二元關(guān)系 R=， S=，,由此可知，合成關(guān)系不滿足交換律，滿足結(jié)合律。,4.3 關(guān)系的運(yùn)算,定理8.關(guān)系矩陣的乘法滿足結(jié)合律，即MR1（MR2M

35、R3）=（MR1MR2）MR3,4.3 關(guān)系的運(yùn)算,定理9.設(shè)R1是一個(gè)由A1到A2的關(guān)系，R2是一個(gè)由A2到A3的關(guān)系，Rn是一個(gè)由An到An+1的關(guān)系（Ai都是有限集）。它們的關(guān)系矩陣分別是MR1，MR2，MRn，則合成關(guān)系R1R2Rn的關(guān)系矩陣MR1R2Rn=MR1MR2MRn。,定義5.設(shè)R為A上的關(guān)系，n為自然數(shù)，則R的n次冪定義為： R0=|xA=IA Rn+1=RnR,4.3 關(guān)系的運(yùn)算,冪運(yùn)算的求解：,若R是列舉法表示，可進(jìn)行多次右復(fù)合；,例：A=a，b，c，d，R=，,例：設(shè)A=a，b，c，d，R=，則R0， R2 ，R3，R4。,R0=，,R2=，,R3=，,R4=，,4.

36、3 關(guān)系的運(yùn)算,若R用關(guān)系矩陣M表示，則Rn的關(guān)系矩陣是Mn；,若R是用關(guān)系圖G表示的，則可由G得Rn的關(guān)系圖G。 G與G的頂點(diǎn)集合相同，考察G中每個(gè)頂點(diǎn)x，若在G中 從x出發(fā)經(jīng)過(guò)n步長(zhǎng)的路徑到達(dá)頂點(diǎn)y，則在G中加一條 從x到y(tǒng)的邊。當(dāng)把所有頂點(diǎn)都考察完后，就得到G。,4.3 關(guān)系的運(yùn)算,4.3 關(guān)系的運(yùn)算,定理10.冪運(yùn)算滿足指數(shù)定律：Rn Rm=Rn+m （Rn）m=Rmn,冪運(yùn)算的性質(zhì)：,定理11.設(shè)A為n元集，R是A上的關(guān)系，則存在s、tN，使得Rs=Rt。,4.4 關(guān)系的性質(zhì),定義1.設(shè)RAA， 若x(xAR)，則稱R是自反的； 若x(xA R)，則稱R是反自反的； 若x(xAR)

37、y (yA R)， 則稱R是非自反的。,定義2.設(shè)RAA， 若xy (x,yA RR)， 則稱R是A上的對(duì)稱關(guān)系； 若xy (x,yA R R x=y)， 則稱R是A上的反對(duì)稱關(guān)系； 否則，則稱R是A上的非對(duì)稱關(guān)系。,空關(guān)系既是對(duì)稱的又是反對(duì)稱的.,非空集合上的空關(guān)系是反自反的、對(duì)稱的、反對(duì)稱的、可傳遞的。,空集合上的空關(guān)系則是自反的、反自反的、對(duì)稱的、反對(duì)稱的和可傳遞的。,4.4 關(guān)系的性質(zhì),非空集合上的全關(guān)系是自反的、對(duì)稱的、和可傳遞的。,例2.S=a，b，c，S上的關(guān)系R1=，R2=，R3=，,例3.在集合S=a，b，c，d上的關(guān)系R：， ,，判斷R的性質(zhì)。,4.4 關(guān)系的性質(zhì),定理.設(shè)

38、R是A上的二元關(guān)系，那么R是傳遞的當(dāng)且僅當(dāng)RRR。,4.4 關(guān)系的性質(zhì),根據(jù)定義可證明下面幾個(gè)定理是成立的。,4.4 關(guān)系的性質(zhì),4.4 關(guān)系的性質(zhì),可能有某種關(guān)系，既是對(duì)稱的，又是反對(duì)稱的。,例4.S=a，b，c，S上的關(guān)系R=，,某種關(guān)系，既不是對(duì)稱的，也不是反對(duì)稱的。,例5.S上的關(guān)系Q=，,定理5.設(shè)R在A上是反自反的和可傳遞的，則R必是反對(duì)稱的。,4.4 關(guān)系的性質(zhì),例6.設(shè)A=1，2，3，A上的關(guān)系R=和S=都是A上的傳遞關(guān)系。,傳遞性對(duì)并運(yùn)算不一定保持。,4.4 關(guān)系的性質(zhì),關(guān)系的閉包運(yùn)算是關(guān)系上的一元運(yùn)算，他把給出的關(guān)系R擴(kuò)充成一新關(guān)系Rc，使Rc具有一定的性質(zhì)，且進(jìn)行的擴(kuò)充又

39、是最小的。,4.5 關(guān)系的閉包,該定義表明，r（R）（s（R），t（R）是包含R的 最小自反（對(duì)稱，傳遞）關(guān)系。,必要性：R=r（R），由定義1（1）知，r（R）是自反的，故R是自反的。,4.5 關(guān)系的閉包,4.5 關(guān)系的閉包,4.5 關(guān)系的閉包,4.5 關(guān)系的閉包,4.5 關(guān)系的閉包,4.5 關(guān)系的閉包,4.5 關(guān)系的閉包,3.IA的自反、對(duì)稱和傳遞閉包是什么？,4.空關(guān)系的自反、對(duì)稱和傳遞閉包是什么？,例：A=a，b，c，d，R=，,設(shè)R、r(R)、s(R)、t(R)的關(guān)系矩陣分別為M、Mr、Ms、Mt，則 Mr=M+E Ms=M+M Mt=M+M2+M3+,設(shè)R、r(R)、s(R)、t(

40、R)的關(guān)系矩陣分別為G、Gr、Gs、Gt，則 考察G中的每個(gè)頂點(diǎn)，若沒(méi)有環(huán)就加上一個(gè)，得到Gr； 考察G中每條邊，若有xi到xj的單向邊（ij），則加xj到xi 的反向邊，得Gs； 考察G中每個(gè)頂點(diǎn)xi，找出從xi出發(fā)的所有2步、3步n步 長(zhǎng)的路徑（n為G中的頂點(diǎn)數(shù)）。設(shè)路徑的終點(diǎn)為xj1、xj2、 、xjk，若沒(méi)有從xi到xjl（l=1，2，k)的邊，就加上這條 邊。考察完所有的頂點(diǎn)后，得到Gt。,4.5 關(guān)系的閉包,4.5 關(guān)系的閉包,4.5 關(guān)系的閉包,4.5 關(guān)系的閉包,4.6 等價(jià)關(guān)系與劃分,例：A=1,2,3,4,5,6,7,8，R=|x,yAxy(mod3),4.6 等價(jià)關(guān)系與劃

41、分,4.6 等價(jià)關(guān)系與劃分,一個(gè)集合的劃分往往不是唯一的。,4.6 等價(jià)關(guān)系與劃分,4.6 等價(jià)關(guān)系與劃分,等價(jià)關(guān)系與劃分一一對(duì)應(yīng)。,4.7 偏序關(guān)系,4.7 偏序關(guān)系,由以上定義可知，在具有偏序關(guān)系的集合中任取x、y，有 xy、xy、x與y不可比,例：A=1,2,3，是A上的整除關(guān)系。,蓋住關(guān)系的關(guān)系圖稱哈斯圖.,求法:1.省略關(guān)系圖中每個(gè)結(jié)點(diǎn)處的自環(huán).,2.若xy且y蓋住x,將代表y的結(jié)點(diǎn)放在代表x的結(jié)點(diǎn)之上,并在x與y之間連線,省去有向邊的箭頭.,4.7 偏序關(guān)系,若xy但y不蓋住x，則省去x與y之間的連線。,4.7 偏序關(guān)系,4.7 偏序關(guān)系,4.7 偏序關(guān)系,B的最小元一定是B的下界

42、，同時(shí)也是B的最大下界。 B的最大元一定是B的上界，同時(shí)也是B的最小上界。,一般的調(diào)度問(wèn)題可以描述為： 給定有窮的任務(wù)集T和m臺(tái)機(jī)器，T上存在偏序關(guān)系。如果 t1t2,那么t1完成以后t2才能開(kāi)始工作。,tT，l(t):表示完成任務(wù)t所需的時(shí)間 d(t):表示任務(wù)t的截止時(shí)間。 l(t),d(t)Z+,設(shè)開(kāi)始時(shí)間為0，：T0,1,2,，D表示對(duì)任務(wù)集T的一個(gè) 調(diào)度方案。 (t)：表示任務(wù)t的開(kāi)始時(shí)間； D：表示完成所有任務(wù)的最終時(shí)間,4.7 偏序關(guān)系,假設(shè)每項(xiàng)任務(wù)都可以在任何一臺(tái)機(jī)器上進(jìn)行加工，如果滿足 下述三個(gè)條件，則稱其為可行調(diào)度 tT，（t）l(t)d(t) i,0 i D,|t|t T

43、 （t） i （t）l(t)| m t,t T,tt （t）l(t) (t),4.7 偏序關(guān)系,第五章 函數(shù),5.1 函數(shù)的定義與性質(zhì) 5.2 函數(shù)的復(fù)合與反函數(shù),5.1 函數(shù)的定義與性質(zhì),例1：F1=, F2=,定義2.設(shè)F、G為函數(shù)，則F=GFGGF. 即滿足條件：domF=domG xdomF，都F(x)=G(x).,5.1 函數(shù)的定義與性質(zhì),5.1 函數(shù)的定義與性質(zhì),5.1 函數(shù)的定義與性質(zhì),5.1 函數(shù)的定義與性質(zhì),5.1 函數(shù)的定義與性質(zhì),定義7,單調(diào)函數(shù)可以定義于一般的偏序集上。 每個(gè)子集對(duì)應(yīng)一個(gè)特征函數(shù)，不同的子集則對(duì)應(yīng)不同的特征函數(shù)。 故而可用特征函數(shù)來(lái)標(biāo)記不同的子集。 給定

44、集合A和A上的等價(jià)關(guān)系R，就可以確定一個(gè)自然映射，不同的 等價(jià)關(guān)系將確定不同的自然映射。,5.1 函數(shù)的定義與性質(zhì),算法的評(píng)價(jià)標(biāo)準(zhǔn)：時(shí)間復(fù)雜度、空間復(fù)雜度 估計(jì)復(fù)雜度的方法是：選擇一個(gè)基本運(yùn)算，對(duì)于給定規(guī)模為n的輸入， 計(jì)算算法所做基本運(yùn)算的次數(shù)，將這個(gè)次數(shù)表示為輸入規(guī)模的函數(shù)。 最壞情況下的復(fù)雜度w（n） 平均情況下的復(fù)雜度A（n） 算法分析的主要工作就是估計(jì)復(fù)雜度函數(shù)的階。階越高，增長(zhǎng)越快， 算法復(fù)雜度越高，效率越低。,5.1 函數(shù)的定義與性質(zhì),5.1 函數(shù)的定義與性質(zhì),5.2 函數(shù)的復(fù)合與反函數(shù),5.2 函數(shù)的復(fù)合與反函數(shù),5.2 函數(shù)的復(fù)合與反函數(shù),5.2 函數(shù)的復(fù)合與反函數(shù),第四部分

45、 圖論,第六章 圖的基本概念 第七章 一些重要的圖,第六章 圖的基本概念,6.1 圖 6.2 通路、回路 6.3 圖的連通性 6.4 圖的矩陣表示 6.5 圖的運(yùn)算,用點(diǎn)表示事物，用點(diǎn)之間是否有連線表示事物之間是否 有某種關(guān)系，這樣構(gòu)成的圖，就是圖論中的圖。二元關(guān) 系的關(guān)系圖就是圖，與幾何學(xué)中的圖形有本質(zhì)區(qū)別。因 此，先看無(wú)序積。,定義1.設(shè)A，B為集合，稱a，b|aAbB為A與B 的無(wú)序積，記作A&B。為方便，將a，b記為（a，b）,6.1 圖,定義2.圖G=是有序二元組，其中V(G)是有限非空 集；V中元素稱為G的頂點(diǎn)或結(jié)點(diǎn)，V稱為G的頂點(diǎn)集。E(G) 是V(G)中諸頂點(diǎn)之間邊或弧的集合，

46、E稱為G的邊集。,圖G的邊可以是無(wú)方向的，用vi，vj表示，稱為無(wú)向邊， 只由無(wú)向邊構(gòu)成的圖G稱為無(wú)向圖。,圖G的邊可以是有方向的，用表示，稱為有向邊， 只由有向邊構(gòu)成的圖D稱為有向圖。,6.1 圖,如果圖G中既有有向邊，又有無(wú)向邊，則稱圖G為混合圖。,6.1 圖,D=,ek=E,稱vi為ek的起點(diǎn)， vj為ek的終點(diǎn)， 并稱vi鄰接到vj或vj鄰接于vi。 若ek的終點(diǎn)是el的起點(diǎn)，則ek、el相鄰。,6.1 圖,定義4.在無(wú)向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的無(wú)向邊若多于1條，則稱這些邊 為平行邊，平行邊的條數(shù)為重?cái)?shù)。 在D中，關(guān)聯(lián)一對(duì)頂點(diǎn)的有向邊若多于1條，且始點(diǎn)、終點(diǎn)相同，則 稱這些邊為平行邊。 含

47、平行邊的圖為多重圖，不含平行邊、環(huán)的圖為簡(jiǎn)單圖。,6.1 圖,6.1 圖,6.1 圖,必要條件：階數(shù)相同 邊數(shù)相同 度數(shù)相同的頂點(diǎn)數(shù)相同,6.1 圖,6.1 圖,6.1 圖,6.2 通路與回路,定理1.在n階圖G中，若從頂點(diǎn)vi到vj（vivj）存在通路，則 從vi到vj存在長(zhǎng)度小于或等于（n-1）的通路。,推論：在n階圖G中，若從頂點(diǎn)vi到vj（vivj）存在通路，則 從vi到vj一定存在長(zhǎng)度小于或等于（n-1）的初級(jí)通路。,定理2.在n階圖G中，若存在從頂點(diǎn)vi到自身的回路，則一定 存在長(zhǎng)度小于或等于n的回路。,推論：在n階圖G中，若存在從頂點(diǎn)vi到自身的簡(jiǎn)單回路，則 一定存在長(zhǎng)度小于或等

48、于n的初級(jí)回路。,6.2 通路與回路,無(wú)向圖頂點(diǎn)間的連通關(guān)系是V上的一個(gè)等價(jià)關(guān)系，他的所 有等價(jià)類構(gòu)成V的一個(gè)劃分。任意兩個(gè)頂點(diǎn)vi,vj屬于同一個(gè) 等價(jià)類當(dāng)且僅當(dāng)他們有路連接。,6.3 圖的連通性,6.3 圖的連通性,6.3 圖的連通性,當(dāng)v是G的點(diǎn)割集，則稱v是G的割點(diǎn)。,若v是連通圖G的一個(gè)割點(diǎn)，那么G-v就是不連通或平凡圖。,6.3 圖的連通性,6.3 圖的連通性,6.3 圖的連通性,6.3 圖的連通性,定理3.一個(gè)有向圖D是強(qiáng)連通圖的充要條件是D中存在至少 經(jīng)過(guò)每個(gè)頂點(diǎn)一次的回路。,6.3 圖的連通性,定理4.設(shè)D是n階有向圖，D是單向連通圖當(dāng)且僅當(dāng)D中存在 經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的通

49、路。,6.3 圖的連通性,極大路徑法：,設(shè)G=為n階無(wú)向圖，E。設(shè)l為G中一條路 徑。若此路徑的始點(diǎn)或終點(diǎn)與通路外的頂點(diǎn)相鄰，就將它 們擴(kuò)充到通路中來(lái)，繼續(xù)這一過(guò)程，直到最后得到的通路 的兩個(gè)端點(diǎn)不與通路外的頂點(diǎn)相鄰為止。設(shè)最后得到的路 徑為l+k，稱其為極大路徑。稱使用此種方法證明問(wèn)題 的方法為極大路徑法。,鄰接矩陣A的階就是G的頂點(diǎn)數(shù)n。,6.4 圖的矩陣表示,圖的表示方法： （1）用邊的集合和邊的集合表示，如G= （2）用圖形表示，頂點(diǎn)用小圓圈表示，邊用線段或弧表示 （3）用矩陣表示,鄰接矩陣依賴于V中個(gè)元素的給定次序，對(duì)于V中各元素 的不同給定次序，可以得到同一個(gè)圖G的不同鄰接矩陣。

50、這些矩陣可以通過(guò)交換另一個(gè)矩陣的某些行或?qū)?yīng)的列而 得到。如果兩個(gè)圖有這樣的鄰接矩陣，則這兩個(gè)圖是同構(gòu) 的。,6.4 圖的矩陣表示,若主對(duì)角線某元素不為0，則表示該對(duì)應(yīng)頂點(diǎn)上有自環(huán)。 零矩陣對(duì)應(yīng)的圖為零圖。,6.4 圖的矩陣表示,6.4 圖的矩陣表示,6.4 圖的矩陣表示,6.4 圖的矩陣表示,6.4 圖的矩陣表示,6.4 圖的矩陣表示,6.5 圖的運(yùn)算,6.5 圖的運(yùn)算,第七章 歐拉圖與哈密頓圖,7.1 歐拉圖 7.2 哈密頓圖 7.3二部圖 7.4平面圖 7.5樹(shù),定義1.通過(guò)圖G的每條邊一次且僅一次行遍圖中所有頂點(diǎn)的 通路稱為歐拉通路。通過(guò)圖G的每條邊一次且僅一次行遍圖 中所有頂點(diǎn)的回路

51、稱為歐拉回路。具有歐拉回路的圖稱為 歐拉圖。具有歐拉通路而無(wú)歐拉回路的圖為半歐拉圖。,定理1.無(wú)向圖G為歐拉圖當(dāng)且僅當(dāng)G是連通圖，且G中所有 頂點(diǎn)的度數(shù)都是偶數(shù)。,定理2.如果G是歐拉圖，那么G可分成若干個(gè)邊不重的回路。,7.1 歐拉圖,定理3.具有一條連接頂點(diǎn)vi和vj的歐拉通路的充要條件是 Vi和vj是G中僅有的具有奇數(shù)度的頂點(diǎn)。,定理4.設(shè)連通圖G=有k個(gè)度為奇數(shù)的頂點(diǎn)，則E(G) 可劃分為k/2條簡(jiǎn)單通路。,定理5.有向連通圖D為歐拉圖的充要條件是每個(gè)頂點(diǎn)的入 度等于出度 。,7.1 歐拉圖,定理6.有向連通圖D存在一條歐拉通路的充要條件是恰有 兩個(gè)奇度數(shù)頂點(diǎn)，其中的一個(gè)入度比出度大1

52、，另一個(gè)的 出度比入度大1，而其余頂點(diǎn)的入度等于出度。,7.1 歐拉圖,7.1 歐拉圖,定義1.通過(guò)圖G的每個(gè)頂點(diǎn)一次且僅一次的回路稱為 哈密頓回路. 哈密頓通路是通過(guò)圖G的每個(gè)頂點(diǎn)一次 且僅一次的通路.具有哈密頓回路的圖稱為哈密頓圖. 具有哈密頓通路而不具有哈密頓回路的圖稱為哈密頓 圖. 平凡圖是哈密頓圖。,性質(zhì):,1.連通,度大于等于2 2.哈密頓通路是度為n-1的基本通路,其回路長(zhǎng)為n,7.2 哈密頓圖,7.2 哈密頓圖,7.2 哈密頓圖,例：在某次國(guó)際會(huì)議的預(yù)備會(huì)中，共有8人參加，他們來(lái) 自不同的國(guó)家。已知他們中任何兩個(gè)無(wú)共同語(yǔ)言的人中的 每一個(gè)，與其余有共同語(yǔ)言的人數(shù)之和大于或等于8

53、。問(wèn) 能否將這8人排在圓桌旁，使任何人都能與兩邊的人交談。,定理4.若D為n（n2）階競(jìng)賽圖，則D中具有哈密頓通路。,帶權(quán)圖與貨郎擔(dān)問(wèn)題,貨郎擔(dān)問(wèn)題：,設(shè)有n個(gè)城市，城市之間均有道路，道路的長(zhǎng)度均大于或 等于0。一個(gè)旅行商從某個(gè)城市出發(fā)，要經(jīng)過(guò)每個(gè)城市一 次且僅一次，最后回到出發(fā)的城市。問(wèn)他如何走，才能使 路線最短？,7.5 樹(shù),7.5.1 無(wú)向樹(shù)及其性質(zhì) 7.5.2 生成樹(shù) 7.5.3 根樹(shù)及其應(yīng)用,定義1.連通無(wú)回路的無(wú)向圖稱為無(wú)向樹(shù)，簡(jiǎn)稱樹(shù)，用T 表示 。若無(wú)向圖F至少有兩個(gè)連通分圖都是樹(shù)，稱F為 森林。僅有一個(gè)頂點(diǎn)的樹(shù)稱為平凡樹(shù)。懸掛點(diǎn)稱為樹(shù)葉。,定理1.設(shè)G=是n階m條邊的無(wú)向圖，下

54、列各命題等價(jià)； （1）G是樹(shù)； （2）G的任意兩個(gè)頂點(diǎn)之間有唯一路徑；,7.5.1 無(wú)向樹(shù)及其性質(zhì),（3）G中無(wú)回路且m=n-1； （4）G是連通且m=n-1； （5）G是連通的，且G中任何邊均是割邊； （6）G中無(wú)回路，但若在G的任意兩個(gè)不同的頂點(diǎn)間加 一條邊，則所得的圖中恰有唯一的一個(gè)含有新邊的圈。,定理2.設(shè)T是n階非平凡的無(wú)向樹(shù)，則T中至少有兩片樹(shù)葉。,7.5.1 無(wú)向樹(shù)及其性質(zhì),定義1.設(shè)T是無(wú)向圖G的子圖并且為樹(shù)，則稱T為G的樹(shù)。 若T是G的樹(shù)且為生成子圖，則稱T是G的生成樹(shù)，T中的 邊稱為樹(shù)枝。圖G中不在T中的邊稱作相應(yīng)生成樹(shù)T的弦。 并稱導(dǎo)出子圖GE(G)-E(T)為T的余樹(shù)，

55、記作 。,定理1.無(wú)向圖G具有生成樹(shù)當(dāng)且僅當(dāng)G是連通圖。,推論1： 設(shè)G為n階m條邊的無(wú)向連通圖，則mn-1。,7.5.2 生成樹(shù),7.5.2 生成樹(shù),7.5.2 生成樹(shù),定義4.設(shè)G=是無(wú)向連通帶權(quán)圖，T是G的 一棵生成樹(shù)。T中各條邊帶權(quán)之和稱為T的權(quán)，記作 W(T)。若生成樹(shù)T0在所有生成樹(shù)中有最小的權(quán)，則稱 T0是G的最小生成樹(shù)。,7.5.2 生成樹(shù),7.5.2 生成樹(shù),7.5.3 根樹(shù)及其應(yīng)用,在根樹(shù)中，由于有向邊的方向一致，故在畫(huà)的時(shí)候可以省去邊的方向。,設(shè)T為根樹(shù)，若將T中層數(shù)相同的頂點(diǎn)都標(biāo)定次序，可以將 根樹(shù)分成以下各類：, 若T的每個(gè)分支點(diǎn)至多有r個(gè)兒子，則稱T為r叉樹(shù)； 又若

56、r叉樹(shù)是有序的，則稱其為r叉有序樹(shù)。, 若T的每個(gè)分支點(diǎn)恰好有r個(gè)兒子，則稱T為r叉正則樹(shù)； 又若T是有序的，則稱其為r叉正則有序樹(shù)。, 若T為r叉正則樹(shù)，且每個(gè)樹(shù)葉的層數(shù)均為樹(shù)高，則稱T為r叉 完全正則樹(shù)；又若T是有序的，則稱其為r叉完全正則有序樹(shù)。,7.5.3 根樹(shù)及其應(yīng)用,2叉正則有序樹(shù)的每個(gè)分支點(diǎn)的兩個(gè)兒子導(dǎo)出的根子樹(shù)分別 稱為左子樹(shù)和右子樹(shù)。,在所有的r叉樹(shù)中，2叉樹(shù)最重要。,7.5.3 根樹(shù)及其應(yīng)用,在通信中，常用二進(jìn)制編碼表示符號(hào)。如：A，B，C，D就可 用00，01，10，11分別來(lái)表示，這叫做等長(zhǎng)碼表示方法。適用 于出現(xiàn)的頻率基本相同的情況，當(dāng)出現(xiàn)的頻率相差較大時(shí)，就需 要非

57、等長(zhǎng)的編碼。,7.5.3 根樹(shù)及其應(yīng)用,可用2叉樹(shù)產(chǎn)生二元前綴碼。,設(shè)T是具有t片樹(shù)葉的2叉樹(shù)，則T的每個(gè)分支點(diǎn)有12個(gè)兒子。設(shè) V為T的分支點(diǎn)，若v有兩個(gè)兒子，在由v引出的兩條邊上，左邊標(biāo) 上0，右邊標(biāo)上1。若v只有一個(gè)兒子，由它引出的邊上可以標(biāo)0也 可以標(biāo)1。,7.5.3 根樹(shù)及其應(yīng)用,設(shè)v是T的任意一片樹(shù)葉，從樹(shù)根到v的通路上各邊的標(biāo)號(hào)（0或1） 按通路上邊的順序放在v處，則t片樹(shù)葉處t個(gè)符號(hào)串組成的集合為 一個(gè)二元前綴碼。,定理1.由一棵給定的2叉正則樹(shù)，可以產(chǎn)生惟一的一個(gè)二元前綴碼。,由產(chǎn)生的任一個(gè)前綴碼都可以傳輸符號(hào)。但這些符號(hào)出現(xiàn)頻率不同 時(shí)，就要用各符號(hào)出現(xiàn)的頻率為權(quán)，利用Huffman算法求最優(yōu)2叉樹(shù)， 由最優(yōu)2叉樹(shù)產(chǎn)生的前綴碼稱為最佳前綴碼。用最佳前綴碼傳輸對(duì)應(yīng) 的各符號(hào)能使傳輸?shù)亩M(jìn)制數(shù)位最省，即效率最高。,7.5.3 根樹(shù)及其應(yīng)用,7.4 平面圖及圖的著色,7.4.1 平面圖的基本概念 7.4.2 歐拉公式 7.4.3 平面圖的判斷 7.4.4 平面圖的對(duì)偶圖 7.4.5 圖中頂點(diǎn)的著色 7.4.6 地圖的著色與平面圖的點(diǎn)著色 7.4.7 邊著色,定義1.若圖G能以這樣一來(lái)的方式畫(huà)在曲面上，即除 頂點(diǎn)處外無(wú)任何邊交叉，則稱圖G可嵌入曲面S。若G 可嵌入平面，則稱G是可平面圖或平面圖。 畫(huà)