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

1、離散數(shù)學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院第一部分 數(shù)理邏輯第二部分 集合論第三部分 圖論第四部分 抽象代數(shù)離散數(shù)學(xué)第一部分 數(shù)理邏輯數(shù)理邏輯是用數(shù)學(xué)方法研究推理中前提和結(jié)論之間的形式關(guān)系的學(xué)科。推理是由一個或幾個判斷推出一個新判斷的思維形式。數(shù)學(xué)方法是指建立一套表意符號體系，對具體事物進(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. 命題：能判斷真假的陳述句。包含兩層意思：（1）必須是陳述句。 （2）能夠確定（

2、分辨）其真值。1.1 命題和命題聯(lián)結(jié)詞1.1 命題和命題聯(lián)結(jié)詞2. 命題的真值：判斷結(jié)果注意：此處不糾纏具體命題的真假問題，只是將其作為數(shù)學(xué)概念來處理。真值：真用T或1表示，假用F或0表示。3.命題和真值的符號化1.1 命題和命題聯(lián)結(jié)詞1.1 命題和命題聯(lián)結(jié)詞原子命題：不能被分解為更簡單的陳述句復(fù)合命題：原子命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成例：2是有理數(shù)是不對的；2是偶素數(shù)；2或4是素數(shù)；如果2是素數(shù)，則3也是素數(shù)；2是素數(shù)當(dāng)且僅當(dāng)3也是素數(shù)。p：2是有理數(shù)，q：2是偶數(shù)，r：2是素數(shù)，s：3是素數(shù)，t：4是素數(shù)。1.1 命題和命題聯(lián)結(jié)詞4、命題聯(lián)結(jié)詞p pTFFT1.1 命題和命題聯(lián)結(jié)詞pqp qFF

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

4、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é)詞pqp qFFTFTFTFFTTT1.1 命題和命題聯(lián)結(jié)詞p q的邏輯關(guān)系為p與q互為充要條件例：1.3是有理數(shù)當(dāng)且僅當(dāng)加拿大位于亞洲。2.兩圓的面積相等，則他們的半徑相等，反之亦然。pqp qFFFFTTTFTTTF1.1 命題和命題聯(lián)結(jié)詞例：今天第一節(jié)課上離散數(shù)學(xué)或數(shù)據(jù)結(jié)構(gòu)。例：p：北京比天津人口多 q：224

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

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

7、錯。問王教授是哪人？聯(lián)結(jié)詞的完備集n個命題變元可以形成22n個不同的真值函數(shù)對于每個真值函數(shù)，都可以找到許多與之等值的命題公式，而每個命題公式對應(yīng)唯一的與之等值的真值函數(shù)。定義.設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n（n1）元真值 函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則 稱S是聯(lián)結(jié)詞完備集。聯(lián)結(jié)詞的完備集1.4 析取范式與合取范式定義：命題變元及其否定統(tǒng)稱為文字。 僅由有限個文字構(gòu)成的析取式稱為簡單（質(zhì)）析取式。 僅由有限個文字構(gòu)成的合取式稱為簡單（質(zhì)）合取式。注意：單個文字既是簡單析取式又是簡單合取式。討論：設(shè)A為含n個文字的簡單析取式 若A中同時含pi和pi，則？若A為永真式，則？若A為

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

9、式當(dāng)且僅當(dāng)它的每個簡單析 取式為重言式。定理3.任一命題公式都存在與之等值的析取范式和合取范式。范式的求法：消去公式中的蘊涵、等價和異或聯(lián)結(jié)詞 使用雙重否定律和德摩根律，將公式中出現(xiàn) 的否定 詞移到命題變元之前。 利用分配律、結(jié)合律將公式化為合（析）取 范式。范式形式不唯一。1.4 析取范式與合取范式定義：在含有n個命題變元的簡單合（析）取式中，若每個 命題變元和 它的否定式不同時出現(xiàn)，而二者之一必 出現(xiàn)且僅出現(xiàn)一次，且第 i個命題變元或它的否定是 出現(xiàn)在從左算起的第i位上（字典序），稱這樣的簡 單合（析）取式為極小（大）項。性質(zhì)：n個變元可以形成2n個極?。ù螅╉?； 每個極?。ù螅╉椨星覂H有

10、一個成真（假）賦值； 每組賦值下僅有一個極小（大）項為真（假）； 所有極小（大）項的析（合）取為真（假）；1.4 析取范式與合取范式將極小項的成真賦值對應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為i，將對應(yīng)的極小項記為mi。將極大項的成假賦值對應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為i，將對應(yīng)的極大項記為Mi。定義：設(shè)由n個命題變元構(gòu)成的析（合）取范式中所有的簡 單合（析）取式都是極?。ù螅╉?，則稱該析取范 式為主析（合）取范式。1.4 析取范式與合取范式定理.任何命題公式都存在與之等值的主析取范式和主合取范 式，并且是唯一的。1.4 析取范式與合取范式公式法：求析取范式 用同一律補進(jìn)未出現(xiàn)的命題變元 消去永假或重復(fù)出現(xiàn)

11、的變元和極小項 將極小項按下標(biāo)從小到大排列真值表法：列出公式及各極小項的真值表，將每組賦值下 公式及極小項真值都為真的極小項進(jìn)行析取。主析取范式的求法：1.公式法2.真值表法1.4 析取范式與合取范式應(yīng)用：1.求公式的成真、成假賦值 成真賦值為析取范式中所含極小項的編碼的二進(jìn)制數(shù) 成假賦值為合取范式中所含極大項的編碼的二進(jìn)制數(shù)由主析取范式可以直接求主合取范式： 1求出主析取范式中未包含的極小項 2求出與1中求出的極小項下標(biāo)相同的極大項 3做2中極大項之合取1.4 析取范式與合取范式3.判斷兩公式是否等值 若A，B共含有n個命題變元，按n個命題變元求出A與B的主析取范式A、B，若AB，則AB.2

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

13、度，則王曉燕必去游泳。若她去游 泳，她就不會去看電影。所以若王曉燕沒去看電影， 下午溫度必超過了30度。p：溫度超過30度q：王曉燕去游泳r：王曉燕去看電影1.5推理的形式結(jié)構(gòu)1.5推理的形式結(jié)構(gòu)注意：以上都是蘊含式模式若某推理的形式結(jié)構(gòu)與某定律一致，則推理正確成立的等值式可產(chǎn)生兩條定律推理定律可產(chǎn)生相應(yīng)的推理規(guī)則1.5推理的形式結(jié)構(gòu)1.6自然推理系統(tǒng)P定義.一個形式系統(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ī)

14、則得到結(jié)論（永真）1.6自然推理系統(tǒng)P1.6自然推理系統(tǒng)P例：若小王是理科生，則他的數(shù)學(xué)成績一定很好。如果 小王不是理科生，他一定是文科生。小王的數(shù)學(xué)成績 不好。所以小王是文科生。p：小王是理科生q：小王是文科生r：小王的數(shù)學(xué)成績很好1.6自然推理系統(tǒng)P例：如果小張和小王去看電影，則小李也去看電影。小趙 不去看電影或小張去看電影。小王去看電影。所以， 當(dāng)小趙去看電影時，小李也去。p：小張去看電影q：小王去看電影r：小李去看電影s：小趙去看電影1.6自然推理系統(tǒng)P2.歸謬法將結(jié)論的否定作為前提引入，能推出矛盾來，則推理正確例：如果馬會飛或羊不吃草，則母雞就會是飛鳥。如果母 雞是飛鳥，那么烤熟的鴨

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

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

17、對任意的整數(shù)x，都存在整數(shù)y使得xy10。注意：多個量詞出現(xiàn)時，順序一般不能隨便換有些命題符號化形式不唯一2.1一階邏輯命題符號化2.2一階邏輯公式及解釋2.2一階邏輯公式及解釋合式公式也稱謂詞公式，簡稱公式2.2一階邏輯公式及解釋2.2一階邏輯公式及解釋2.2一階邏輯公式及解釋2.2一階邏輯公式及解釋定理.閉式在任何解釋下都變成命題。2.2一階邏輯公式及解釋2.2一階邏輯公式及解釋定理.重言式的代換實例都是永真式，矛盾式的代換 實例都是矛盾式。2.2一階邏輯公式及解釋2.3一階邏輯等值式與置換規(guī)則第一組 命題邏輯中等值式模式的代換實例都是一階邏 輯的等值式模式第二組 一階邏輯中特殊的等值式2

18、.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)行定理證明和邏輯推理，需要把謂詞公式變換為便于使用的規(guī)范形式，就是范式。 定理1：任一謂詞公式都可以化成為與之等值的前束范式。2.4一階邏輯前束范式2.4一階邏輯前束范式2.5一階邏輯的推理理論在一階邏輯中，稱永真的蘊涵式為推理定律。若一個推理的形式結(jié)構(gòu)正是某條推理定律，則該推理顯然是正確的。第一組 命題邏輯推理定律的代換實例第二組 由基本等值式生成的推理定律第三組 以下重要定律第四組 消

19、去量詞和引入量詞的推理規(guī)則1、全稱量詞消去規(guī)則（UI）2.5一階邏輯的推理理論UI規(guī)則成立的條件： （1）取代x的y應(yīng)為任意不在A(x)中約束出現(xiàn)的個體變項； （2）用y取代A(x)中自由出現(xiàn)的x時，必須將所有的自由出現(xiàn)x都取代； （3）自由變元y也可替換為個體域中任意的個體常元c，c為任意不在A(x)中出現(xiàn)過的個體常項。2.5一階邏輯的推理理論含義：如果個體域的所有個體都具有性質(zhì)A，則個體域中的任一個個體都具有性質(zhì)A。 2、存在量詞消去規(guī)則（EI）含義：如果個體域存在有性質(zhì)A的個體，則個體域中必有某一個個體具有性質(zhì)A。 2.5一階邏輯的推理理論ES規(guī)則成立的條件： （1）c是個體域中使A為真

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

21、輯的推理理論定義.一階邏輯自然推理系統(tǒng)F的定義 1.字母表：同一階語言的字母表 2.合式公式：同一階語言合式公式的定義 3.推理規(guī)則 a.前提引入規(guī)則 b.結(jié)論引入規(guī)則 c.置換規(guī)則 d.假言推理規(guī)則 e.附加規(guī)則 f.化簡規(guī)則 g.拒取式規(guī)則 h.假言三段論規(guī)則 i.析取三段論規(guī)則 j.構(gòu)造性二難規(guī)則 k.合取引入規(guī)則 l. UI，EI，UG，EG2.5一階邏輯的推理理論例7：證明邏輯三段論 所有的人總是要死的。 蘇格拉底是人。所以蘇格拉底是要死的。2.5一階邏輯的推理理論2.5一階邏輯的推理理論例10：如果一個人怕困難就不會獲得成功。每一個人或者獲得成功或者是失敗的。有些人未曾失敗過，所以

22、有些人不怕困難。（個體域是人的集合）判斷這個推理是否正確。 例9：根據(jù)前提集合：同事之間總是有工作矛盾的，張平和李明沒有工作矛盾，能得出什么結(jié)論？第二部分 集合論第三章 集合代數(shù)第四章 二元關(guān)系第五章 函數(shù)第三章 集合代數(shù)3.1 集合的基本概念3.2 集合的運算3.3 集合恒等式一、集合的概念集合（set)的含義：一個集合是作為整體識別的、確定的、互相區(qū)別的一些事物的聚集（全體或總體等)。構(gòu)成一個集合的每個事物，成為這個集合中的元素或成員。集合一般用A、B、C表示，集合中的元素用a、b、c表示。但這不是絕對的，因為一個集合可以作為另一個集合的元素。如果x是集合s的一個元素,記作 ; y不是集合

23、s的元素，記作 3.1集合的基本概念例1： 1.偶素數(shù)集合。2.二進(jìn)制的基數(shù)集合。3.英文字母的集合。4.全體實數(shù)的集合。5.自然數(shù)集合。6.整數(shù)集合。7.有理數(shù)集合。8.素數(shù)集合。3.1集合的基本概念3.1集合的基本概念集合的表示方法: 1.列舉法（枚舉法、外延法）把集合的所有元素（元素較少時）寫在一個花括號內(nèi);列出足夠多的元素（元素很多或無窮時）以反映集合中元素的特征。如例1中的1、2、3、5可分別表示為：20，1a，b，cz，A，B，CZ1，2，33.1集合的基本概念2.描述法（概括法）將集合中的元素的性質(zhì)用一個謂詞公式來描述，S=X|P(X),意義為:集合S由且僅由滿足為此公式P(X)

24、的對象組成，即 ，當(dāng)且僅當(dāng)p(a)為真。如例1中的4、6、7可表示為：3.文氏圖用圖形圖像直觀的描述集合之間的相互關(guān)系和有關(guān)運算。3.1集合的基本概念幾個常見集合的表示符號：N：自然數(shù)集合，N=0，1，2，3；I：整數(shù)集合；P：素數(shù)或質(zhì)數(shù)集合；Q：有理數(shù)集合；R：實數(shù)集合；C：復(fù)數(shù)集合；3.1集合的基本概念集合的特性:A.互異性：一個集合的個元素是可以區(qū)分開的，即每一 元素只出現(xiàn)一次。B.無序性：集合中元素排列順序無關(guān)緊要，即集合表示 形式的不唯一性。例2：a，b，c=b，c，a=c，a，b=a，c，b=b，a，c=c，b，a3.1集合的基本概念C.確定性：任一事物是否屬于某一集合，回答是確定

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

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

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

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

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

30、=.區(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，符號化為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=B=，成立；A ，B ，成立；A= 且 B ，不成立； A 且B= ，不成立。定義4.由n個具有給定次序的個體

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

32、關(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,MRR=，4.2 二元關(guān)系三、關(guān)系的表示方法4.2 二元關(guān)系一個有限集合A上的關(guān)系R還可以用一個稱為R的關(guān)系圖來表示。4.2 二元關(guān)系aaaa dabcde例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,6ranR=a,b,d4.3 關(guān)系的運算例:1.Z上的關(guān)系.3.空關(guān)系的逆是空關(guān)系.例3中R的逆關(guān)系R-1=,4.3 關(guān)系的運算4.3 關(guān)系的運算例：1.

33、 R1=是的兄弟，R2=是的父親2. A=1，2，3，4，5，R，S是A上的二元關(guān)系R=，S=，4.3 關(guān)系的運算關(guān)系是以序偶為元素的集合，故可對關(guān)系進(jìn)行集合的運算以產(chǎn)生新的關(guān)系。作為關(guān)系，絕對補運算是對全關(guān)系而言的。4.3 關(guān)系的運算2. A=1，2，3，4，5，R，S是A上的二元關(guān)系R=，S=，由此可知，合成關(guān)系不滿足交換律，滿足結(jié)合律。4.3 關(guān)系的運算定理8.關(guān)系矩陣的乘法滿足結(jié)合律，即MR1（MR2MR3）=（MR1MR2）MR34.3 關(guān)系的運算定理9.設(shè)R1是一個由A1到A2的關(guān)系，R2是一個由A2到A3的關(guān)系，Rn是一個由An到An+1的關(guān)系（Ai都是有限集）。它們的關(guān)系矩陣分

34、別是MR1，MR2，MRn，則合成關(guān)系R1R2Rn的關(guān)系矩陣MR1R2Rn=MR1MR2MRn。定義5.設(shè)R為A上的關(guān)系，n為自然數(shù)，則R的n次冪定義為：R0=|xA=IARn+1=RnR4.3 關(guā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.3 關(guān)系的運算若R用關(guān)系矩陣M表示，則Rn的關(guān)系矩陣是Mn；若R是用關(guān)系圖G表示的，則可由G得Rn的關(guān)系圖G。G與G的頂點集合相同，考察G中每個頂點x，若在G中從x出發(fā)經(jīng)過n步長的路徑到達(dá)頂點y，則在G中加一條從x到

35、y的邊。當(dāng)把所有頂點都考察完后，就得到G。4.3 關(guān)系的運算4.3 關(guān)系的運算定理10.冪運算滿足指數(shù)定律：Rn Rm=Rn+m （Rn）m=Rmn冪運算的性質(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) 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)系?？贞P(guān)系既是對稱的又是反對稱的.非空集合上的空

36、關(guān)系是反自反的、對稱的、反對稱的、可傳遞的?？占仙系目贞P(guān)系則是自反的、反自反的、對稱的、反對稱的和可傳遞的。4.4 關(guān)系的性質(zhì)非空集合上的全關(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。4.4 關(guān)系的性質(zhì)根據(jù)定義可證明下面幾個定理是成立的。4.4 關(guān)系的性質(zhì)4.4 關(guān)系的性質(zhì)可能有某種關(guān)系，既是對稱的，又是反對稱的。例4.S=a，b，c，S上的關(guān)系R=，某種關(guān)系，既不是對稱的，也不是反對稱的。例5.S上的關(guān)系Q=

37、，定理5.設(shè)R在A上是反自反的和可傳遞的，則R必是反對稱的。4.4 關(guān)系的性質(zhì)例6.設(shè)A=1，2，3，A上的關(guān)系R=和S=都是A上的傳遞關(guān)系。傳遞性對并運算不一定保持。4.4 關(guān)系的性質(zhì)關(guān)系的閉包運算是關(guān)系上的一元運算，他把給出的關(guān)系R擴充成一新關(guān)系Rc，使Rc具有一定的性質(zhì)，且進(jìn)行的擴充又是最小的。4.5 關(guān)系的閉包該定義表明，r（R）（s（R），t（R）是包含R的最小自反（對稱，傳遞）關(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.

38、IA的自反、對稱和傳遞閉包是什么？4.空關(guān)系的自反、對稱和傳遞閉包是什么？例：A=a，b，c，d，R=，設(shè)R、r(R)、s(R)、t(R)的關(guān)系矩陣分別為M、Mr、Ms、Mt，則Mr=M+EMs=M+MMt=M+M2+M3+設(shè)R、r(R)、s(R)、t(R)的關(guān)系矩陣分別為G、Gr、Gs、Gt，則考察G中的每個頂點，若沒有環(huán)就加上一個，得到Gr；考察G中每條邊，若有xi到xj的單向邊（ij），則加xj到xi的反向邊，得Gs；考察G中每個頂點xi，找出從xi出發(fā)的所有2步、3步n步長的路徑（n為G中的頂點數(shù)）。設(shè)路徑的終點為xj1、xj2、xjk，若沒有從xi到xjl（l=1，2，k)的邊，就加

39、上這條邊?？疾焱晁械捻旤c后，得到Gt。4.5 關(guān)系的閉包4.5 關(guān)系的閉包4.5 關(guān)系的閉包4.5 關(guān)系的閉包4.6 等價關(guān)系與劃分例：A=1,2,3,4,5,6,7,8，R=|x,yAxy(mod3)4.6 等價關(guān)系與劃分4.6 等價關(guān)系與劃分一個集合的劃分往往不是唯一的。4.6 等價關(guān)系與劃分4.6 等價關(guān)系與劃分等價關(guān)系與劃分一一對應(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)系圖中每個結(jié)點處的自環(huán).2.若xy且y蓋住x,將代表y的結(jié)點放在代

40、表x的結(jié)點之上,并在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的下界，同時也是B的最大下界。B的最大元一定是B的上界，同時也是B的最小上界。一般的調(diào)度問題可以描述為： 給定有窮的任務(wù)集T和m臺機器，T上存在偏序關(guān)系。如果t1t2,那么t1完成以后t2才能開始工作。tT，l(t):表示完成任務(wù)t所需的時間 d(t):表示任務(wù)t的截止時間。 l(t),d(t)Z+設(shè)開始時間為0，：T0,1,2,，D表示對任務(wù)集T的一個調(diào)度方案。 (t)：表示任務(wù)t的開始時間；D：表示完成所有任務(wù)的

41、最終時間4.7 偏序關(guān)系假設(shè)每項任務(wù)都可以在任何一臺機器上進(jìn)行加工，如果滿足下述三個條件，則稱其為可行調(diào)度tT，（t）l(t)d(t) i,0 i D,|t|t T （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=domGxdomF，都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單

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

43、合與反函數(shù)5.2 函數(shù)的復(fù)合與反函數(shù)5.2 函數(shù)的復(fù)合與反函數(shù)5.2 函數(shù)的復(fù)合與反函數(shù)第四部分 圖論第六章 圖的基本概念第七章 一些重要的圖第六章 圖的基本概念6.1 圖 6.2 通路、回路6.3 圖的連通性 6.4 圖的矩陣表示6.5 圖的運算用點表示事物，用點之間是否有連線表示事物之間是否有某種關(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 圖定義2.圖G=是有序二元組，其中V(G)是有限非空集；V中元素稱為G的頂點或結(jié)點

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

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

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

47、路徑法： 設(shè)G=為n階無向圖，E。設(shè)l為G中一條路徑。若此路徑的始點或終點與通路外的頂點相鄰，就將它們擴充到通路中來，繼續(xù)這一過程，直到最后得到的通路的兩個端點不與通路外的頂點相鄰為止。設(shè)最后得到的路徑為l+k，稱其為極大路徑。稱使用此種方法證明問題的方法為極大路徑法。鄰接矩陣A的階就是G的頂點數(shù)n。6.4 圖的矩陣表示圖的表示方法： （1）用邊的集合和邊的集合表示，如G= （2）用圖形表示，頂點用小圓圈表示，邊用線段或弧表示（3）用矩陣表示 鄰接矩陣依賴于V中個元素的給定次序，對于V中各元素的不同給定次序，可以得到同一個圖G的不同鄰接矩陣。這些矩陣可以通過交換另一個矩陣的某些行或?qū)?yīng)的列而得

48、到。如果兩個圖有這樣的鄰接矩陣，則這兩個圖是同構(gòu)的。 6.4 圖的矩陣表示若主對角線某元素不為0，則表示該對應(yīng)頂點上有自環(huán)。零矩陣對應(yīng)的圖為零圖。 6.4 圖的矩陣表示6.4 圖的矩陣表示6.4 圖的矩陣表示6.4 圖的矩陣表示6.4 圖的矩陣表示6.4 圖的矩陣表示6.5 圖的運算6.5 圖的運算第七章 歐拉圖與哈密頓圖7.1 歐拉圖7.2 哈密頓圖7.3二部圖7.4平面圖7.5樹定義1.通過圖G的每條邊一次且僅一次行遍圖中所有頂點的通路稱為歐拉通路。通過圖G的每條邊一次且僅一次行遍圖中所有頂點的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。具有歐拉通路而無歐拉回路的圖為半歐拉圖。定理1.無

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

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

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

52、通的，且G中任何邊均是割邊； （6）G中無回路，但若在G的任意兩個不同的頂點間加一條邊，則所得的圖中恰有唯一的一個含有新邊的圈。定理2.設(shè)T是n階非平凡的無向樹，則T中至少有兩片樹葉。7.5.1 無向樹及其性質(zhì)定義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。7.5.2 生成樹7.5.2 生成樹7.5.2 生成樹定義4.設(shè)G=是無向連通帶

53、權(quán)圖，T是G的一棵生成樹。T中各條邊帶權(quán)之和稱為T的權(quán)，記作W(T)。若生成樹T0在所有生成樹中有最小的權(quán)，則稱T0是G的最小生成樹。 7.5.2 生成樹7.5.2 生成樹7.5.3 根樹及其應(yīng)用在根樹中，由于有向邊的方向一致，故在畫的時候可以省去邊的方向。 設(shè)T為根樹，若將T中層數(shù)相同的頂點都標(biāo)定次序，可以將根樹分成以下各類： 若T的每個分支點至多有r個兒子，則稱T為r叉樹； 又若r叉樹是有序的，則稱其為r叉有序樹。 若T的每個分支點恰好有r個兒子，則稱T為r叉正則樹； 又若T是有序的，則稱其為r叉正則有序樹。 若T為r叉正則樹，且每個樹葉的層數(shù)均為樹高，則稱T為r叉 完全正則樹；又若T是有

54、序的，則稱其為r叉完全正則有序樹。7.5.3 根樹及其應(yīng)用 2叉正則有序樹的每個分支點的兩個兒子導(dǎo)出的根子樹分別稱為左子樹和右子樹。在所有的r叉樹中，2叉樹最重要。7.5.3 根樹及其應(yīng)用 在通信中，常用二進(jìn)制編碼表示符號。如：A，B，C，D就可用00，01，10，11分別來表示，這叫做等長碼表示方法。適用于出現(xiàn)的頻率基本相同的情況，當(dāng)出現(xiàn)的頻率相差較大時，就需要非等長的編碼。7.5.3 根樹及其應(yīng)用可用2叉樹產(chǎn)生二元前綴碼。設(shè)T是具有t片樹葉的2叉樹，則T的每個分支點有12個兒子。設(shè)V為T的分支點，若v有兩個兒子，在由v引出的兩條邊上，左邊標(biāo)上0，右邊標(biāo)上1。若v只有一個兒子，由它引出的邊上

55、可以標(biāo)0也可以標(biāo)1。7.5.3 根樹及其應(yīng)用設(shè)v是T的任意一片樹葉，從樹根到v的通路上各邊的標(biāo)號（0或1）按通路上邊的順序放在v處，則t片樹葉處t個符號串組成的集合為一個二元前綴碼。定理1.由一棵給定的2叉正則樹，可以產(chǎn)生惟一的一個二元前綴碼。由產(chǎn)生的任一個前綴碼都可以傳輸符號。但這些符號出現(xiàn)頻率不同時，就要用各符號出現(xiàn)的頻率為權(quán)，利用Huffman算法求最優(yōu)2叉樹，由最優(yōu)2叉樹產(chǎn)生的前綴碼稱為最佳前綴碼。用最佳前綴碼傳輸對應(yīng)的各符號能使傳輸?shù)亩M(jìn)制數(shù)位最省，即效率最高。7.5.3 根樹及其應(yīng)用7.4 平面圖及圖的著色7.4.1 平面圖的基本概念7.4.2 歐拉公式7.4.3 平面圖的判斷7.

56、4.4 平面圖的對偶圖7.4.5 圖中頂點的著色7.4.6 地圖的著色與平面圖的點著色7.4.7 邊著色定義1.若圖G能以這樣一來的方式畫在曲面上，即除頂點處外無任何邊交叉，則稱圖G可嵌入曲面S。若G可嵌入平面，則稱G是可平面圖或平面圖。 畫出的無邊相交的圖稱為G的平面遷入，無平面嵌入的圖稱為非平面圖。 7.4.1 平面圖的概念定理1.若圖G是平面圖，則G的任何子圖都是平面圖。定理2.若圖G是非平面圖，則G的任何母圖都是非平面圖。推論：Kn (n5)和K3,n(n3)都是非平面圖。定義2.設(shè)G是一個平面圖，由圖的邊所包圍的一個區(qū)域，其內(nèi)部既不包含圖的頂點，也不包含圖的邊，則稱這樣的區(qū)域為G的一

57、個面。如果面的面積是有限的，則稱該面為有限面，否則稱該面為無限面。如果兩個面的邊界至少有一條公共邊，則稱這兩個面是相鄰的，否則是不相鄰的。包圍一個面的所有邊組成的回路稱為該面的邊界，邊界的長度成為面的次數(shù)，記作deg(Ri). 定理3.若圖G是平面圖，則在G中加平行邊和環(huán)后都是平面圖。7.4.1 平面圖的概念定理4. 平面圖G中所有面的次數(shù)之和等于邊數(shù)的2倍。定義3.設(shè)G是簡單平面圖，若在G的任意不相鄰的頂點u,v之間加邊(u,v)，所得圖為非平面圖，則稱G為極大平面圖。定理5.極大平面圖是連通的。定理6.設(shè)G為n階極大平面圖，則G中不可能存在割點和橋。定理7.設(shè)G為n階簡單連通的平面圖，G為極大連通平面圖當(dāng)且僅當(dāng)G的每個面的次數(shù)均為3。定義4.若在非平面圖G中任意刪除一條邊，所得圖為平面圖，則稱G為極小非平面圖。7.4.1 平面圖的概念7.4.2 歐拉公式定理6.設(shè)G是n(n3)階m條邊的極大平面圖，則m=3n-6.7.4.2 歐拉公式7.4.3 平面圖的判斷定義1.設(shè)e=(u,v)為圖G的一條邊，在G中刪除e，增加新的 頂點w，使u,v均與w相鄰，稱