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

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

Fn的連通平面圖G=<V,E>實(shí)施下列步驟所得到的圖G*稱(chēng)為圖G的對(duì)偶圖（dualofgraph）：如果存在一個(gè)圖G*=<V*，E*>滿(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*,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í)線邊圖為平面圖，虛線邊圖為其對(duì)偶圖。v*=r，e*=e，r*=v2、自對(duì)偶圖定義7-6.2

如果圖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ì)于平面圖的結(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種顏色可以著色該圖，其次證明用少于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)的著色數(shù)不能少于n，又n個(gè)結(jié)點(diǎn)的著色數(shù)至多為n，故χ(Kn)=n。6、定理7-6.2：連通平面圖G=<V，E>至少有三個(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

則有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ù)歸納假設(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é)上的著名難題，它吸引許許多多的人，為之而作出大量辛勞，也得到很多重要結(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。作業(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)（branchednode）或內(nèi)點(diǎn)。每個(gè)連通分支是樹(shù)的無(wú)向圖稱(chēng)為森林。平凡圖也是樹(shù)，稱(chēng)為平凡樹(shù)。2、定理7-7.1：給定圖T=<V，E>，以下關(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，deg(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的一棵生成樹(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ù)。由定理的證明過(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ù)的補(bǔ)沒(méi)有公共邊，那么這回路包含在生成樹(shù)中，然而這是不可能的，因?yàn)橐豢蒙蓸?shù)不能包含回路。4、定理7-7.5：一個(gè)邊割集和任何生成樹(shù)至少有一條公共邊。證明：若有一個(gè)邊割集和一棵生成樹(shù)沒(méi)有公共邊，那么刪去這個(gè)邊割集后，所得子圖必包含該生成樹(shù)，這意味著刪去邊割集后仍是連通圖，與邊割集定義矛盾。5、最小生成樹(shù)設(shè)G=<V，E>是一連通圖，G的每一條邊e有權(quán)C(e)，G的生成樹(shù)T的權(quán)w(T)就是T的邊的權(quán)和。定義7-7.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)值盡可能的小?？唆斔箍査惴ǖ幕舅枷耄篴bcdegf195141827168213ae12dcbgf7148531621例如:7121819求最小生成樹(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，此時(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í)是一棵樹(shù)，那么，該有向圖稱(chēng)為有向樹(shù)。2、根樹(shù)

定義7-8.2

一棵有向樹(shù),如果恰有一個(gè)結(jié)點(diǎn)的入度為0，其余所有結(jié)點(diǎn)的入度都為1,則稱(chēng)為根樹(shù)(rootedtree)。入度為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à)在最上方，邊的箭頭全指向下，則可以省略全部箭頭，樹(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ù)中規(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)樾值?。?）頂點(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自身及以它的樹(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ù)。當(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è)有完全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-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),把

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月第一章

命題邏輯第二章

謂詞邏輯第四章函數(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)造、命題公式等價(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)化主析（合）取范式求取方法命題邏輯推理第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)謂詞邏輯推理方法

一、知識(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.偏序集中特殊的元素極小元、極大元最小元、最大元上界、下界上確界、下確界第三章集合與關(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)：廣群、半群、獨(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)格的概念，偏序