離散數(shù)學7-6對偶圖與著色7-7樹+復(fù)習

7-6對偶圖與著色掌握對偶圖的定義，會畫圖G的對偶圖

G*掌握自對偶圖的定義及必要條件。與平面圖有密切關(guān)系的一個圖論的應(yīng)用是圖形的著色問題，這個問題最早起源于地圖的著色，一個地圖中相鄰國家著以不同顏色，那么最少需用多少種顏色？一百多年前，英國格色里(Guthrie)提出了用四種顏色即可對地圖著色的猜想，1879年肯普(Kempe)給出了這個猜想的第一個證明，但到1890年希伍德(Hewood)發(fā)現(xiàn)肯普證明是錯誤的，但他指出肯普的方法雖不能證明地圖著色用四種顏色就夠了，但可證明用五種顏色就夠了，即五色定理成立。此后四色猜想一直成為數(shù)學家感興趣而未能解決的難題。直到1976年美國數(shù)學家阿佩爾和黑肯宣布：他們用電子計算機證明了四色猜想是成立的。所以從1976年以后就把四色猜想這個名詞改成“四色定理”了。為了敘述圖形著色的有關(guān)定理，下面先介紹對偶圖的概念。一、對偶圖1、對偶圖定義7-6.1對具有面F1,F2,...,

Fn的連通平面圖G=<V,E>實施下列步驟所得到的圖G*稱為圖G的對偶圖（dualofgraph）：如果存在一個圖G*=<V*，E*>滿足下述條件：（a）在G的每一個面Fi的內(nèi)部作一個G*的頂點vi*

。即對圖G的任一個面Fi內(nèi)部有且僅有一個結(jié)點vi*∈V*。(b)若G的面Fi，F(xiàn)j有公共邊ek，則作ek*=(vi*，vj*)，且ek*與ek相交。即若G中面Fi與Fj有公共邊界ek

，那么過邊界的每一邊ek作關(guān)聯(lián)vi*與vj*的一條邊ek*=(vi*,vj*)

。

ek*與G*的其它邊不相交。(c)當且僅當ek只是一個面Fi的邊界時(割邊)，vi*存在一個環(huán)e*k與ek相交。即當ek為單一面Fi的邊界而不是與其它面的公共邊界時，作vi*的一條環(huán)與ek相交（且僅交于一處）。所作的環(huán)不與G*的邊相交。則稱圖G*為G的對偶圖。實線邊圖為平面圖，虛線邊圖為其對偶圖。v*=r，e*=e，r*=v2、自對偶圖定義7-6.2

如果圖G的對偶圖G*同構(gòu)于G,則稱G是自對偶圖。二、圖的著色1、問題的提出該問題起源于地圖的著色問題。圖著色的三種情況:對點著色是對圖G的每個結(jié)點指定一種顏色，使得相鄰結(jié)點的顏色不同;對邊著色給每條邊指定一種顏色使得相鄰的邊的顏色不同，給面著色給每個面指定一種顏色使得有公共邊的兩個面有不同的顏色。對邊著色和對面著色均可轉(zhuǎn)化為對結(jié)點著色問題。從對偶圖的概念，可以看到，對于地圖的著色問題，可以歸納為對于平面圖的結(jié)點的著色問題，因此四色問題可以歸結(jié)為要證明對于任何一個平面圖，一定可以用四種顏色，對它的結(jié)點進行著色，使得鄰接的結(jié)點都有不同的顏色。2、圖的正常著色：圖G的正常著色(或簡稱著色)是指對它的每一個結(jié)點指定一種顏色，使得沒有兩個鄰接的結(jié)點有同一種顏色。如果圖在著色時用了n種顏色，我們稱G為n-色的圖。3、色數(shù)：對于圖G著色時，需要的最少顏色數(shù)稱為G的色數(shù)，記作x(G)。

證明一個圖的色數(shù)為n，首先必須證明用n種顏色可以著色該圖，其次證明用少于n種顏色不能著色該圖。4、對點著色的鮑威爾方法：第一步：對每個結(jié)點按度數(shù)遞減次序進行排列(相同度數(shù)的結(jié)點次序可隨意)第二步：用第一種顏色對第一個結(jié)點著色，并按次序?qū)εc前面著色點不相鄰的每一點著同樣的顏色。第三步：用第二種顏色對未著色的點重復(fù)第二步，用第三種顏色繼續(xù)這種做法，直到全部點均著了色為止。5、定理7-6.1：對于完全圖Kn有χ(Kn)=n。證明：因為完全圖的每一個結(jié)點與其他各個結(jié)點都鄰接，故n個結(jié)點的著色數(shù)不能少于n，又n個結(jié)點的著色數(shù)至多為n，故χ(Kn)=n。6、定理7-6.2：連通平面圖G=<V，E>至少有三個結(jié)點，則必有一點u∈V使得deg(u)≤5。證明：設(shè)|V|=v，|E|=e，若G的每個結(jié)點均有

v

deg(u)≥6，

deg(vi)=2|E|=2e

i=1

則有2e≥6v，即e≥3v>3v-6，與定理矛盾。*7、定理7-6.3：(五色定理)任意平面圖最多是5-色的。

證明思路：對結(jié)點個數(shù)v采用歸納法(1)歸納基礎(chǔ)：圖G的結(jié)點數(shù)為v=1,2，3，4，5時，結(jié)論成立。

(2)歸納假設(shè)：設(shè)G有k個結(jié)點時結(jié)論成立。即G是最多可5-著色的。

(3)歸納推理：需要證明G有k+1個結(jié)點時結(jié)論仍成立。先在G中刪去度數(shù)小于5的結(jié)點u,根據(jù)歸納假設(shè)，所得的圖G-{u}有k個結(jié)點,結(jié)論成立。然后考慮在G-{u}中加上一個結(jié)點的情況。若加入的結(jié)點滿足deg(u)<5，則可以對u正常著色。若加入的結(jié)點滿足deg(u)=5，則與它鄰接的5個結(jié)點可以用4種顏色著色。分兩中情況證明：

.對調(diào)v1,v3兩個結(jié)點的顏色后，給著v1的顏色。

.對調(diào)v2,v4兩個結(jié)點的顏色后，給著v2的顏色。

自從四色猜想提出后，一百多年來，一直成為數(shù)學上的著名難題，它吸引許許多多的人，為之而作出大量辛勞，也得到很多重要結(jié)果，但長久未能得到解決。直到1976年6月，由美國伊利諾斯大學兩名數(shù)學家愛普爾(K.I.Apple)、黑肯(W.Haken)在考西(J.Koch)幫助下借助于電子計算機，用了一百多億次邏輯判斷，花了1200多機時才證明四色猜想是成立的，從此宣告，四色猜想成為四色定理。相應(yīng)地有下面的定理。9、定理：對于任何地圖M，M是四著色的，即χ(M)≤4。8、四色定理：平面圖的色數(shù)不超過4。作業(yè)P321：（1）（4）7-7樹樹是圖論中重要的概念之一，它在計算機科學中應(yīng)用非常廣泛，這里將介紹樹的一些基本性質(zhì)和應(yīng)用。一、樹的概念1、定義7-7.1：一個連通且無回路的無向圖稱為樹（tree）。樹中度數(shù)為1的結(jié)點稱為樹葉（leave）。度數(shù)大于1的結(jié)點稱為分支點（branchednode）或內(nèi)點。每個連通分支是樹的無向圖稱為森林。平凡圖也是樹，稱為平凡樹。2、定理7-7.1：給定圖T=<V，E>，以下關(guān)于樹的定義是等價的。(1)無回路的連通圖(2)無回路且e=v-1(3)連通且e=v-1(4)無回路，但增加一邊后得到且僅得一個回路(5)連通，但刪去任一邊后就不連通(6)每一對結(jié)點間有且僅有一條通路。證明思路：6個命題可以循環(huán)推出。即(1)(2)(3)(4)(5)(6)(1)3、定理7-7.2：任一棵樹中至少存在兩個葉。證明：因T連通則u∈T，deg(u)≥1。設(shè)T有k個一度點，其它點均大于等于2，則

2e=∑deg(vi)≥k+2(v-k)=2v-k。

因e=v-1，故2(v-1)≥2v-k，則k≥2。二、生成樹有一些圖，本身不是樹，但它的子圖卻是樹，一個圖可能有許多子圖是樹，其中很重要的一類是生成樹。1、生成樹定義7-7.2：若G的生成子圖是一棵樹，則稱這棵樹為G的生成樹。設(shè)G的一棵生成樹為T，則T中的邊稱為樹枝，在G中而不在T中的邊稱弦，所有弦的集合稱為生成樹T的補。e1、e7、e5、e8、e3是T的樹枝，e2、e4、e6是T的弦，{e2、e4、e6}是T的補。2、定理7-7.3：連通圖至少有一棵生成樹。證明：如果連通圖G無回路，則G本身就是它的生成樹。如果G有回路，則在回路上任取去掉一條邊，得到圖G1仍是連通的，如G1仍有回路，重復(fù)上述步驟，直到圖Gi中無回路為止，此時該圖就是G的一棵生成樹。由定理的證明過程可以看出，一個連通圖可以有許多生成樹。因為在取定一個回路后，就可以從中去掉任一條邊，去掉的邊不一樣，故可能得到不同的生成樹。一般如果G有v個點e條邊連通，則e≥v-1，則G刪除e-(v-1)條邊，破壞了e-(v-1)個回路，必成G的一棵生成樹，這是”破圈法”。也可以從e條邊中選取v-1條邊并使它不含有回路，這是”避圈法”。3、定理7-7.4：一條回路和任何一棵生成樹的補至少有一條公共邊。證明：若有一條回路和一棵生成樹的補沒有公共邊，那么這回路包含在生成樹中，然而這是不可能的，因為一棵生成樹不能包含回路。4、定理7-7.5：一個邊割集和任何生成樹至少有一條公共邊。證明：若有一個邊割集和一棵生成樹沒有公共邊，那么刪去這個邊割集后，所得子圖必包含該生成樹，這意味著刪去邊割集后仍是連通圖，與邊割集定義矛盾。5、最小生成樹設(shè)G=<V，E>是一連通圖，G的每一條邊e有權(quán)C(e)，G的生成樹T的權(quán)w(T)就是T的邊的權(quán)和。定義7-7.3：在圖G所有生成樹中，樹權(quán)最小的那棵樹稱為G的最小生成樹。

構(gòu)造圖的一棵最小生成樹，即：在e條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。該問題等價于：具體做法:先構(gòu)造一個只含n個頂點的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止?？紤]問題的出發(fā)點:為使生成樹上邊的權(quán)值之和達到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能的小。克魯斯卡爾算法的基本思想：abcdegf195141827168213ae12dcbgf7148531621例如:7121819求最小生成樹的克魯斯卡爾(Kruskal)算法(避圈法)：a)在G中選取最小權(quán)的邊，記作e1，置i=1。b)當i=n-1時結(jié)束，否則轉(zhuǎn)c)。c)設(shè)已選擇邊為e1，e2，……ei，此時無回路。在G中選取不同于這i條邊的邊ei+1，該邊使得{e1，…，ei+1}生成的子圖中無回路，并ei+1是滿足該條件中權(quán)最小的一條邊。d)置i：=i+1，轉(zhuǎn)b)。定理7-7.6：克魯斯卡爾(Kruskal)算法產(chǎn)生的是最小生成樹。作業(yè)327頁（6）(b)的最小生成樹有5棵，最小生成樹的樹權(quán)為11。(a)的最小生成樹：7-8根樹及其應(yīng)用一、根樹1、有向樹定義7-8.1

如果一個有向圖在不考慮邊的方向時是一棵樹，那么，該有向圖稱為有向樹。2、根樹

定義7-8.2

一棵有向樹,如果恰有一個結(jié)點的入度為0，其余所有結(jié)點的入度都為1,則稱為根樹(rootedtree)。入度為0的結(jié)點稱為T的樹根。出度為0的結(jié)點稱為樹葉。出度不為0的結(jié)點稱為分支點或內(nèi)點。

根樹的畫法有：樹根在下，向上生長；樹根在上，向下生長。習慣把有向樹的根畫在最上方，邊的箭頭全指向下，則可以省略全部箭頭，樹根到一個結(jié)點的有向通路的長度稱為該點的層數(shù)。所有結(jié)點的最大層數(shù)稱為樹高。3、子樹定義7-8.3：任一結(jié)點v及其后代導出的子圖稱為根樹的子樹。

定義7-8.3

根樹包含一個或多個結(jié)點,這些結(jié)點中的某一個稱為根,其他所有結(jié)點被分成有限個子根樹。

在有向樹中，結(jié)點的出現(xiàn)次序是沒有意義的。但實際應(yīng)用中，有時要給出同一級中結(jié)點的相對次序，這便導出有序樹的概念。4、有序數(shù)：在根樹中規(guī)定了每一層上結(jié)點的次序，稱為有序樹。為表示結(jié)點間的關(guān)系，有時借用家族中的術(shù)語。定義在以v0為根的樹中，（1）v1，v2,…，vk稱為v0的兒子，v0稱為它們的父親。vi，vj

同為一頂點v的兒子時，稱它們?yōu)樾值?。?）頂點間的父子關(guān)系的傳遞閉包稱為頂點間的祖孫關(guān)系。即當vi為vi+1(i=1,2,…,l-1)的父親時，v1是vl的祖先，vl為v1的子孫。（3）根樹T自身及以它的樹根的子孫為根的根樹（T的子圖），均稱為T的子樹（subtree），后者又稱為T的真子樹。5、m叉樹

定義7-8.4：在根樹中,若每個結(jié)點的出度均≤m，則稱T為m元樹(m叉樹)，若每個分支點的出度恰好等于m，則稱T為m叉完全樹，若T的所有樹葉的層數(shù)均相同，則稱T正則m元樹。若m元樹是有序的，則稱T為m元有序樹，若m元完全樹是有序的則稱T為完全m元有序樹，若m元正則樹是有序的，則稱T為m元正則有序樹。當m=2時，稱為二元樹，二元有序樹的每個結(jié)點至多有兩個兒子，其序按左右分，分別為左兒子，右兒子，任一分支點最多有兩棵子樹，稱為左子樹和右子樹。當m=2時，便可得到常用的二叉樹、完全二叉樹和正則二叉樹。不難看出，二叉樹中的每個結(jié)點v，至多有兩個子樹，分別稱為v的左子樹和右子樹。若v只有一個子樹，則稱它為左子樹或右子樹均可。在二叉樹的圖形表示中，v的左子樹畫在v的左下方，v的右子樹畫在v的右下方。

6.定理7-8.1設(shè)有完全m叉樹，其樹葉的數(shù)目為t,分支數(shù)為i,則(m-1)×i=t-1。

7.定義7-8.5在根樹中，一個結(jié)點的通路長度，就是從樹根到該結(jié)點的通路中的邊數(shù)。分支點的通路長度稱為內(nèi)部通路長度，樹葉的通路長度稱為外部通路長度。二、最優(yōu)樹二叉樹的一個重要應(yīng)用就是最優(yōu)樹問題。給定一組數(shù)w1，w2，…，wn。令一棵二叉樹有n個葉結(jié)點，并對它們分別指派w1，w2，…，wn作為權(quán)，則該二叉樹稱為加權(quán)二叉樹。

8.定理7-8.2設(shè)有完全二叉樹有n個分支點，且內(nèi)部通路長度為總和為I

，外部通路長度總和為E

，則

E=I+2n。

已知w1，w2，…，wn為權(quán)，T0為加權(quán)二叉樹，其權(quán)為w(T0)，如果對任意加權(quán)二叉樹T，它的權(quán)是w(T)，均有w(T0)≥w(T)，則稱T0是最優(yōu)樹或Huffman樹。

9.定義7-8.6在帶權(quán)二叉樹T中，若帶權(quán)為wi樹葉，其通路長度為L(wi),把

t

w(T)=wi

L(wi)

i=1

稱為該帶權(quán)二叉樹權(quán)，所有帶權(quán)w1,w2,…,wt的二叉樹樹中，w(T)最小的那棵樹，稱為最優(yōu)樹。離散數(shù)學總復(fù)習曾慶田Email：qtzeng@163.com2008年.12月第一章

命題邏輯第二章

謂詞邏輯第四章函數(shù)

第六章格和布爾代數(shù)第七章

圖論第一篇數(shù)理邏輯第二篇集合論

第三章集合與關(guān)系第四篇圖論教學內(nèi)容：數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)與布爾代數(shù)和圖論共四部分。第五章

代數(shù)結(jié)構(gòu)第三篇代數(shù)系統(tǒng)第一章命題邏輯

一、知識點1．命題的概念、表示方法；聯(lián)結(jié)詞的邏輯意義。2．命題公式的遞歸定義，自然語言翻譯成命題公式3．真值表的構(gòu)造、命題公式等價的概念。4．重言式與蘊涵式的定義、邏輯意義，邏輯等價與邏輯蘊涵的意義和證明方法。常用的邏輯等價公式和邏輯蘊涵公式。

5．命題公式的對偶式、合取范式、析取范式、主合取范式、主析取范式。邏輯小項、邏輯大項。任給公式化為析取范式、任給公式化為主析取范式、任給公式化為合取范式、任給公式化為主合取范式。

6．命題邏輯的推理理論，主要的推理方法：真值表法、直接證明法、間接證明法。常用推理規(guī)則：P規(guī)則、T規(guī)則、CP規(guī)則。重點命題符號化主析（合）取范式求取方法命題邏輯推理第2章謂詞邏輯一、知識點1.謂詞的概念與表示方法2.命題函數(shù)與量詞3.謂詞邏輯的合式公式與自然語言的翻譯4.謂詞中變元約束5.謂詞邏輯的等價式和蘊含式6.前束范式7.推理理論謂詞邏輯的推理方法規(guī)則：P、T規(guī)則；US、UG、ES、EG規(guī)則公式表：命題邏輯的等價式、蘊含式；謂詞邏輯的常用等價式和蘊含式；推理方法： 直接證明方法 間接證明方法 反證法

CP規(guī)則重點謂詞邏輯推理方法

一、知識點1．集合的基本概念與表示方法；2．集合的運算:并、交、對稱差、冪集、劃分、覆蓋；3．序偶與笛卡爾積；4．關(guān)系及其表示、關(guān)系矩陣、關(guān)系圖；5．關(guān)系的性質(zhì)，復(fù)合關(guān)系、逆關(guān)系；6．關(guān)系的閉包運算：t(R),r(R),s(R),tr(R)；第三章集合與關(guān)系7．集合的劃分與覆蓋、等價關(guān)系與等價類；相容關(guān)系；細分；8．序關(guān)系、偏序集、哈斯圖。9.偏序集中特殊的元素極小元、極大元最小元、最大元上界、下界上確界、下確界第三章集合與關(guān)系重點關(guān)系的三種閉包求取方法關(guān)系的性質(zhì)證明一、知識點1．函數(shù)的概念，定義域、值域、定義域與前域的關(guān)系、值域與陪域的關(guān)系，入射函數(shù)、滿射函數(shù)、雙射函數(shù)。2．復(fù)合函數(shù)、逆函數(shù)的概念，復(fù)合函數(shù)與關(guān)系復(fù)合的聯(lián)系與區(qū)別，逆函數(shù)與逆關(guān)系的聯(lián)系與區(qū)別。第四章函數(shù)第五章 代數(shù)結(jié)構(gòu)運算的性質(zhì)：封閉性、結(jié)合性、分配性、交換性；特殊的元素：幺元、零元、逆元、等冪元的識別主要的代數(shù)系統(tǒng)：廣群、半群、獨異點、群、子群；代數(shù)系統(tǒng)之間的關(guān)系；交換群和循環(huán)群；陪集、拉格朗日定理；同態(tài)映射、同構(gòu)映射；環(huán)、同態(tài)象、域重點半群、含幺半群、群、Abel群的運算性質(zhì)半群、含幺半群、群、Abel群的證明方法第6章格與布爾代數(shù)一、知識點格的概念，偏序