離散數(shù)學(xué)教程課件

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

2、真假的陳述句。,包含兩層意思：,（1）必須是陳述句。,（2）能夠確定（分辨）其真值。,1.1 命題和命題聯(lián)結(jié)詞,6,1.1 命題和命題聯(lián)結(jié)詞,7,2. 命題的真值：判斷結(jié)果,注意：此處不糾纏具體命題的真假問題，只是將其作為數(shù)學(xué)概念來處理。,真值：真用T或1表示，假用F或0表示。,3.命題和真值的符號化,1.1 命題和命題聯(lián)結(jié)詞,8,1.1 命題和命題聯(lián)結(jié)詞,9,原子命題：不能被分解為更簡單的陳述句 復(fù)合命題：原子命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成,例：2是有理數(shù)是不對的；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

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

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

5、據(jù)結(jié)構(gòu)。,18,例：p：北京比天津人口多 q：224 r：烏鴉是黑色的,1.1 命題和命題聯(lián)結(jié)詞,19,5、語句形式化,1.1 命題和命題聯(lián)結(jié)詞,例：2是有理數(shù)是不對的；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不對；q且r；r或t；如果r，則s；r當(dāng)且僅當(dāng)s。,20,1.1 命題和命題聯(lián)結(jié)詞,21,命題常元：表示具體確定內(nèi)容的命題。 命題變元：表示不確定具體內(nèi)容的命題。,1.2 命題公式及其賦值,22,1.2 命題公式及其賦值,同時(shí)約定：（1）最外層的括號可以省去。 （2）

6、不影響運(yùn)算次序的括號也可以省去。,23,1.2 命題公式及其賦值,24,1.2 命題公式及其賦值,25,1.2 命題公式及其賦值,26,1.2 命題公式及其賦值,27,1.2 命題公式及其賦值,28,1.3 命題公式的等值式,29,基本等值式（A，B，C為任意命題公式）,1.3 命題公式的等值式,30,1.3 命題公式的等值式,31,因A，B，C可以代入任意的命題公式，故以上等值式稱為等值式模式。,由已知的等值式推演出另外一些等值式的過程為等值演算。,1.3 命題公式的等值式,32,等值演算的應(yīng)用： 1.驗(yàn)證等值式 2.判定公式的類型 3.解決工作生活中的判斷問題,1.3 命題公式的等值式,甲

7、、已、丙3人根據(jù)口音對王教授是哪人進(jìn)行了判斷： 甲說：王教授不是蘇州人，是上海人 已說：王教授不是上海人，是蘇州人 丙說：王教授既不是上海人，也不是杭州人 結(jié)果3人中有一人全對，一人對一半，一人全錯(cuò)。問王教授是哪人？,33,聯(lián)結(jié)詞的完備集,n個(gè)命題變元可以形成22n個(gè)不同的真值函數(shù),對于每個(gè)真值函數(shù)，都可以找到許多與之等值的命題公式， 而每個(gè)命題公式對應(yīng)唯一的與之等值的真值函數(shù)。,定義.設(shè)S是一個(gè)聯(lián)結(jié)詞集合，如果任何n（n1）元真值 函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則 稱S是聯(lián)結(jié)詞完備集。,34,聯(lián)結(jié)詞的完備集,35,1.4 析取范式與合取范式,定義：命題變元及其否定統(tǒng)稱為文字。

8、僅由有限個(gè)文字構(gòu)成的析取式稱為簡單（質(zhì)）析取式。 僅由有限個(gè)文字構(gòu)成的合取式稱為簡單（質(zhì)）合取式。,注意：單個(gè)文字既是簡單析取式又是簡單合取式。,討論：設(shè)A為含n個(gè)文字的簡單析取式 若A中同時(shí)含pi和pi，則？,若A為永真式，則？,36,若A為永真式，則A中必同時(shí)含有pi和pi，反之亦然。,同理有，若A為簡單合取式， A為永假式的充要條件是A中同時(shí)含有pi和pi。,定理1. 一個(gè)簡單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含有某 個(gè)命題變元及其他的否定。 一個(gè)簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含有某 個(gè)命題變元及其他的否定。,1.4 析取范式與合取范式,37,定義：由有限個(gè)簡單合取式構(gòu)成的析取式稱為析取范式

9、。 由有限個(gè)簡單析取式構(gòu)成的合取式稱為合取范式。 析取范式與合取范式稱為范式。,注意：單個(gè)文字、簡單析取式、簡單合取式都既是析取范 式又是合取范式。,1.4 析取范式與合取范式,定理2. 一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡單合 取式為矛盾式。 一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每個(gè)簡單析 取式為重言式。,38,定理3.任一命題公式都存在與之等值的析取范式和合取范式。,范式的求法：消去公式中的蘊(yùn)涵、等價(jià)和異或聯(lián)結(jié)詞 使用雙重否定律和德摩根律，將公式中出現(xiàn) 的否定 詞移到命題變元之前。 利用分配律、結(jié)合律將公式化為合（析）取 范式。,范式形式不唯一。,1.4 析取范式與合取范式,39,定義：在含

10、有n個(gè)命題變元的簡單合（析）取式中，若每個(gè) 命題變元和 它的否定式不同時(shí)出現(xiàn)，而二者之一必 出現(xiàn)且僅出現(xiàn)一次，且第 i個(gè)命題變元或它的否定是 出現(xiàn)在從左算起的第i位上（字典序），稱這樣的簡 單合（析）取式為極?。ù螅╉?xiàng)。,性質(zhì)：n個(gè)變元可以形成2n個(gè)極?。ù螅╉?xiàng)； 每個(gè)極小（大）項(xiàng)有且僅有一個(gè)成真（假）賦值； 每組賦值下僅有一個(gè)極小（大）項(xiàng)為真（假）； 所有極小（大）項(xiàng)的析（合）取為真（假）；,1.4 析取范式與合取范式,40,將極小項(xiàng)的成真賦值對應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為i， 將對應(yīng)的極小項(xiàng)記為mi。 將極大項(xiàng)的成假賦值對應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為i， 將對應(yīng)的極大項(xiàng)記為Mi。,定義：設(shè)

11、由n個(gè)命題變元構(gòu)成的析（合）取范式中所有的簡 單合（析）取式都是極?。ù螅╉?xiàng)，則稱該析取范 式為主析（合）取范式。,1.4 析取范式與合取范式,定理.任何命題公式都存在與之等值的主析取范式和主合取范 式，并且是唯一的。,41,1.4 析取范式與合取范式,公式法：求析取范式 用同一律補(bǔ)進(jìn)未出現(xiàn)的命題變元 消去永假或重復(fù)出現(xiàn)的變元和極小項(xiàng) 將極小項(xiàng)按下標(biāo)從小到大排列,真值表法：列出公式及各極小項(xiàng)的真值表，將每組賦值下 公式及極小項(xiàng)真值都為真的極小項(xiàng)進(jìn)行析取。,主析取范式的求法：,1.公式法 2.真值表法,42,1.4 析取范式與合取范式,應(yīng)用：1.求公式的成真、成假賦值 成真賦值為析取范式中所含極

12、小項(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)之合取,43,1.4 析取范式與合取范式,3.判斷兩公式是否等值 若A，B共含有n個(gè)命題變元，按n個(gè)命題變元求出A與B的 主析取范式A、B，若AB，則AB.,2.判斷公式的類型 設(shè)A含有n個(gè)命題變元 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)。,44,例：要在A，B，C中挑選

13、2名出國進(jìn)修，選派時(shí)滿足下列條件： 若A去，則C同去 若B去，則C不能去 若C不去，則A或B可以去 問有幾種選派方案，分別是什么？,4.解決實(shí)際問題,1.4 析取范式與合取范式,45,1.5推理的形式結(jié)構(gòu),注意： 推理正確實(shí)際是排除前提真結(jié)論假的情況 推理是否正確與前提的排列順序無關(guān) 推理正確并不能保證B一定為真,46,1.5推理的形式結(jié)構(gòu),推理的形式結(jié)構(gòu),47,1.5推理的形式結(jié)構(gòu),48,例：若下午溫度超過30度，則王曉燕必去游泳。若她去游 泳，她就不會去看電影。所以若王曉燕沒去看電影， 下午溫度必超過了30度。,p：溫度超過30度 q：王曉燕去游泳 r：王曉燕去看電影,1.5推理的形式結(jié)構(gòu)

14、,49,1.5推理的形式結(jié)構(gòu),50,注意： 以上都是蘊(yùn)含式模式 若某推理的形式結(jié)構(gòu)與某定律一致，則推理正確 成立的等值式可產(chǎn)生兩條定律 推理定律可產(chǎn)生相應(yīng)的推理規(guī)則,1.5推理的形式結(jié)構(gòu),51,1.6自然推理系統(tǒng)P,定義.一個(gè)形式系統(tǒng)I由以下4部分組成： 非空的字母表，記作A(I) A(I)中符號構(gòu)成的合式公式集，記作E(I) E(I)中特殊的公式組成的公理集，記作Ax(I) 推理規(guī)則集，記作R(I),任給的前提，應(yīng)用規(guī)則得到結(jié)論（可能真）,任給的公理，應(yīng)用規(guī)則得到結(jié)論（永真）,52,1.6自然推理系統(tǒng)P,53,1.6自然推理系統(tǒng)P,54,例：若小王是理科生，則他的數(shù)學(xué)成績一定很好。如果 小王

15、不是理科生，他一定是文科生。小王的數(shù)學(xué)成績 不好。所以小王是文科生。,p：小王是理科生 q：小王是文科生 r：小王的數(shù)學(xué)成績很好,1.6自然推理系統(tǒng)P,55,例：如果小張和小王去看電影，則小李也去看電影。小趙 不去看電影或小張去看電影。小王去看電影。所以， 當(dāng)小趙去看電影時(shí)，小李也去。,p：小張去看電影 q：小王去看電影 r：小李去看電影 s：小趙去看電影,1.6自然推理系統(tǒng)P,56,2.歸謬法 將結(jié)論的否定作為前提引入，能推出矛盾來，則推理正確,例：如果馬會飛或羊不吃草，則母雞就會是飛鳥。如果母 雞是飛鳥，那么烤熟的鴨子還會跑?？臼斓镍喿硬粫?跑。所以羊吃草。,p：馬會飛 q：羊吃草 r：母

16、雞是飛鳥 s：烤熟的鴨子會跑,1.6自然推理系統(tǒng)P,57,所有的人總是要死的。 蘇格拉底是人。 所以蘇格拉底是要死的。,p: q: r:,第二章 謂詞邏輯,58,第二章 謂詞邏輯,2.1一階邏輯命題符號化 2.2一階邏輯公式及解釋 2.3一階邏輯等值式與置換規(guī)則 2.4一階邏輯前束范式 2.5一階邏輯的推理理論,59,2.1一階邏輯命題符號化,1.個(gè)體詞,所研究對象中可以獨(dú)立存在的具體的或抽象的客體（事物）,表示具體的或特定的客體,表示抽象或泛指的客體,個(gè)體變項(xiàng)的取值范圍稱為個(gè)體域，用D表示,宇宙間一切事物組成的稱為全總個(gè)體域,60,2.謂詞,用來刻劃個(gè)體詞性質(zhì)及個(gè)體詞之間相互關(guān)系的詞,2是有

17、理數(shù) x是無理數(shù) 小王與小李同歲 x與y具有關(guān)系L,是有理數(shù) 是無理數(shù) 與同歲 與具有關(guān)系L,F： G： H： L：,2.1一階邏輯命題符號化,61,3.量詞：個(gè)體詞之間的數(shù)量關(guān)系,（1）全稱量詞 “一切的”，“所有的”，“每一個(gè)”，“任意的”，“凡”，“都” 記作,4.符號化,確定個(gè)體域 確定個(gè)體詞、量詞和謂詞 確定聯(lián)結(jié)詞,2.1一階邏輯命題符號化,62,例：所有的人都是要死的。 有的人用左手寫字。,注意： 全稱量詞的特性謂詞必須作為蘊(yùn)涵式的前件引入 存在量詞的特性謂詞必須作為合取式的合取項(xiàng)引入 同一命題，不同的個(gè)體域符號化的形式可能不同 未指明個(gè)體域即為全總個(gè)體域,2.1一階邏輯命題符號化

18、,63,例：在美國留學(xué)的學(xué)生未必都是亞洲人。 有的兔子比所有的烏龜跑的快。 對任意的整數(shù)x，都存在整數(shù)y使得xy10。,注意： 多個(gè)量詞出現(xiàn)時(shí)，順序一般不能隨便換 有些命題符號化形式不唯一,2.1一階邏輯命題符號化,64,2.2一階邏輯公式及解釋,65,2.2一階邏輯公式及解釋,66,合式公式也稱謂詞公式，簡稱公式,2.2一階邏輯公式及解釋,67,2.2一階邏輯公式及解釋,68,2.2一階邏輯公式及解釋,69,2.2一階邏輯公式及解釋,70,定理.閉式在任何解釋下都變成命題。,2.2一階邏輯公式及解釋,71,2.2一階邏輯公式及解釋,72,定理.重言式的代換實(shí)例都是永真式，矛盾式的代換 實(shí)例都

19、是矛盾式。,2.2一階邏輯公式及解釋,73,2.3一階邏輯等值式與置換規(guī)則,第一組 命題邏輯中等值式模式的代換實(shí)例都是一階邏 輯的等值式模式,第二組 一階邏輯中特殊的等值式,74,2.3一階邏輯等值式與置換規(guī)則,75,D=N，F(xiàn)(x)：x是奇數(shù) G(x)：x是偶數(shù),2.3一階邏輯等值式與置換規(guī)則,76,2.3一階邏輯等值式與置換規(guī)則,77,2.3一階邏輯等值式與置換規(guī)則,78,2.4一階邏輯前束范式,為了方便使用謂詞公式進(jìn)行定理證明和邏輯推理，需要 把謂詞公式變換為便于使用的規(guī)范形式，就是范式。,79,定理1：任一謂詞公式都可以化成為與之等值的前束范式。,2.4一階邏輯前束范式,80,2.4一

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

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

22、義：如果個(gè)體域的任意個(gè)體都具有性質(zhì)A，則個(gè)體域中 的所有個(gè)體都具有性質(zhì)A。,2.5一階邏輯的推理理論,87,4、存在量詞引入規(guī)則（EG）,EG規(guī)則成立的條件： （1）c是個(gè)體域中某個(gè)確定的個(gè)體； （2）代替c的x不在A（c）中出現(xiàn)過。,含義：如果個(gè)體域有某一個(gè)個(gè)體c具有性質(zhì)A，則個(gè)體域中 必存在具有性質(zhì)A的個(gè)體。,2.5一階邏輯的推理理論,88,定義.一階邏輯自然推理系統(tǒng)F的定義 1.字母表：同一階語言的字母表 2.合式公式：同一階語言合式公式的定義 3.推理規(guī)則 a.前提引入規(guī)則 b.結(jié)論引入規(guī)則 c.置換規(guī)則 d.假言推理規(guī)則 e.附加規(guī)則 f.化簡規(guī)則 g.拒取式規(guī)則 h.假言三段論規(guī)則

23、 i.析取三段論規(guī)則 j.構(gòu)造性二難規(guī)則 k.合取引入規(guī)則 l. UI，EI，UG，EG,2.5一階邏輯的推理理論,89,例7：證明邏輯三段論 所有的人總是要死的。 蘇格拉底是人。 所以蘇格拉底是要死的。,2.5一階邏輯的推理理論,90,2.5一階邏輯的推理理論,例10：如果一個(gè)人怕困難就不會獲得成功。每一個(gè)人或 者獲得成功或者是失敗的。有些人未曾失敗過，所以有 些人不怕困難。（個(gè)體域是人的集合）判斷這個(gè)推理是 否正確。,例9：根據(jù)前提集合：同事之間總是有工作矛盾的， 張平和李明沒有工作矛盾，能得出什么結(jié)論？,91,第二部分 集合論,第三章 集合代數(shù) 第四章 二元關(guān)系 第五章 函數(shù),92,第三

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

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

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

27、任一元素，利用某種方法可以判斷它是否是這個(gè)集合的元素，而不是把集合的每一個(gè)元素都給出來。,100,3.1集合的基本概念,集合的元素可以是任何具體或抽象的事物，包括別的集合，但不能是本集合自身。,例4：在一個(gè)住著一些人家的偏僻孤島上，島上只有一個(gè)理發(fā)師a，a給且只給島上所有不能自己理發(fā)的人理發(fā)。問誰給a理發(fā)？,101,定義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)系,102,3.1集合的基本概念,定義3.若A是B的子集且

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

29、元集，其含有k(kn)個(gè)元素的子集稱為它的k元子集。,定義6.由集合S的所有子集組成的集合，稱為集合S的冪 集，記作P（S）。表示為：,有限集S ，|P（S）|=2|S|,例：Aa，b，c，d，c,107,3.2集合的運(yùn)算,一、集合的基本運(yùn)算,108,3.2集合的運(yùn)算,定義5.設(shè)A 為集合， A 的元素的元素構(gòu)成的集合稱為A的廣義并，記作A 。,109,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

30、A1 A2 An,例：Aa，b，c，a，b，e B=a C=a，c，d,110,集合運(yùn)算的優(yōu)先級： 高級：廣義并、廣義交、絕對補(bǔ)、求冪集；同級按從右向左的順 序進(jìn)行 低級：并、交、相對補(bǔ)和對稱差；同級按從左向右的順序進(jìn)行,3.2集合的運(yùn)算,111,3.2集合的運(yùn)算,文氏圖可以用來描述集合間的關(guān)系及其運(yùn)算.在文氏圖中,全集用矩形表示,子集用圓形表示,陰影部分表示運(yùn)算結(jié)果的集合.,二、文氏圖,112,3.2集合的運(yùn)算,113,3.3集合恒等式,一、集合運(yùn)算定律,以下列出集合性質(zhì)中最主要的幾條基本定律，對于全集E的任意子集A，B，C，有：,114,3.3集合恒等式,115,1、基本定義法,根據(jù)集合相

31、等的充要條件等式兩邊互為子集或由定義進(jìn)行等價(jià)推理。,2、公式法,利用已證明過的恒等式去證明另外的恒等式。若表達(dá)式中出現(xiàn)形為 A-B的差集時(shí)，用功能完備律先將運(yùn)算“-”轉(zhuǎn)化為運(yùn)算“ ”和“”。,二、集合恒等式證明,3.3集合恒等式,116,3.3集合恒等式,117,3.3集合恒等式,118,3.3集合恒等式,119,小 結(jié),集合的概念 集合的特性 集合的表示方法:列舉法、描述法、文氏圖 集合的運(yùn)算：并、交、補(bǔ)、差、求冪 集合間的關(guān)系：包含、相等 集合恒等式的證明：定義法、公式法、成員表法,120,第四章二元關(guān)系,4.1 有序?qū)εc笛卡兒積 4.2 二元關(guān)系 4.3 關(guān)系的運(yùn)算 4.4 關(guān)系的性質(zhì)

32、4.5 關(guān)系的閉包 4.6 劃分和等價(jià)關(guān)系 4.7 偏序關(guān)系,121,定義1.由兩個(gè)具有固定次序的個(gè)體a，b組成的序列,稱為序偶,記作.其中a,b稱為序偶的分量.,定義2.設(shè)和是兩個(gè)序偶,若a=c且b=d,則稱這兩個(gè)序偶相等,記作=.,區(qū)別:集合a,b=b,a = (a=b),4.1 有序?qū)εc笛卡兒積,122,例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，符號化為 AB =|xAyB,性質(zhì)1. A=， A=,123,例4:設(shè)A=a,b,B=0,1,C=u,v

33、則,4.1 有序?qū)εc笛卡兒積,124,4.1 有序?qū)εc笛卡兒積,125,4.1 有序?qū)εc笛卡兒積,126,性質(zhì)5.若AC BD，則A B CD。,4.1 有序?qū)εc笛卡兒積,其逆命題不成立。 A=B=，成立； A ，B ，成立； A= 且 B ，不成立； A 且B= ，不成立。,127,定義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笛卡兒積,128,定義5. 設(shè)A1，A2，An是任意的n個(gè)集合，所有有序n元組組成的集合，稱為集合A1，A2

34、，An的笛卡兒積，并用 表示。其中 （i=1，2，n）,4.1 有序?qū)εc笛卡兒積,129,4.2 二元關(guān)系,定義1.若一個(gè)集合滿足以下條件之一： （1）集合非空，且它的元素都是有序?qū)?（2）集合是空集 則稱該集合為一個(gè)二元關(guān)系。,一、關(guān)系的定義,130,4.2 二元關(guān)系,例2:任意兩個(gè)集合A,B,若|A|=n,|B|=m,求A到B共有多少不同的二元關(guān)系?,131,4.2 二元關(guān)系,二、特殊關(guān)系,132,例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)系的表示方法,133,4.2 二元關(guān)系,一個(gè)有限集合A

35、上的關(guān)系R還可以用一個(gè)稱為R的關(guān)系圖來表示。,134,4.2 二元關(guān)系,例6：設(shè)A=a，b，c，d，e，A上關(guān)系R=，則R的關(guān)系圖為：,135,例3:設(shè)A=1,2,3,4,5,6,B=a,b,c,d, R=,求domR,ranR.,解:domR=2,3,4,6,ranR=a,b,d,4.3 關(guān)系的運(yùn)算,136,例:1.Z上的關(guān)系.,3.空關(guān)系的逆是空關(guān)系.,例3中R的逆關(guān)系R-1=,4.3 關(guān)系的運(yùn)算,137,4.3 關(guān)系的運(yùn)算,例：1. R1=是的兄弟，R2=是的父親,2. A=1，2，3，4，5，R，S是A上的二元關(guān)系 R=， S=，,138,4.3 關(guān)系的運(yùn)算,關(guān)系是以序偶為元素的集合，

36、故可對關(guān)系進(jìn)行集合的運(yùn)算以產(chǎn)生新的關(guān)系。作為關(guān)系，絕對補(bǔ)運(yùn)算是對全關(guān)系而言的。,139,4.3 關(guān)系的運(yùn)算,2. A=1，2，3，4，5，R，S是A上的二元關(guān)系 R=， S=，,由此可知，合成關(guān)系不滿足交換律，滿足結(jié)合律。,140,4.3 關(guān)系的運(yùn)算,141,定理8.關(guān)系矩陣的乘法滿足結(jié)合律，即MR1（MR2MR3）=（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。,

37、142,定義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=，,143,例：設(shè)A=a，b，c，d，R=，則R0， R2 ，R3，R4。,R0=，,R2=，,R3=，,R4=，,4.3 關(guān)系的運(yùn)算,144,若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)過n步長的路徑到達(dá)頂點(diǎn)y，則在G中加一條 從x到y(tǒng)的邊。當(dāng)把所有頂點(diǎn)都考察完后，就得到

38、G。,4.3 關(guān)系的運(yùn)算,145,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。,146,4.4 關(guān)系的性質(zhì),定義1.設(shè)RAA， 若x(xAR)，則稱R是自反的； 若x(xA R)，則稱R是反自反的； 若x(xAR) y (yA R)， 則稱R是非自反的。,定義2.設(shè)RAA， 若xy (x,yA RR)， 則稱R是A上的對稱關(guān)系； 若xy (x,yA R R x=y)， 則稱R是A上的反對稱關(guān)系； 否則，則稱R是A上的非對稱關(guān)系。,147,空關(guān)系既是對稱的又是反

39、對稱的.,非空集合上的空關(guān)系是反自反的、對稱的、反對稱的、可傳遞的。,空集合上的空關(guān)系則是自反的、反自反的、對稱的、反對稱的和可傳遞的。,4.4 關(guān)系的性質(zhì),148,非空集合上的全關(guān)系是自反的、對稱的、和可傳遞的。,例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è)R是A上的二元關(guān)系，那么R是傳遞的當(dāng)且僅當(dāng)RRR。,149,4.4 關(guān)系的性質(zhì),根據(jù)定義可證明下面幾個(gè)定理是成立的。,150,4.4 關(guān)系的性質(zhì),151,4.4 關(guān)系的性質(zhì),152,可能有某種關(guān)系，既是對稱的，又是反對稱的。,例4.

40、S=a，b，c，S上的關(guān)系R=，,某種關(guān)系，既不是對稱的，也不是反對稱的。,例5.S上的關(guān)系Q=，,定理5.設(shè)R在A上是反自反的和可傳遞的，則R必是反對稱的。,4.4 關(guān)系的性質(zhì),153,例6.設(shè)A=1，2，3，A上的關(guān)系R=和S=都是A上的傳遞關(guān)系。,傳遞性對并運(yùn)算不一定保持。,4.4 關(guān)系的性質(zhì),154,關(guān)系的閉包運(yùn)算是關(guān)系上的一元運(yùn)算，他把給出的關(guān)系R擴(kuò)充成一新關(guān)系Rc，使Rc具有一定的性質(zhì)，且進(jìn)行的擴(kuò)充又是最小的。,4.5 關(guān)系的閉包,155,該定義表明，r（R）（s（R），t（R）是包含R的 最小自反（對稱，傳遞）關(guān)系。,必要性：R=r（R），由定義1（1）知，r（R）是自反的，故R

41、是自反的。,4.5 關(guān)系的閉包,156,4.5 關(guān)系的閉包,157,4.5 關(guān)系的閉包,158,4.5 關(guān)系的閉包,159,4.5 關(guān)系的閉包,160,4.5 關(guān)系的閉包,161,4.5 關(guān)系的閉包,3.IA的自反、對稱和傳遞閉包是什么？,4.空關(guān)系的自反、對稱和傳遞閉包是什么？,例：A=a，b，c，d，R=，,162,設(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(R)的關(guān)系矩陣分別為G、Gr、Gs、Gt，則 考察G中的每個(gè)頂點(diǎn)，若沒有環(huán)就加上一個(gè)，得到Gr； 考察G中每條邊，若有x

42、i到xj的單向邊（ij），則加xj到xi 的反向邊，得Gs； 考察G中每個(gè)頂點(diǎn)xi，找出從xi出發(fā)的所有2步、3步n步 長的路徑（n為G中的頂點(diǎn)數(shù)）。設(shè)路徑的終點(diǎn)為xj1、xj2、 、xjk，若沒有從xi到xjl（l=1，2，k)的邊，就加上這條 邊?？疾焱晁械捻旤c(diǎn)后，得到Gt。,4.5 關(guān)系的閉包,163,4.5 關(guān)系的閉包,164,4.5 關(guān)系的閉包,165,4.5 關(guān)系的閉包,166,4.6 等價(jià)關(guān)系與劃分,例：A=1,2,3,4,5,6,7,8，R=|x,yAxy(mod3),167,4.6 等價(jià)關(guān)系與劃分,168,4.6 等價(jià)關(guān)系與劃分,169,一個(gè)集合的劃分往往不是唯一的。,4.

43、6 等價(jià)關(guān)系與劃分,170,4.6 等價(jià)關(guān)系與劃分,等價(jià)關(guān)系與劃分一一對應(yīng)。,171,4.7 偏序關(guān)系,172,4.7 偏序關(guān)系,由以上定義可知，在具有偏序關(guān)系的集合中任取x、y，有 xy、xy、x與y不可比,例：A=1,2,3，是A上的整除關(guān)系。,173,蓋住關(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之間的連線。,174,4.7 偏序關(guān)系,175,4.7 偏序關(guān)系,176,4.7 偏序關(guān)系,B的最小元一定是B的下界，同時(shí)也

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

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

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

47、數(shù),190,5.2 函數(shù)的復(fù)合與反函數(shù),191,5.2 函數(shù)的復(fù)合與反函數(shù),192,5.2 函數(shù)的復(fù)合與反函數(shù),193,第四部分 圖論,第六章 圖的基本概念 第七章 一些重要的圖,194,第六章 圖的基本概念,6.1 圖 6.2 通路、回路 6.3 圖的連通性 6.4 圖的矩陣表示 6.5 圖的運(yùn)算,195,用點(diǎn)表示事物，用點(diǎn)之間是否有連線表示事物之間是否 有某種關(guān)系，這樣構(gòu)成的圖，就是圖論中的圖。二元關(guān) 系的關(guān)系圖就是圖，與幾何學(xué)中的圖形有本質(zhì)區(qū)別。因 此，先看無序積。,定義1.設(shè)A，B為集合，稱a，b|aAbB為A與B 的無序積，記作A&B。為方便，將a，b記為（a，b）,6.1 圖,19

48、6,定義2.圖G=是有序二元組，其中V(G)是有限非空 集；V中元素稱為G的頂點(diǎn)或結(jié)點(diǎn)，V稱為G的頂點(diǎn)集。E(G) 是V(G)中諸頂點(diǎn)之間邊或弧的集合，E稱為G的邊集。,圖G的邊可以是無方向的，用vi，vj表示，稱為無向邊， 只由無向邊構(gòu)成的圖G稱為無向圖。,圖G的邊可以是有方向的，用表示，稱為有向邊， 只由有向邊構(gòu)成的圖D稱為有向圖。,6.1 圖,197,如果圖G中既有有向邊，又有無向邊，則稱圖G為混合圖。,6.1 圖,198,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.在無

49、向圖中，關(guān)聯(lián)一對頂點(diǎn)的無向邊若多于1條，則稱這些邊 為平行邊，平行邊的條數(shù)為重?cái)?shù)。 在D中，關(guān)聯(lián)一對頂點(diǎn)的有向邊若多于1條，且始點(diǎn)、終點(diǎn)相同，則 稱這些邊為平行邊。 含平行邊的圖為多重圖，不含平行邊、環(huán)的圖為簡單圖。,199,6.1 圖,200,6.1 圖,201,6.1 圖,必要條件：階數(shù)相同 邊數(shù)相同 度數(shù)相同的頂點(diǎn)數(shù)相同,202,6.1 圖,203,6.1 圖,204,6.1 圖,205,6.2 通路與回路,206,定理1.在n階圖G中，若從頂點(diǎn)vi到vj（vivj）存在通路，則 從vi到vj存在長度小于或等于（n-1）的通路。,推論：在n階圖G中，若從頂點(diǎn)vi到vj（vivj）存在通路

50、，則 從vi到vj一定存在長度小于或等于（n-1）的初級通路。,定理2.在n階圖G中，若存在從頂點(diǎn)vi到自身的回路，則一定 存在長度小于或等于n的回路。,推論：在n階圖G中，若存在從頂點(diǎn)vi到自身的簡單回路，則 一定存在長度小于或等于n的初級回路。,6.2 通路與回路,207,無向圖頂點(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 圖的連通性,208,6.3 圖的連通性,209,6.3 圖的連通性,210,當(dāng)v是G的點(diǎn)割集，則稱v是G的割點(diǎn)。,若v是連通圖G的一個(gè)割點(diǎn)，那么G-v就是不連通或平凡圖。,

51、6.3 圖的連通性,211,6.3 圖的連通性,212,6.3 圖的連通性,213,6.3 圖的連通性,214,定理3.一個(gè)有向圖D是強(qiáng)連通圖的充要條件是D中存在至少 經(jīng)過每個(gè)頂點(diǎn)一次的回路。,6.3 圖的連通性,定理4.設(shè)D是n階有向圖，D是單向連通圖當(dāng)且僅當(dāng)D中存在 經(jīng)過每個(gè)頂點(diǎn)至少一次的通路。,215,6.3 圖的連通性,極大路徑法：,設(shè)G=為n階無向圖，E。設(shè)l為G中一條路 徑。若此路徑的始點(diǎn)或終點(diǎn)與通路外的頂點(diǎn)相鄰，就將它 們擴(kuò)充到通路中來，繼續(xù)這一過程，直到最后得到的通路 的兩個(gè)端點(diǎn)不與通路外的頂點(diǎn)相鄰為止。設(shè)最后得到的路 徑為l+k，稱其為極大路徑。稱使用此種方法證明問題 的方法

52、為極大路徑法。,216,鄰接矩陣A的階就是G的頂點(diǎn)數(shù)n。,6.4 圖的矩陣表示,圖的表示方法： （1）用邊的集合和邊的集合表示，如G= （2）用圖形表示，頂點(diǎn)用小圓圈表示，邊用線段或弧表示 （3）用矩陣表示,217,鄰接矩陣依賴于V中個(gè)元素的給定次序，對于V中各元素 的不同給定次序，可以得到同一個(gè)圖G的不同鄰接矩陣。 這些矩陣可以通過交換另一個(gè)矩陣的某些行或?qū)?yīng)的列而 得到。如果兩個(gè)圖有這樣的鄰接矩陣，則這兩個(gè)圖是同構(gòu) 的。,6.4 圖的矩陣表示,若主對角線某元素不為0，則表示該對應(yīng)頂點(diǎn)上有自環(huán)。 零矩陣對應(yīng)的圖為零圖。,218,6.4 圖的矩陣表示,219,6.4 圖的矩陣表示,220,6.

53、4 圖的矩陣表示,221,6.4 圖的矩陣表示,222,6.4 圖的矩陣表示,223,6.4 圖的矩陣表示,224,6.5 圖的運(yùn)算,225,6.5 圖的運(yùn)算,226,第七章 歐拉圖與哈密頓圖,7.1 歐拉圖 7.2 哈密頓圖 7.3二部圖 7.4平面圖 7.5樹,227,定義1.通過圖G的每條邊一次且僅一次行遍圖中所有頂點(diǎn)的 通路稱為歐拉通路。通過圖G的每條邊一次且僅一次行遍圖 中所有頂點(diǎn)的回路稱為歐拉回路。具有歐拉回路的圖稱為 歐拉圖。具有歐拉通路而無歐拉回路的圖為半歐拉圖。,定理1.無向圖G為歐拉圖當(dāng)且僅當(dāng)G是連通圖，且G中所有 頂點(diǎn)的度數(shù)都是偶數(shù)。,定理2.如果G是歐拉圖，那么G可分成

54、若干個(gè)邊不重的回路。,7.1 歐拉圖,228,定理3.具有一條連接頂點(diǎn)vi和vj的歐拉通路的充要條件是 Vi和vj是G中僅有的具有奇數(shù)度的頂點(diǎn)。,定理4.設(shè)連通圖G=有k個(gè)度為奇數(shù)的頂點(diǎn)，則E(G) 可劃分為k/2條簡單通路。,定理5.有向連通圖D為歐拉圖的充要條件是每個(gè)頂點(diǎn)的入 度等于出度 。,7.1 歐拉圖,229,定理6.有向連通圖D存在一條歐拉通路的充要條件是恰有 兩個(gè)奇度數(shù)頂點(diǎn)，其中的一個(gè)入度比出度大1，另一個(gè)的 出度比入度大1，而其余頂點(diǎn)的入度等于出度。,7.1 歐拉圖,230,7.1 歐拉圖,231,定義1.通過圖G的每個(gè)頂點(diǎn)一次且僅一次的回路稱為 哈密頓回路. 哈密頓通路是通過

55、圖G的每個(gè)頂點(diǎn)一次 且僅一次的通路.具有哈密頓回路的圖稱為哈密頓圖. 具有哈密頓通路而不具有哈密頓回路的圖稱為哈密頓 圖. 平凡圖是哈密頓圖。,性質(zhì):,1.連通,度大于等于2 2.哈密頓通路是度為n-1的基本通路,其回路長為n,7.2 哈密頓圖,232,7.2 哈密頓圖,233,7.2 哈密頓圖,例：在某次國際會議的預(yù)備會中，共有8人參加，他們來 自不同的國家。已知他們中任何兩個(gè)無共同語言的人中的 每一個(gè)，與其余有共同語言的人數(shù)之和大于或等于8。問 能否將這8人排在圓桌旁，使任何人都能與兩邊的人交談。,定理4.若D為n（n2）階競賽圖，則D中具有哈密頓通路。,234,帶權(quán)圖與貨郎擔(dān)問題,貨郎擔(dān)

56、問題：,設(shè)有n個(gè)城市，城市之間均有道路，道路的長度均大于或 等于0。一個(gè)旅行商從某個(gè)城市出發(fā)，要經(jīng)過每個(gè)城市一 次且僅一次，最后回到出發(fā)的城市。問他如何走，才能使 路線最短？,235,7.5 樹,7.5.1 無向樹及其性質(zhì) 7.5.2 生成樹 7.5.3 根樹及其應(yīng)用,236,定義1.連通無回路的無向圖稱為無向樹，簡稱樹，用T 表示 。若無向圖F至少有兩個(gè)連通分圖都是樹，稱F為 森林。僅有一個(gè)頂點(diǎn)的樹稱為平凡樹。懸掛點(diǎn)稱為樹葉。,定理1.設(shè)G=是n階m條邊的無向圖，下列各命題等價(jià)； （1）G是樹； （2）G的任意兩個(gè)頂點(diǎn)之間有唯一路徑；,7.5.1 無向樹及其性質(zhì),237,（3）G中無回路且m

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

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

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

60、可用2叉樹產(chǎn)生二元前綴碼。,設(shè)T是具有t片樹葉的2叉樹，則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 根樹及其應(yīng)用,248,設(shè)v是T的任意一片樹葉，從樹根到v的通路上各邊的標(biāo)號（0或1） 按通路上邊的順序放在v處，則t片樹葉處t個(gè)符號串組成的集合為 一個(gè)二元前綴碼。,定理1.由一棵給定的2叉正則樹，可以產(chǎn)生惟一的一個(gè)二元前綴碼。,由產(chǎn)生的任一個(gè)前綴碼都可以傳輸符號。但這些符號出現(xiàn)頻率不同 時(shí)，就要用各符號出現(xiàn)的頻率為權(quán)，利用Huffman算法求最優(yōu)2叉樹， 由