離散數(shù)學(xué)-7-6對(duì)偶圖與著色7-7-樹(shù)復(fù)習(xí)

1、7-6 對(duì)偶圖與著色,掌握對(duì)偶圖的定義，會(huì)畫(huà)圖G的對(duì)偶圖 G*掌握自對(duì)偶圖的定義及必要條件。,與平面圖有密切關(guān)系的一個(gè)圖論的應(yīng)用是圖形的著色問(wèn)題，這個(gè)問(wèn)題最早起源于地圖的著色，一個(gè)地圖中相鄰國(guó)家著以不同顏色，那么最少需用多少種顏色？一百多年前，英國(guó)格色里(Guthrie)提出了用四種顏色即可對(duì)地圖著色的猜想，1879年肯普(Kempe)給出了這個(gè)猜想的第一個(gè)證明，但到1890年希伍德(Hewood)發(fā)現(xiàn)肯普證明是錯(cuò)誤的，但他指出肯普

2、的方法 雖不能證明地圖著色用四種顏色就夠了，但可證明用五種顏色就夠了，即五色定理成立。,此后四色猜想一直成為數(shù)學(xué)家感興趣而未能解決的難題。直到1976年美國(guó)數(shù)學(xué)家阿佩爾和黑肯宣布：他們用電子計(jì)算機(jī)證明了四色猜想是成立的。所以從1976年以后就把四色猜想這個(gè)名詞改成“四色定理”了。為了敘述圖形著色的有關(guān)定理，下面先介紹對(duì)偶圖的概念。,一、對(duì)偶圖1、對(duì)偶圖定義7-6.1 對(duì)具有面F1 ,F2,..., Fn的連通平面圖G=實(shí)施

3、下列步驟所得到的圖G*稱(chēng)為圖G的對(duì)偶圖（dual of graph）：,如果存在一個(gè)圖G*=滿(mǎn)足下述條件：,（a）在G的每一個(gè)面Fi的內(nèi)部作一個(gè)G*的頂點(diǎn)vi* 。即對(duì)圖G的任一個(gè)面Fi內(nèi)部有且僅有一個(gè)結(jié)點(diǎn)vi*∈V*。,(b)若G的面Fi，F(xiàn)j有公共邊ek，則作ek*=(vi*，vj*)，且ek*與ek相交。 即若G中面Fi與Fj有公共邊界ek ，那么過(guò)邊界的每一邊ek作關(guān)聯(lián)vi*與vj*的一條邊ek* =(vi*,

4、 vj*) 。 ek*與G*的其它邊不相交。,(c)當(dāng)且僅當(dāng)ek只是一個(gè)面Fi的邊界時(shí)(割邊)，vi*存在一個(gè)環(huán)e*k與ek相交。 即當(dāng)ek為單一面Fi的邊界而不是與其它面的公共邊界時(shí)，作vi*的一條環(huán)與ek相交（且僅交于一處）。所作的環(huán)不與 G*的邊相交。,則稱(chēng)圖G*為G的對(duì)偶圖。,,實(shí)線(xiàn)邊圖為平面圖，虛線(xiàn)邊圖為其對(duì)偶圖。,,,,,,,,,,,,,,,,,,,v*=r，e*=e，r*=v,2、自對(duì)偶圖定義7-6.2 如

5、果圖G的對(duì)偶圖G*同構(gòu)于G,則稱(chēng)G是自對(duì)偶圖。,,,,,,,,,二、圖的著色1、問(wèn)題的提出該問(wèn)題起源于地圖的著色問(wèn)題。圖著色的三種情況:對(duì)點(diǎn)著色 是對(duì)圖G的每個(gè)結(jié)點(diǎn)指定一種顏色，使得相鄰結(jié)點(diǎn)的顏色不同;對(duì)邊著色 給每條邊指定一種顏色使得相鄰的邊的顏色不同，給面著色 給每個(gè)面指定一種顏色使得有公共邊的兩個(gè)面有不同的顏色。對(duì)邊著色和對(duì)面著色均可轉(zhuǎn)化為對(duì)結(jié)點(diǎn)著色問(wèn)題。,從對(duì)偶圖的概念，可以看到，對(duì)于地圖的著色問(wèn)題，可以歸納為對(duì)

6、于平面圖的結(jié)點(diǎn)的著色問(wèn)題，因此四色問(wèn)題可以歸結(jié)為要證明對(duì)于任何一個(gè)平面圖，一定可以用四種顏色，對(duì)它的結(jié)點(diǎn)進(jìn)行著色，使得鄰接的結(jié)點(diǎn)都有不同的顏色。,2、圖的正常著色：圖G的正常著色(或簡(jiǎn)稱(chēng)著色)是指對(duì)它的每一個(gè)結(jié)點(diǎn)指定一種顏色，使得沒(méi)有兩個(gè)鄰接的結(jié)點(diǎn)有同一種顏色。如果圖在著色時(shí)用了n種顏色，我們稱(chēng)G為n-色的圖。3、色數(shù)：對(duì)于圖G著色時(shí)，需要的最少顏色數(shù)稱(chēng)為G的色數(shù)，記作x(G)。,證明一個(gè)圖的色數(shù)為n，首先必須證明用n種顏色可以著色該

7、圖，其次證明用少于n種顏色不能著色該圖。,4、對(duì)點(diǎn)著色的鮑威爾方法：第一步：對(duì)每個(gè)結(jié)點(diǎn)按度數(shù)遞減次序進(jìn)行排列(相同度數(shù)的結(jié)點(diǎn)次序可隨意)第二步：用第一種顏色對(duì)第一個(gè)結(jié)點(diǎn)著色，并按次序?qū)εc前面著色點(diǎn)不相鄰的每一點(diǎn)著同樣的顏色。第三步：用第二種顏色對(duì)未著色的點(diǎn)重復(fù)第二步，用第三種顏色繼續(xù)這種做法，直到全部點(diǎn)均著了色為止。,5、定理7-6.1：對(duì)于完全圖Kn有χ(Kn)=n。,證明：因?yàn)橥耆珗D的每一個(gè)結(jié)點(diǎn)與其他各個(gè)結(jié)點(diǎn)都鄰接，故n個(gè)結(jié)點(diǎn)

8、的著色數(shù)不能少于n，又n個(gè)結(jié)點(diǎn)的著色數(shù)至多為n，故χ(Kn)=n。,6、定理7-6.2：連通平面圖G=至少有三個(gè)結(jié)點(diǎn)，則必有一點(diǎn)u∈V使得deg(u)≤5。,證明：設(shè)|V|=v，|E|=e，若G的每個(gè)結(jié)點(diǎn)均有 v deg(u)≥6，? deg(vi )= 2|E|= 2e i=1

9、 則有2e≥6v，即e≥3v>3v-6，與定理矛盾。,*7、定理7-6.3：(五色定理)任意平面圖最多是5-色的。,? 證明思路：對(duì)結(jié)點(diǎn)個(gè)數(shù)v采用歸納法 (1)歸納基礎(chǔ)：圖G的結(jié)點(diǎn)數(shù)為v=1,2，3，4，5時(shí)，結(jié)論成立。 (2)歸納假設(shè)：設(shè)G有k個(gè)結(jié)點(diǎn)時(shí)結(jié)論成立。即G是最多可5-著色的。 (3)歸納推理：需要證明G有k+1個(gè)結(jié)點(diǎn)時(shí)結(jié)論仍成立。 先在G中刪去度數(shù)小于5的結(jié)點(diǎn)u,根據(jù)

10、歸納假設(shè)，所得的圖G-{u}有k個(gè)結(jié)點(diǎn),結(jié)論成立。然后考慮在G-{u}中加上一個(gè)結(jié)點(diǎn)的情況。若加入的結(jié)點(diǎn)滿(mǎn)足deg (u)<5，則可以對(duì)u正常著色。若加入的結(jié)點(diǎn)滿(mǎn)足deg (u)=5，則與它鄰接的5個(gè)結(jié)點(diǎn)可以用4種顏色著色。分兩中情況證明： ?. 對(duì)調(diào)v1,v3兩個(gè)結(jié)點(diǎn)的顏色后，給著v1的顏色。 ?.對(duì)調(diào)v2,v4兩個(gè)結(jié)點(diǎn)的顏色后，給著v2的顏色。 ?,自從四色猜想提出后，一百多年來(lái)，一直成為數(shù)學(xué)上的著名難題，它

11、吸引許許多多的人，為之而作出大量辛勞，也得到很多重要結(jié)果，但長(zhǎng)久未能得到解決。直到1976年6月，由美國(guó)伊利諾斯大學(xué)兩名數(shù)學(xué)家愛(ài)普爾(K.I.Apple)、黑肯(W.Haken)在考西(J.Koch)幫助下借助于電子計(jì)算機(jī)，用了一百多億次邏輯判斷，花了1200多機(jī)時(shí)才證明四色猜想是成立的，從此宣告，四色猜想成為四色定理。,相應(yīng)地有下面的定理。9、定理：對(duì)于任何地圖M，M是四著色的，即χ(M)≤4。,8、四色定理：平面圖的色數(shù)不超過(guò)4

12、。,作業(yè),P321： （1）（4）,7-7 樹(shù),樹(shù)是圖論中重要的概念之一，它在計(jì)算機(jī)科學(xué)中應(yīng)用非常廣泛，這里將介紹樹(shù)的一些基本性質(zhì)和應(yīng)用。,一、樹(shù)的概念1、定義7-7.1：一個(gè)連通且無(wú)回路的無(wú)向圖稱(chēng)為樹(shù)（tree） 。樹(shù)中度數(shù)為1的結(jié)點(diǎn)稱(chēng)為樹(shù)葉（leave）。度數(shù)大于1的結(jié)點(diǎn)稱(chēng)為分支點(diǎn)（branched node）或內(nèi)點(diǎn)。每個(gè)連通分支是樹(shù)的無(wú)向圖稱(chēng)為森林。平凡圖也是樹(shù)，稱(chēng)為平凡樹(shù)。,,,,,,,,,,,,,,,,,,2、定理7

13、-7.1：給定圖T=，以下關(guān)于樹(shù)的定義是等價(jià)的。(1)無(wú)回路的連通圖(2)無(wú)回路且e=v-1(3)連通且e=v-1(4)無(wú)回路，但增加一邊后得到且僅得一個(gè)回路(5)連通，但刪去任一邊后就不連通(6)每一對(duì)結(jié)點(diǎn)間有且僅有一條通路。,? 證明思路：6個(gè)命題可以循環(huán)推出。即(1)?(2)?(3)?(4)?(5)?(6)?(1) ?,3、定理7-7.2：任一棵樹(shù)中至少存在兩個(gè)葉。,證明： 因T連通則?u∈T，d

14、eg(u)≥1。設(shè)T有k個(gè)一度點(diǎn)，其它點(diǎn)均大于等于2，則 2e=∑deg(vi)≥k+2(v-k)=2v-k。 因e=v-1， 故2(v-1)≥2v-k，則k≥2。,二、生成樹(shù) 有一些圖，本身不是樹(shù)，但它的子圖卻是樹(shù)，一個(gè)圖可能有許多子圖是樹(shù)，其中很重要的一類(lèi)是生成樹(shù)。1、生成樹(shù) 定義7-7.2：若G的生成子圖是一棵樹(shù)，則稱(chēng)這棵樹(shù)為G的生成樹(shù)。 設(shè)G的

15、一棵生成樹(shù)為T(mén)，則T中的邊稱(chēng)為樹(shù)枝，在G中而不在T中的邊稱(chēng)弦，所有弦的集合稱(chēng)為生成樹(shù)T的補(bǔ)。,e1、e7、e5、e8、e3是T的樹(shù)枝， e2、e4、e6是T的弦，{e2、e4、e6}是T的補(bǔ)。,2、定理7-7.3：連通圖至少有一棵生成樹(shù)。,證明：如果連通圖G無(wú)回路，則G本身就是它的生成樹(shù)。如果G有回路，則在回路上任取去掉一條邊，得到圖G1仍是連通的，如G1仍有回路，重復(fù)上述步驟，直到圖Gi中無(wú)回路為止，此時(shí)該圖就是G的一棵生成樹(shù)。,由定

16、理的證明過(guò)程可以看出，一個(gè)連通圖可以有許多生成樹(shù)。因?yàn)樵谌《ㄒ粋€(gè)回路后，就可以從中去掉任一條邊，去掉的邊不一樣，故可能得到不同的生成樹(shù)。一般如果G有v個(gè)點(diǎn)e條邊連通，則e≥v-1，則G刪除e-(v-1)條邊，破壞了e-(v-1)個(gè)回路，必成G的一棵生成樹(shù)，這是”破圈法”。也可以從e條邊中選取v-1條邊并使它不含有回路，這是”避圈法”。,3、定理7-7.4：一條回路和任何一棵生成樹(shù)的補(bǔ)至少有一條公共邊。,證明：若有一條回路和一棵生成樹(shù)

17、的補(bǔ)沒(méi)有公共邊，那么這回路包含在生成樹(shù)中，然而這是不可能的，因?yàn)橐豢蒙蓸?shù)不能包含回路。,4、定理7-7.5：一個(gè)邊割集和任何生成樹(shù)至少有一條公共邊。,證明：若有一個(gè)邊割集和一棵生成樹(shù)沒(méi)有公共邊，那么刪去這個(gè)邊割集后，所得子圖必包含該生成樹(shù)，這意味著刪去邊割集后仍是連通圖，與邊割集定義矛盾。,5、最小生成樹(shù) 設(shè)G=是一連通圖，G的每一條邊e有權(quán)C(e)，G的生成樹(shù)T的權(quán)w(T)就是T的邊的權(quán)和。 定義7-7.

18、3：在圖G所有生成樹(shù)中，樹(shù)權(quán)最小的那棵樹(shù)稱(chēng)為G的最小生成樹(shù)。,構(gòu)造圖的一棵最小生成樹(shù)，即：在 e 條帶權(quán)的邊中選取 n-1 條邊（不構(gòu)成回路），使“權(quán)值之和”為最小。,該問(wèn)題等價(jià)于：,具體做法: 先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)的子圖 SG，然后從權(quán)值最小的邊開(kāi)始，若它的添加不使SG 中產(chǎn)生回路，則在 SG 上加上這條邊，如此重復(fù)，直至加上 n-1 條邊為止。,考慮問(wèn)題的出發(fā)點(diǎn): 為使生成樹(shù)上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹(shù)中每一條邊的權(quán)值

19、盡可能的小。,克魯斯卡爾算法的基本思想：,a,b,c,d,e,g,f,,,,,,,,,,,,19,5,14,18,27,16,8,21,3,a,,e,,12,d,,c,,b,,g,,f,7,14,8,5,3,16,21,例如:,,,,,7,12,18,19,求最小生成樹(shù)的克魯斯卡爾(Kruskal)算法(避圈法)：a)在G中選取最小權(quán)的邊，記作e1，置i=1。b)當(dāng)i=n-1時(shí)結(jié)束，否則轉(zhuǎn)c)。c)設(shè)已選擇邊為e1，e2，……ei

20、，此時(shí)無(wú)回路。在G中選取不同于這i條邊的邊ei+1，該邊使得{e1，…，ei+1}生成的子圖中無(wú)回路，并ei+1是滿(mǎn)足該條件中權(quán)最小的一條邊。d)置i：=i+1，轉(zhuǎn)b)。,定理7-7.6：克魯斯卡爾(Kruskal)算法產(chǎn)生的是最小生成樹(shù)。,作業(yè),327頁(yè)（6）,(b)的最小生成樹(shù)有5棵，最小生成樹(shù)的樹(shù)權(quán)為11。,(a)的最小生成樹(shù)：,7-8 根樹(shù)及其應(yīng)用,一、根樹(shù)1、有向樹(shù)定義7-8.1 如果一個(gè)有向圖在不考慮邊的方向時(shí)是

21、一棵樹(shù)，那么，該有向圖稱(chēng)為 有向樹(shù)。,2、根樹(shù) 定義7-8.2 一棵有向樹(shù),如果恰有一個(gè)結(jié)點(diǎn)的入度為0，其余所有結(jié)點(diǎn)的入度都為1,則稱(chēng)為根樹(shù)(rooted tree)。入度為0的結(jié)點(diǎn)稱(chēng)為T(mén)的樹(shù)根。出度為0的結(jié)點(diǎn)稱(chēng)為樹(shù)葉。出度不為0的結(jié)點(diǎn)稱(chēng)為分支點(diǎn)或內(nèi)點(diǎn)。,根樹(shù)的畫(huà)法有：樹(shù)根在下，向上生長(zhǎng)； 樹(shù)根在上，向下生長(zhǎng)。,習(xí)慣把有向樹(shù)的根畫(huà)在最上方，

22、邊的箭頭全指向下，則可以省略全部箭頭，樹(shù)根到一個(gè)結(jié)點(diǎn)的有向通路的長(zhǎng)度稱(chēng)為該點(diǎn)的層數(shù)。所有結(jié)點(diǎn)的最大層數(shù)稱(chēng)為樹(shù)高。,3、子樹(shù) 定義7-8.3：任一結(jié)點(diǎn)v及其后代導(dǎo)出的子圖稱(chēng)為根樹(shù)的子樹(shù)。,定義7-8.3 根樹(shù)包含一個(gè)或多個(gè)結(jié)點(diǎn),這些結(jié)點(diǎn)中的某一個(gè)稱(chēng)為根,其他所有結(jié)點(diǎn)被分成有限個(gè)子根樹(shù)。,在有向樹(shù)中，結(jié)點(diǎn)的出現(xiàn)次序是沒(méi)有意義的。但實(shí)際應(yīng)用中，有時(shí)要給出同一級(jí)中結(jié)點(diǎn)的相對(duì)次序，這便導(dǎo)出有序樹(shù)的概念。4、有序數(shù)：在根樹(shù)中

23、規(guī)定了每一層上結(jié)點(diǎn)的次序，稱(chēng)為有序樹(shù)。,為表示結(jié)點(diǎn)間的關(guān)系，有時(shí)借用家族中的術(shù)語(yǔ)。 定義 在以v0為根的樹(shù)中， （1）v1，v2,…，vk稱(chēng)為v0的 兒子，v0稱(chēng)為它們的父親。vi，vj 同為一頂點(diǎn)v的兒子時(shí)，稱(chēng)它們?yōu)樾值堋?（2）頂點(diǎn)間的父子關(guān)系的傳遞閉包稱(chēng)為頂點(diǎn)間的祖孫關(guān)系。即當(dāng)vi為vi+1 (i = 1, 2,…, l-1) 的父親時(shí)，v1是vl的祖先，vl為v1的子孫。 （3）根樹(shù)T自身

24、及以它的樹(shù)根的子孫為根的根樹(shù)（T的子圖），均稱(chēng)為T(mén)的子樹(shù)（subtree），后者又 稱(chēng)為T(mén)的真子樹(shù)。,5、m叉樹(shù) 定義7-8.4：在根樹(shù)中,若每個(gè)結(jié)點(diǎn)的出度均≤m，則稱(chēng)T為m元樹(shù)(m叉樹(shù))，若每個(gè)分支點(diǎn)的出度恰好等于m，則稱(chēng)T為m叉完全樹(shù)，若T的所有樹(shù)葉的層數(shù)均相同，則稱(chēng)T正則m元樹(shù)。若m元樹(shù)是有序的，則稱(chēng)T為m元有序樹(shù)，若m元完全樹(shù)是有序的則稱(chēng)T為完全m元有序樹(shù)，若m元正則樹(shù)是有序的，則稱(chēng)T為m元正則有序樹(shù)。

25、當(dāng)m=2時(shí)，稱(chēng)為二元樹(shù)，二元有序樹(shù)的每個(gè)結(jié)點(diǎn)至多有兩個(gè)兒子，其序按左右分，分別為左兒子，右兒子，任一分支點(diǎn)最多有兩棵子樹(shù)，稱(chēng)為左子樹(shù)和右子樹(shù)。,當(dāng)m=2時(shí)，便可得到常用的二叉樹(shù)、完全二叉樹(shù)和正則二叉樹(shù)。不難看出，二叉樹(shù)中的每個(gè)結(jié)點(diǎn)v，至多有兩個(gè)子樹(shù)，分別稱(chēng)為v的左子樹(shù)和右子樹(shù)。若v只有一個(gè)子樹(shù)，則稱(chēng)它為左子樹(shù)或右子樹(shù)均可。在二叉樹(shù)的圖形表示中，v的左子樹(shù)畫(huà)在v的左下方，v的右子樹(shù)畫(huà)在v的右下方。,6.定理7-8.1 設(shè)有完全

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

27、-8.2 設(shè)有完全二叉樹(shù)有n個(gè)分支點(diǎn)，且內(nèi)部通路長(zhǎng)度為總和為I ，外部通路長(zhǎng)度總和為E ，則 E=I+2n。,已知w1，w2，…，wn為權(quán)，T0為加權(quán)二叉樹(shù)，其權(quán)為w(T0)，如果對(duì)任意加權(quán)二叉樹(shù)T，它的權(quán)是w(T)，均有w(T0)≥w(T)，則稱(chēng)T0是最優(yōu)樹(shù)或Huffman樹(shù)。,9.定義7-8.6 在帶權(quán)二叉樹(shù)T中，若帶權(quán)為wi樹(shù)葉，其通路長(zhǎng)度為L(zhǎng)(wi) ,把

28、 t w(T) = ? wi L(wi) i=1 稱(chēng)為該帶權(quán)二叉樹(shù)權(quán)，所有帶權(quán)w1, w2,…, wt的二叉樹(shù)樹(shù)中， w(T)最小的那棵樹(shù)，稱(chēng)為最優(yōu)樹(shù)。,離散數(shù)學(xué)總復(fù)習(xí),曾慶田Email：qtzeng@163.com2008年.12月,第一章

29、 命題邏輯,第二章 謂詞邏輯,第四章 函數(shù),第六章 格和布爾代數(shù),第七章 圖論,第一篇 數(shù)理邏輯,第二篇 集合論,第三章 集合與關(guān)系,第四篇 圖 論,教學(xué)內(nèi)容：數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)與布爾代數(shù)和圖論共四部分。,第五章 代數(shù)結(jié)構(gòu),第三篇 代數(shù)系統(tǒng),第一章 命題邏輯 一、知識(shí)點(diǎn)1．命題的概念、表示方法；聯(lián)結(jié)詞的邏輯意義。2．命題公式的遞歸定義，自然語(yǔ)言翻譯成命題公式3．真值表的構(gòu)造、命題公式

30、等價(jià)的概念。4．重言式與蘊(yùn)涵式的定義、邏輯意義，邏輯等價(jià)與邏輯蘊(yùn)涵的意義和證明方法。常用的邏輯等價(jià)公式和邏輯蘊(yùn)涵公式。,5．命題公式的對(duì)偶式、合取范式、析取范式、主合取范式、主析取范式。邏輯小項(xiàng)、邏輯大項(xiàng)。任給公式化為析取范式、任給公式化為主析取范式、任給公式化為合取范式、任給公式化為主合取范式。 6．命題邏輯的推理理論，主要的推理方法：真值表法、直接證明法、間接證明法。常用推理規(guī)則：P規(guī)則、T規(guī)則、CP規(guī)則。,重點(diǎn),命題符號(hào)化

31、主析（合）取范式求取方法命題邏輯推理,第2章 謂詞邏輯,一、知識(shí)點(diǎn)1.謂詞的概念與表示方法2.命題函數(shù)與量詞3.謂詞邏輯的合式公式與自然語(yǔ)言的翻譯4.謂詞中變?cè)s束5.謂詞邏輯的等價(jià)式和蘊(yùn)含式6.前束范式7.推理理論,謂詞邏輯的推理方法,規(guī)則：P、T規(guī)則；US、UG、ES、EG規(guī)則公式表：命題邏輯的等價(jià)式、蘊(yùn)含式；謂詞邏輯的常用等價(jià)式和蘊(yùn)含式；推理方法：直接證明方法間接證明方法反證法CP規(guī)則,重點(diǎn)

32、,謂詞邏輯推理方法,一、知識(shí)點(diǎn)1．集合的基本概念與表示方法；2．集合的運(yùn)算:并、交、對(duì)稱(chēng)差、冪集、劃分、覆蓋；3．序偶與笛卡爾積；4．關(guān)系及其表示、關(guān)系矩陣、關(guān)系圖；5．關(guān)系的性質(zhì)，復(fù)合關(guān)系、逆關(guān)系；6．關(guān)系的閉包運(yùn)算：t(R),r(R),s(R),tr(R)；,第三章 集合與關(guān)系,7．集合的劃分與覆蓋、等價(jià)關(guān)系與等價(jià)類(lèi)；相容關(guān)系；細(xì)分；8．序關(guān)系、偏序集、哈斯圖。9. 偏序集中特殊的元素極小元、極大元最小元、最大

33、元上界、下界上確界、下確界,第三章集合與關(guān)系,重點(diǎn),關(guān)系的三種閉包求取方法關(guān)系的性質(zhì)證明,一、知識(shí)點(diǎn)1．函數(shù)的概念，定義域、值域、定義域與前域的關(guān)系、值域與陪域的關(guān)系，入射函數(shù)、滿(mǎn)射函數(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),運(yùn)算的性質(zhì)：封閉性、結(jié)合性、分配性、交換性；特殊的元素：幺元、零元、逆元、等冪元的識(shí)別主要的代數(shù)系統(tǒng)：廣群

34、、半群、獨(dú)異點(diǎn)、群、子群；代數(shù)系統(tǒng)之間的關(guān)系；交換群和循環(huán)群；陪集、拉格朗日定理；同態(tài)映射、同構(gòu)映射；環(huán)、同態(tài)象、域,重點(diǎn),半群、含幺半群、群、Abel群的運(yùn)算性質(zhì)半群、含幺半群、群、Abel群的證明方法,第6章 格與布爾代數(shù),一、知識(shí)點(diǎn)格的概念，偏序集上的并運(yùn)算、偏序集上的交運(yùn)算。模格、分配格、有補(bǔ)格；布爾代數(shù)、Stone表示定理及其推論。,重點(diǎn),布爾代數(shù)的性質(zhì)布爾代數(shù)的原子布爾代數(shù)的證明,第七章 圖論,1．圖的基

35、本概念、結(jié)點(diǎn)度數(shù)與邊數(shù)的關(guān)系公式；2. 路徑、擬路徑、回路、通路、連通圖與非連通圖、強(qiáng)連通圖與弱連通圖、有向圖與無(wú)向圖；強(qiáng)分圖、點(diǎn)割集、邊割集；3. 圖的矩陣表示：鄰接矩陣、可達(dá)性矩陣、關(guān)聯(lián)矩陣、關(guān)聯(lián)矩陣的秩與結(jié)點(diǎn)數(shù)的關(guān)系式。,第七章 圖論,4. 歐拉路、歐拉回路、歐拉圖；哈密爾頓路、哈密爾頓回路、哈密爾頓圖；5. 平面圖、歐拉定理、平面圖中結(jié)點(diǎn)數(shù)和邊數(shù)之間的關(guān)系不等式；Kuratowski定理；6. 對(duì)偶圖、平面圖的著色問(wèn)題。

36、7. 樹(shù)、生成樹(shù)、帶權(quán)樹(shù)、最小生成子樹(shù)；8. 根樹(shù)、完全m叉樹(shù)、二叉樹(shù)、完全二叉樹(shù)中分支點(diǎn)和通路長(zhǎng)度之間的關(guān)系式。,重點(diǎn),連通圖（證明）歐拉圖（一筆畫(huà)）、哈密爾頓圖的判斷方法平面圖（歐拉公式）,考試說(shuō)明(A卷),第一章25分（命題符號(hào)化、主析/合取范式、命題邏輯證明）第二章10分（謂詞邏輯證明）第三章10分（關(guān)系）第四章0分第五章15分（群、Abel群的證明）第六章15分（布爾代數(shù)的原子）第七章25分（

37、連通圖、平面圖）,考試說(shuō)明(B卷),第一章25分（命題符號(hào)化、主析/合取范式、命題邏輯證明）第二章10分（謂詞邏輯證明）第三章10分（關(guān)系）第四章0分第五章15分（半群、群的運(yùn)算性質(zhì)）第六章15分（布爾代數(shù)的原子）第七章25分（平面圖、歐拉圖（一筆畫(huà)）、哈密爾頓圖的判斷方法）,題目來(lái)源,《離散數(shù)學(xué)》課本部分課后習(xí)題小部分作業(yè)題目小部分例題、定理,考試時(shí)間、地點(diǎn),時(shí)間：2009年1月8日（星期四）下午2：3