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

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

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

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

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

。

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

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

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

v

deg(u)≥6，

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

i=1

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

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

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

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

.對調v1,v3兩個結點的顏色后，給著v1的顏色。

.對調v2,v4兩個結點的顏色后，給著v2的顏色。

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

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

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

定義7-8.2

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

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

定義7-8.3

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

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

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

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

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

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

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

，外部通路長度總和為E

，則

E=I+2n。

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

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

t

w(T)=wi

L(wi)

i=1

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

命題邏輯第二章

謂詞邏輯第四章函數

第六章格和布爾代數第七章

圖論第一篇數理邏輯第二篇集合論

第三章集合與關系第四篇圖論教學內容：數理邏輯、集合論、代數結構與布爾代數和圖論共四部分。第五章

代數結構第三篇代數系統第一章命題邏輯

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

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

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

CP規則重點謂詞邏輯推理方法

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