《離散數(shù)學(xué)》總復(fù)習(xí)

《離散數(shù)學(xué)》總復(fù)習(xí)黃玉yuhua2k@163.com南航計(jì)算機(jī)學(xué)院A12-1161.主范式、集合、布爾格(有補(bǔ)分配格)運(yùn)算2.命題符號(hào)化+命題/謂詞邏輯推理3.前束范式4.元素與集合、集合與集合的關(guān)系(判斷,證明)5.排列組合、容斥原理、遞推方程6.關(guān)系合成、函數(shù)復(fù)合、置換乘法7.等價(jià)關(guān)系(等價(jià)類、商集、劃分、自然映射)8.偏序集(偏序關(guān)系、覆蓋、哈斯圖)、格9.同構(gòu)=同態(tài)∩雙射10.代數(shù)系統(tǒng)及其性質(zhì)(判斷)11.域=整環(huán)∩除環(huán)0.重要概念:冪集,笛卡積,閉包,積代數(shù),循環(huán)群;0.重要概念:生成子圖,自補(bǔ)圖,自對(duì)偶圖,割集12.握手定理13.鄰接矩陣14.最短路徑(標(biāo)號(hào)法)與關(guān)鍵路徑(最長路徑)15.圖的類型(二部,歐拉,哈密頓,平面,樹)判別16.平面圖歐拉公式：n

m+r=217.樹的重要性質(zhì)：m=n-118.最小生成樹(避圈法)、基本回路/割集系統(tǒng)19.Huffman算法(最優(yōu)二元樹/最佳前綴碼)20.二/多項(xiàng)式定理與組合恒等式21.分治算法的常用遞推公式第1章命題邏輯1.1命題符號(hào)化及聯(lián)結(jié)詞（聯(lián)結(jié)詞是基礎(chǔ)）1.2命題公式及分類1.3等值演算1.4聯(lián)結(jié)詞全功能集1.5對(duì)偶與范式（主范式演算是重點(diǎn)）1.6推理理論（重點(diǎn)）聯(lián)結(jié)詞與復(fù)合命題(小結(jié))聯(lián)結(jié)詞優(yōu)先級(jí):(),

,

,

,

,

同級(jí)按從左到右的順序進(jìn)行

pq

pp∧qp∨qp

qp

q0010011011011010001001101111基本復(fù)合命題的真值1.3命題邏輯等值演算等值式定義：(A

B1)(A

B)（重點(diǎn)）基本等值式(重點(diǎn)) 雙重否定律

:

A

A等冪律：

A

A

A,A

A

A交換律:A

B

B

A,A

B

B

A結(jié)合律:(A

B)

C

A

(B

C)(A

B)

C

A

(B

C)分配律:A

(B

C)

(A

B)

(A

C)

A

(B

C)

(A

B)

(A

C)德·摩根律:

(A

B)

A

B

(A

B)

A

B基本等值式（續(xù)）吸收律:A

(A

B)

A,A

(A

B)

A零律:A

1

1,A

0

0同一律:A

0

A,

A

1

A排中律:A

A

1矛盾律:A

A

0蘊(yùn)涵等值式:A

B

A

B等價(jià)等值式:A

B

(A

B)

(B

A)假言易位:A

B

B

A等價(jià)否定等值式:A

B

A

B歸謬論:(A

B)

(A

B)

A1.4復(fù)合聯(lián)結(jié)詞（重要的非重點(diǎn)）與非式:p

q(p

q)；或非式:p

q(p

q)習(xí)題1.14，1.10(4)(5)異或：p

q

p

q

(p

q)

p

q

p

qA

p1

p2

…

pn,偶數(shù)個(gè)命題變項(xiàng)賦值為1T(A0),奇數(shù)個(gè)命題變項(xiàng)賦值為1T(A1);B

q1

q2

…

qn,偶數(shù)個(gè)命題變項(xiàng)賦值為0T(A1),奇數(shù)個(gè)命題變項(xiàng)賦值為0T(A0).習(xí)題1.221.5主范式（重點(diǎn)）成真賦值i對(duì)應(yīng)主析取范式的極小項(xiàng)mi；成假賦值j對(duì)應(yīng)主合取范式的極大項(xiàng)Mj。命題公式有幾個(gè)成真賦值，主析取范式就是幾個(gè)極小項(xiàng)相或(

)；命題公式有幾個(gè)成假賦值，主合取范式就是幾個(gè)極大項(xiàng)相與(

)。例1.31，1.32分配律Bj

Bj

(pi

pi)(Bj

pi)(Bj

pi)Bj

Bj

(pi

pi)(Bj

pi)(Bj

pi)習(xí)題1.12(1),1.13(1)。五71.6

命題邏輯推理（重點(diǎn)）“推理正確”定義：(A?B1)(ATB)（重點(diǎn)）A

T(AúB) 附加律(AùB)T

A

化簡律(A?B)ùA

T

B

假言推理(A?B)ù?B

T

?A

拒取式(AúB)ù?B

T

A

析取三段論(A?B)ù(B?C)T(A?C) 假言三段論(A?B)ù(B?C)T(A?C) 等價(jià)三段論(A?B)ù(C?D)ù(AúC)T(BúD) 構(gòu)造性二難(A?B)ù(?A?B)ù(Aú?A)T

B

構(gòu)造性二難(特殊形式)(A?B)ù(C?D)ù(?Bú?D)T(?Aú?C)破壞性二難習(xí)題1.18,1.21,1.17(2)。六1注意事項(xiàng)1：命題只有能確定真假(但不能可真可假)的陳述句才是命題.不管是正確的觀點(diǎn),還是錯(cuò)誤的觀點(diǎn),都是命題.猜想和預(yù)言是命題,如哥德巴赫猜想.感嘆句,祈使句,疑問句都不是命題.陳述句中的悖論以及判斷結(jié)果不惟一確定的也不是命題.有些簡單命題貌似復(fù)合命題,要注意區(qū)分.題1(15)注意事項(xiàng)2：蘊(yùn)涵聯(lián)結(jié)詞“

”p

q的邏輯關(guān)系:p為q的充分條件，q為p的必要條件.“如果p,則q”的多種表述方式：(1)若p,就q.(2)只要p,就q.(3)p僅當(dāng)q.(4)只有q

才p.(5)除非q,才p.(6)除非q,否則非p.p

q為假當(dāng)且僅當(dāng)p為真q為假，即當(dāng)p為假時(shí)，p

q為真(不管q為真,還是為假);當(dāng)q為真時(shí)，p

q為真(不管p為真,還是為假).習(xí)題1.5(6)(7)了解概念、掌握方法真值表、命題公式類型所有等值的含n個(gè)命題變項(xiàng)的公式對(duì)應(yīng)同一個(gè)n元真值函數(shù)F:{0,1}n

{0,1}；啞元最小聯(lián)結(jié)詞組對(duì)偶式與對(duì)偶原理簡單析取式、簡單合取式析取范式與合取范式附加前提證明法、反證法第2章一階邏輯2.1 一階邏輯基本概念（量詞是關(guān)鍵）2.2 一階邏輯公式、解釋及分類2.3 一階邏輯等值式、前束范式（重點(diǎn)）2.4 一階邏輯推理理論（重點(diǎn)）一階邏輯與命題邏輯關(guān)系一階邏輯將命題(公式)拆分為個(gè)體詞、謂詞、量詞(

、)。謂詞是核心，沒有謂詞，不構(gòu)成命題；量詞是關(guān)鍵。個(gè)體詞（元素）分為個(gè)體常項(xiàng)和個(gè)體變項(xiàng).個(gè)體域（集合）:個(gè)體變項(xiàng)的取值范圍.

全總個(gè)體域:宇宙間一切事物組成一階邏輯≈命題邏輯+量詞

xF(x)

x

F(x),

xF(x)

x

F(x);

xF(x)

x

F(x),

xF(x)

x

F(x)2.3一階邏輯等值式基本等值式（重點(diǎn)）

:命題邏輯中16組基本等值式的代換實(shí)例消去量詞等值式設(shè)D={a1,a2,…,an}

xA(x)

A(a1)

A(a2)

…

A(an)

xA(x)

A(a1)

A(a2)

…

A(an)量詞轄域收縮與擴(kuò)張等值式

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(B

A(x))

B

xA(x)量詞分配等值式

x(A(x)

B(x))

xA(x)

xB(x)

x(A(x)

B(x))

xA(x)

xB(x)

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(B

A(x))

B

xA(x)注意事項(xiàng)1：前束范式（重點(diǎn)）設(shè)A為一個(gè)一階邏輯公式,若A具有如下形式

Q1x1Q2x2…QkxkB,則稱A為前束范式,其中Qi(1

i

k)為

或

，B為不含量詞的公式.1）對(duì)

無分配律，

對(duì)

無分配律

xA(x)

xB(x)

x

y(A(x)

B(y))

x

y(A(x)

B(y))

xA(x)

xB(x)2）變量沖突，有一個(gè)要換名.3）x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B習(xí)題2.21,2.15(1),2.14(1)。四102.4一階邏輯推理理論（重點(diǎn)）重要的推理定律第一組命題邏輯推理定律代換實(shí)例第二組由基本等值式生成（置換規(guī)則）第三組

xA(x)

xB(x)

x(A(x)

B(x))

x(A(x)

B(x))

xA(x)

xB(x)(12)

全稱量詞消去規(guī)則（簡記為UI規(guī)則或UI）(13)

全稱量詞引入規(guī)則（簡記為UG規(guī)則或UG）(14)存在量詞引入規(guī)則（簡記為EG規(guī)則或EG）(15)存在量詞消去規(guī)則（簡記為EI規(guī)則或EI）注:必須先消去存在量詞,后消去全稱量詞.七1第三版:習(xí)題2.22,2.16,2.19,2.17(1),2.23；例2.18注意事項(xiàng)2：一階邏輯中命題符號(hào)化無特別要求，用全總個(gè)體域量詞順序一般不要隨便顛倒

x

yA(x,y)

y

xA(x,y)全稱量詞一般對(duì)應(yīng)“”存在量詞一般對(duì)應(yīng)“”習(xí)題2.3(2)(5)(6)了解有限個(gè)體域,無限個(gè)體域;謂詞常項(xiàng),謂詞變項(xiàng),一元謂詞,多元謂詞(n元謂詞,n

2),0元謂詞,原子公式;項(xiàng)字母表包含：1)個(gè)體常項(xiàng),2)個(gè)體變項(xiàng),3)函數(shù)符號(hào),4)謂詞符號(hào),5)量詞符號(hào)(

,),6)聯(lián)結(jié)詞符號(hào)(

,

,

,

,),7)括號(hào)與逗號(hào).指導(dǎo)變元，轄域，約束出現(xiàn)，自由出現(xiàn)閉式:不含自由出現(xiàn)的個(gè)體變項(xiàng)的公式.解釋I包含：(a)非空個(gè)體域DI,(b)DI中一些特定元素集,(c)DI上特定函數(shù)集,(d)DI上特定謂詞集.閉式在任何解釋下都是命題，不是閉式的公式在某些解釋下也可能是命題.公式類型.換名規(guī)則與代替規(guī)則第3章集合的基本概念和運(yùn)算3.1集合的基本概念3.2集合的基本運(yùn)算（重點(diǎn)）3.3集合中元素的計(jì)數(shù)（容斥原理是重點(diǎn)）3.1集合的基本概念元素x與集合A的關(guān)系：屬于x

A，不屬于x

A集合A與集合B的關(guān)系：習(xí)題3.2,3.8,3.12,3.16

包含(子集)A

B,不包含A?B

相等A=B,不相等A

B

真包含A

B,

不真包含A

B重要概念：集合A的冪集P(A)={x|x

A}。如果|A|=n，則|P(A)|=2n.習(xí)題3.14(4),3.18習(xí)題3.3,3.9,3.113.2集合的基本運(yùn)算（重點(diǎn)）集合運(yùn)算符，，，分別對(duì)應(yīng) 聯(lián)結(jié)詞∧,∨，，A

B=A

B=A

(A

B)A

B=(A

B)

(B

A)=(A

B)(A

B)

A

B

A

A

BA

B

A

B=B

A

B=A

A

B=

A

B=

A

B=A習(xí)題3.17,3.16；例3.17，3.18。四3，4；六4集合運(yùn)算的文氏圖表示習(xí)題3.4,3.15(2)集合運(yùn)算的算律（重點(diǎn)）

交換A

B=B

AA

B=B

AA

B=B

A結(jié)合(A

B)C=A

(B

C)(A

B)C=A

(B

C)(A

B)C=A

(B

C)冪等A

A=AA

A=A

與

與

分配A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)吸收A

(A

B)=AA

(A

B)=A吸收律的前提：、可交換集合運(yùn)算的算律（續(xù)）

D.M律A

(B

C)=(A

B)(A

C)A

(B

C)=(A

B)(A

C)

(B

C)=B

C

(B

C)=B

C雙重否定

A=A

E補(bǔ)元律A

A=A

A=E零律A

=

A

E=E同一律A

=AA

E=A否定

=E

E=3.3集合中元素的計(jì)數(shù)容斥原理及其推論（重點(diǎn)）習(xí)題3.6,3.18,3.19。五10注意1）0是自然數(shù).2）對(duì)于任何集合A和元素x(可以是集合)，

x

A和x

A兩者成立其一，且僅成立其一.3）和

是不同層次的問題.4）空集是任何集合的子集.5）在給定問題中，全集E包含任何集合，即

A(A

E)了解概念、掌握方法1）集合的表示法：列元素法A={a,b,c,d}謂詞表示法B={x|P(x)}.習(xí)題3.10(4)2）文氏圖與文氏圖法.習(xí)題3.63）集合A的基數(shù)cardA=|A|=n4）證明

X

Y命題演算法包含傳遞法等價(jià)條件法反證法并交運(yùn)算法5）證明X=Y命題演算法等式代入法反證法運(yùn)算法第4章二元關(guān)系與函數(shù)4.1集合的笛卡兒積與二元關(guān)系4.2關(guān)系的運(yùn)算（重點(diǎn)）4.3關(guān)系的性質(zhì)（基礎(chǔ)）4.4關(guān)系的閉包4.5等價(jià)關(guān)系和偏序關(guān)系（重點(diǎn)）4.6函數(shù)的定義和性質(zhì)4.7函數(shù)的復(fù)合和反函數(shù)4.1集合的笛卡兒積和二元關(guān)系1）重要概念：集合A與B的笛卡兒積A

B={<x,y>|x

A

y

B}.若|A|=m,|B|=n,則|A

B|=mn分配律A

(B

C)=(A

B)

(A

C)(B

C)

A=(B

A)

(C

A)

A

(B

C)=(A

B)

(A

C)(B

C)

A=(B

A)

(C

A)A

=

B=

(A

C=B

D)(A,B,C,D非空)(A=B)

(C=D)2）從A到B的二元關(guān)系R

A

B.A×B的子集有2mn個(gè)，所以A到B有2mn個(gè)不同的二元關(guān)系.注：笛卡兒積不適合交換律和結(jié)合律.如<x,y>∈R,可記作xRy.A上重要關(guān)系從A到A的二元關(guān)系叫做A上的二元關(guān)系.空關(guān)系

是A上的關(guān)系全域關(guān)系EA={<x,y>|x∈A∧y∈A}=A×A

恒等關(guān)系IA={<x,x>|x∈A}小于等于關(guān)系LA={<x,y>|x,y∈A∧x≤y},A

R整除關(guān)系DA={<x,y>|x,y∈A∧x整除y},A

Z包含關(guān)系R

={<x,y>|x,y∈A∧x

y},A是集合族.類似的還可以定義大于等于關(guān)系,小于關(guān)系,大于關(guān)系,真包含關(guān)系等等.4.2關(guān)系的運(yùn)算逆R

1={<y,x>|<x,y>

R}合成R°S={<x,z>|

y(<x,y>

S

<y,z>

R)}(1)(F°G)°H=F°(G°H)(2)(F°G)

1=G

1°F

1.冪運(yùn)算(1)R0={<x,x>|x∈A}=IA

(2)Rn+1=Rn°R習(xí)題4.13。五14.3關(guān)系的性質(zhì)（基礎(chǔ)，重中之重）(1)若

x∈A,<x,x>

R,則稱R在A上是自反的.(2)若

x∈A,<x,x>

R,稱R在A上是反自反的.(3)若

x

y(x,y∈A∧<x,y>∈R→<y,x>∈R),則稱R為A上對(duì)稱的關(guān)系.(4)若

x,y∈A,<x,y>∈R∧<y,x>∈R→x=y,則稱R為A上的反對(duì)稱關(guān)系.(5)若

x,y,z∈A,<x,y>∈R∧<y,z>∈R→<x,z>∈R,則稱R是A上的傳遞關(guān)系.習(xí)題4.4關(guān)系性質(zhì)判別

自反反自反對(duì)稱反對(duì)稱傳遞表達(dá)式IA

RR∩IA=

R=R

1

R∩R

1

IA

R

R

R關(guān)系矩陣主對(duì)角線元素全是1主對(duì)角線元素全是0矩陣是對(duì)稱矩陣若rij＝1,且i≠j,則rji＝0對(duì)M2中1所在位置,M中相應(yīng)位置都是1關(guān)系圖每個(gè)頂點(diǎn)都有環(huán)每個(gè)頂點(diǎn)都沒有環(huán)如果兩個(gè)頂點(diǎn)之間有邊,是一對(duì)方向相反的邊(無單邊)如果兩點(diǎn)之間有邊,是一條有向邊(無雙向邊)如果頂點(diǎn)xi連通到xk,則從xi到xk有邊

恒等關(guān)系IA既是等價(jià)關(guān)系,又是篇序關(guān)系。運(yùn)算與性質(zhì)的關(guān)系（了解）自反性反自反性對(duì)稱性反對(duì)稱性傳遞性R1

1

√√√√√R1∩R2

√√√√√R1∪R2

√√√××R1

R2

×√√√×R1°R2

√××××4.5等價(jià)關(guān)系和偏序關(guān)系（重點(diǎn)）(1)等價(jià)關(guān)系、等價(jià)類、商集、劃分、自然映射等價(jià)關(guān)系:同時(shí)滿足自反、對(duì)稱和傳遞的關(guān)系.若<x,y>∈等價(jià)關(guān)系R,稱x等價(jià)于y,記做x～y.x(x∈A)關(guān)于集合A上等價(jià)關(guān)系R的等價(jià)類

[x]R

={y|y∈A∧xRy}.以集合A上的等價(jià)關(guān)系R的所有等價(jià)類為元素的集合稱為A關(guān)于R的商集,記做A/R.商集A/R就是A的一個(gè)劃分;等價(jià)關(guān)系與商集、劃分一一對(duì)應(yīng).習(xí)題4.5，4.15，4.24。五2；六14(2)偏序關(guān)系,覆蓋,偏序集與哈斯圖偏序關(guān)系：同時(shí)滿足自反、反對(duì)稱和傳遞的關(guān)系,記作?.如果<x,y>∈偏序關(guān)系?,則記作x?y.x?y且不存在z

A使得x?z?y,則稱y覆蓋x.集合A和A上的偏序關(guān)系?一起叫做偏序集,記作<A,?>.習(xí)題4.6，4.16。五3哈斯圖：簡化關(guān)系圖。特點(diǎn)（注意）：每個(gè)結(jié)點(diǎn)沒有環(huán)，位置低的元素的順序在前，具有覆蓋關(guān)系的兩個(gè)結(jié)點(diǎn)之間才連邊.特定元素：區(qū)分最小(大)元與極小(大)元；下界、上界、下確界、上確界注意事項(xiàng)：特定元素對(duì)于有窮集，極小元和極大元必存在，可能存在多個(gè).

最小元和最大元不一定存在，如果存在一定惟一.

最小元一定是極小元;最大元一定是極大元.反之不對(duì).

孤立結(jié)點(diǎn)既是極小元，也是極大元.下界、上界、下確界、上確界不一定存在.下界、上界存在不一定惟一.下確界、上確界如果存在，則惟一.集合的最小元就是它的下確界，最大元就是它的上確界；反之不對(duì).4.6函數(shù)

x∈domF都存在唯一的y∈ranF使xFy成立,則稱二元關(guān)系F為函數(shù).對(duì)于函數(shù)F,如果有xFy,則記作y=F(x),并稱y為F在x的值.所有從A到B的函數(shù)的集合記作BA,讀作“B上A”，符號(hào)化表示為BA

={f|f：A→B}函數(shù)f：A→B，domF=A，|f|=|A|，ranF

B.計(jì)數(shù)：|A|=m,|B|=n,且m,n>0,|BA|=nm.B

={

}.A≠

,則

A=

.恒等函數(shù)IA(x)=x習(xí)題4.22了解有序?qū)?lt;x,y>，有序n元組<x1,x2,…,xn>.關(guān)系矩陣、關(guān)系圖;關(guān)系的定義域、值域和域.習(xí)題4.2關(guān)系F在集合A上的限制F?A={<x,y>|xFy

x

A}

F.A在F下的像F[A]=ran(F?A)ranF.習(xí)題4.3R的自反閉包r(R)=R∪R0,對(duì)稱閉包s(R)=R∪R

1,傳遞閉包t(R)=R∪R2∪R3∪…。習(xí)題4.14Mr

=M+E，Ms

=M+M’，Mt

=M+M2+M3+…(不)可比。全序(線序)關(guān)系：所有元素可比；良序集單射,滿射,雙射；常函數(shù)、單調(diào)函數(shù)；特征函數(shù).g(a)=[a]是從A到商集A/R的自然映射.習(xí)題4.10,4.18函數(shù)復(fù)合與反函數(shù)良序集：任意非空子集都有最小元素的全序集第5章代數(shù)系統(tǒng)的一般性質(zhì)5.1二元運(yùn)算及其性質(zhì)（基礎(chǔ)）5.2代數(shù)系統(tǒng)及其子代數(shù)和積代數(shù)（重要概念積代數(shù)）5.3代數(shù)系統(tǒng)的同態(tài)與同構(gòu)（重點(diǎn)）5.1一、二元運(yùn)算,代數(shù)系統(tǒng),封閉性函數(shù)f：S×S→S稱為集合S上的二元運(yùn)算,也稱S對(duì)f

封閉;即

x,y∈S,f(x,y)∈S.函數(shù)f：S→S稱為集合S上的一元運(yùn)算;即

x∈S,f(x)∈S.函數(shù)的性質(zhì)：運(yùn)算結(jié)果唯一性.非空集合S和S上k個(gè)一元或二元運(yùn)算f1,f2,…,fk

組成的系統(tǒng)稱為一個(gè)代數(shù)系統(tǒng),簡稱代數(shù)，記做

V=<S,f1,f2,…,fk>.習(xí)題5.8，5.7二元運(yùn)算可能的性質(zhì)

x,y,z∈S

(1)交換律：

x°

y=y°x.(2)結(jié)合律：(x°

y)°

z=x°

(y°z).

(3)冪等律：

x°

x=x.(4)消去律：若x°

y=x°

z,且x不是零元,則y=z;

若y°

x=z°

x,且x不是零元，則y=z.

無零因子：(x°y=

x=

∨y=)

消去律.

(1)°

運(yùn)算對(duì)?運(yùn)算滿足分配律：

z°(x?y)=(z°

x)?(z°

y).(2)°

和?運(yùn)算滿足吸收律(前提°

和?都可交換)：

x°

(x?y)=x；x?(x°

y)=x.一些二元運(yùn)算的性質(zhì)集合運(yùn)算交換律結(jié)合律冪等律消去律Z,Q,R,C普通加法+有有無有普通乘法

有有無有Mn(R)矩陣加法+有有無有矩陣乘法

無有無無P(B){0,1}并

(或∨)有有有無交

(與∧)有有有無對(duì)稱差

(

,

)有有無有AA函數(shù)復(fù)合

無有無無Zn模乘

有有無無Z+lcm,gcd有有有無{0,1}與非

,或非有無無無一些二元運(yùn)算的性質(zhì)

集合運(yùn)算分配律吸收律Z,Q,R,CMn(R)普通加法+與乘法

矩陣加法+與乘法

對(duì)+可分配無+對(duì)

不分配P(B){0,1}并

與交(或∨和與∧)

對(duì)

可分配有

對(duì)

可分配交

與對(duì)稱差(與∧和排斥或)

對(duì)

可分配無

對(duì)

不分配Zn模加

與模乘

對(duì)

可分配無

對(duì)

不分配全集E并

與笛卡兒積

對(duì)可分配無交

與笛卡兒積

對(duì)可分配Z+lcm與gcd有有二元運(yùn)算可能的特異元素

x∈S,(e°x=x)

(x°e=x),稱e為單位元(幺元)(惟一性).

x∈S,(θ°x=θ)

(x°θ=θ),稱θ是零元(惟一性).注:只有左或右單位元(零元),不稱為有單位元(零元).(y°x=e)

(x°y=e),稱y為x的逆元,并稱x是可逆元素.注:逆元的存在以幺元的存在為前提.e-1=e.對(duì)于可結(jié)合的二元運(yùn)算,可逆元素x只有惟一的逆元,記作x

1.

習(xí)題5.14，5.15，5.3，5.12，5.2一些二元運(yùn)算的特異元素集合運(yùn)算幺元e零元θ逆元x-1(e-1=e)Z,Q,R,C普通加法+0無

x普通乘法

101/x(x≠0)Mn(R)矩陣加法+0陣無

x矩陣乘法

單位陣In0陣x

1(逆陣,x可逆)P(B){0,1}并

(或∨)

(0)B(1)

-1=(0-1=0)交

(與∧)B(1)

(0)B-1=B(1-1=1)

(

)

(0)無xAA函數(shù)復(fù)合

IA無雙射逆元=反函數(shù)Zn模乘

10x,n互質(zhì),x有逆元模加

0無n

x(0-1=0)Z+lcm1無1-1=1gcd無1無{0,1}等價(jià)

1無x由運(yùn)算表判別算律的一般方法交換律：運(yùn)算表關(guān)于主對(duì)角線對(duì)稱冪等律：主對(duì)角線元素排列與表頭順序一致消去律：所在的行與列中沒有重復(fù)元素單位元:所在行與列的元素排列都與表頭一致零元：元素的行與列都由該元素自身構(gòu)成A的可逆元：a所在的行中某列(比如第j列)元素為e，且第j行

i列的元素也是e，那么a

與第j個(gè)元素互逆結(jié)合律：除了單位元、零元之外，要對(duì)所有3個(gè)元素的組合驗(yàn)證表示結(jié)合律的等式是否成立習(xí)題5.1，5.95.2代數(shù)系統(tǒng)及其子代數(shù)和積代數(shù)重要概念：<S1,o>和<S2,>是代數(shù)系統(tǒng)，積代數(shù)<S1

S2,?>有：<x1,y1>?<x2,y2>=<x1ox2,y1

y2>.題5.10(1)若o

和

運(yùn)算是可交換的，那么?運(yùn)算也是可交換的

(2)若o

和

運(yùn)算是可結(jié)合的，那么?運(yùn)算也是可結(jié)合的

(3)若o

和

運(yùn)算是冪等的，那么?運(yùn)算也是冪等的

(4)若

o

和

運(yùn)算分別具有單位元

e1

和e2，那么?運(yùn)算也具有單位元<e1,e2>(5)若o

和

運(yùn)算分別具有零元1和2，那么?運(yùn)算也具有零元<

1,

2>(6)若x關(guān)于

o

的逆元為x

1,y關(guān)于

的逆元為y1，那么<x,y>關(guān)于?運(yùn)算也具有逆元<x1,y1>5.3代數(shù)系統(tǒng)的同態(tài)與同構(gòu)(重點(diǎn))V1=<S1,°>和V2=<S2,>是代數(shù)系統(tǒng),f:S1

S2,x,y∈S1,

f(x°y)=f(x)f(y),則稱f為V1到V2的同態(tài)(映射).如果同態(tài)f是滿射，則稱為滿同態(tài)，這時(shí)稱V2是V1的同態(tài)像，記作V1

V2；如果同態(tài)f是雙射，則稱為同構(gòu)，記作V1

V2.習(xí)題5.6，5.5。六13，15滿同態(tài)保持運(yùn)算的算律及特異元素V1=<S1,°,?>和V2=<S2,o’,?’

>是代數(shù)系統(tǒng)，f：V1

V2是滿同態(tài)，那么(1)若o運(yùn)算是可交換的（可結(jié)合、冪等的），則o’運(yùn)算也是可交換的（可結(jié)合、冪等的）.(2)若o運(yùn)算對(duì)?運(yùn)算是可分配的，則o’運(yùn)算對(duì)?’運(yùn)算也是可分配的；若o

和?運(yùn)算是可吸收的，則o’和?’運(yùn)算也是可吸收的。(3)若e為o

運(yùn)算的單位元，則f(e)為o’運(yùn)算的單位元.(4)若

為o

運(yùn)算的零元，則f(

)為o’運(yùn)算的零元.(5)設(shè)u

V1，若u1是

u

關(guān)于o運(yùn)算的逆元，則f(u

1)

是

f(u)關(guān)于o’運(yùn)算的逆元。注意事項(xiàng)1）集合S上的二元運(yùn)算就是S×S→S的二元函數(shù).集合S上的一元運(yùn)算就是S→S的一元函數(shù).2）e-1=e.當(dāng)|S|

2，單位元與零元是不同的，零元無逆元；當(dāng)|S|=1時(shí)，這個(gè)元素既是單位元也是零元.3）子代數(shù)B和原代數(shù)S含有相同的代數(shù)常數(shù)4）同態(tài)映射保持運(yùn)算的算律及特異元素僅在滿同態(tài)時(shí)成立，如果不是滿同態(tài)，那么相關(guān)性質(zhì)在同態(tài)像中成立.

同態(tài)映射不一定能保持消去律成立.了解運(yùn)算表代數(shù)系統(tǒng)的載體，成分，代數(shù)常數(shù)同類型與同種代數(shù)系統(tǒng)子代數(shù)和原代數(shù)是同種的代數(shù)系統(tǒng)最大的子代數(shù)就是V本身.代數(shù)常數(shù)(對(duì)運(yùn)算封閉)構(gòu)成最小的子代數(shù).最大和最小子代數(shù)稱為平凡的子代數(shù).真子代數(shù).習(xí)題5.4零同態(tài)、單(自)同態(tài)、(滿)自同態(tài)和自同構(gòu).第6章幾個(gè)典型的代數(shù)系統(tǒng)6.1半群與群6.2環(huán)與域（“域”是重點(diǎn)）6.3格與布爾代數(shù)（“布爾代數(shù)”是重點(diǎn)）6.1 (半)群|S|≥2<S,o>封閉性結(jié)合律含幺所有元有逆元交換律<a>={az}消去律含零代數(shù)系統(tǒng)√半群√√交換半群獨(dú)異點(diǎn)√√√群√√√√√×Abel群√√√√√√×循環(huán)群√√√√√√√×重要概念：循環(huán)群，n元置換群。(半)群實(shí)例(1)<Z+,+>,交換半群,不含幺;<N,+,0>,交換半群,含幺半群,非群;<Z,+,0>,<Q,+,0>,<R,+,0>,<C,+,0>都是交換群;<Z+,*,1>,<N,*,1,0>,<Z,*,1,0>都是交換半群,含幺半群,非群;<Q*,*,1>,<R*,*,1>,<C*,*,1>都是交換群。+是普通加法,*是普通乘法.(2)<Mn(R),+,0n>是交換群;<Mn(R),·,In,0n>是含幺半群,非交換。+和·分別表示矩陣加法和乘法.(3)<P(B),

,,B>,<P(B),

,B,>為交換半群,含幺半群,非群;<P(B),,>為交換群。并

,交

,對(duì)稱差.(4)<Zn,,0>為交換群;<Zn,

,1,0>為交換半群,含幺半群,非群;<Zn*,

,1>(n為素?cái)?shù))為交換群。模加,模乘(5)<AA,,IA>為含幺半群,非交換,

為函數(shù)復(fù)合. n元對(duì)稱群及其子群n元置換群為(非交換)群.注：Q*,R*,C*,Zn*不含0；Zn={0,1,…,n

1}.習(xí)題6.2，6.4，6.8掌握重要概念，了解性質(zhì)設(shè)G為群，a∈G，令H={ak|k∈Z}，則H是G的子群，稱為由a生成的子群，記作<a>.設(shè)G是群，若存在a∈G使得G={ak

|k∈Z}，則稱G是循環(huán)群，記作G=<a>，稱a為G的生成元.習(xí)題6.5，6.9(1)若G=<a>是無限循環(huán)群，則G只有a和a

1兩個(gè)生成元.

(2)若G=<a>是n階循環(huán)群，則ar是G的生成元當(dāng)且僅當(dāng)r是小于等于n且與n互質(zhì)的正整數(shù).(1)設(shè)G=<a>是循環(huán)群，則G的子群仍是循環(huán)群.(2)若G=<a>是無限循環(huán)群，則G的子群除{e}以外都是無限循環(huán)群.(3)若G=<a>是n階循環(huán)群，則對(duì)n的每個(gè)正因子d，G恰好含有一個(gè)d階子群.6.2環(huán)與域<S,+,*>含幺所有元素有逆元交換律分配律消去律|S|≥2環(huán)*是半群√+是Abel群√√√√域整環(huán)交換環(huán)*是交換半群√含幺環(huán)*是獨(dú)異點(diǎn)√除環(huán)無零因子環(huán)*√*√(θ除外)√n為素?cái)?shù)

<Zn,

,

>是域環(huán)與域的實(shí)例(1)整數(shù)集、有理數(shù)集、實(shí)數(shù)集和復(fù)數(shù)集關(guān)于普通加法和乘法構(gòu)成環(huán)，分別稱為整數(shù)環(huán)Z(整環(huán))、有理數(shù)環(huán)Q(域)、實(shí)數(shù)環(huán)R(域)和復(fù)數(shù)環(huán)C(域).(2)n(n≥2)階實(shí)矩陣的集合Mn(R)關(guān)于矩陣的加法和乘法構(gòu)成環(huán)，稱為n階實(shí)矩陣環(huán)(含幺環(huán)).(3)冪集P(B)關(guān)于對(duì)稱差和交運(yùn)算構(gòu)成環(huán)(交換環(huán),含幺環(huán)).(4)Zn＝{0,1,...,n－1}，

和

分別表示模n加法和乘法，<Zn,

,

>構(gòu)成環(huán)，稱為模n的整數(shù)環(huán)(交換環(huán),含幺環(huán))；n為素?cái)?shù)

<Zn,

,

>是域.習(xí)題6.6。六56.3格與布爾代數(shù)(“布爾代數(shù)”是重點(diǎn))<L,∧,∨>結(jié)合律交換律冪等律吸收律封閉性幺元e零元

格∧√√√√√10∨√√√√01布爾格=有補(bǔ)分配格冪集格(|P|=2n)有界格鉆石格和五角格是有補(bǔ)格，非分配格。<Z,≤>是鏈;鏈?zhǔn)欠峙涓?中間元素?zé)o補(bǔ)。6.3格與布爾代數(shù)1）設(shè)<S,?>是偏序集，如果

x,y?S，{x,y}都有最小上界和最大下界，則稱S關(guān)于偏序?作成一個(gè)格.Sn是n的正因子的集合.D為整除關(guān)系,則偏序集<Sn,D>構(gòu)成分配格.n分解為素?cái)?shù)的單次冪相乘時(shí),Sn是布爾格.<P(B),>為B的冪集格

布爾格.<Z,≤>是鏈；任何一條鏈(中間元素?zé)o補(bǔ)元)都是分配格.2）定理設(shè)L是格,則L是分配格當(dāng)且僅當(dāng)L不含有與鉆石格或五角格同構(gòu)的子格.小于五元的格都是分配格.3）格L若存在全下界0或全上界1,一定是惟一的.a∧b=0和a∨b=1成立,則稱b是a的補(bǔ)元.0,1互補(bǔ).有界分配格L中元素a若存在補(bǔ)元,則存在惟一的補(bǔ)元.4）有限布爾代數(shù)(布爾格=有補(bǔ)分配格)L含有2n個(gè)元素.習(xí)題6.13，6.12，6.3，6.14，6.7；例6.13。七2；四8注意事項(xiàng)1）兩個(gè)n元置換的乘法就是函數(shù)的復(fù)合運(yùn)算n

元置換的求逆就是求反函數(shù).題6.10。五9.所有的n元置換構(gòu)成集合Sn，Sn關(guān)于置換乘法構(gòu)成n元對(duì)稱群.恒等置換(1)是單位元，逆置換σ

1是σ的逆元.n元對(duì)稱群的子群稱為n元置換群.2）x的加法逆元為負(fù)元，記作

x.3）全下界0與全上界1互補(bǔ).了解冪運(yùn)算子半群與子獨(dú)異點(diǎn);子群,真子群,平凡子群;子格積半群與積獨(dú)異點(diǎn)半群和獨(dú)異點(diǎn)的同態(tài)，格同態(tài).習(xí)題6.11Klein四元群有限群，無限群.群G的基數(shù)稱為群G的階|G|.元素x的階(或周期)|x|=k，稱x為k階元.無限階元.子群判定定理；群G的中心C.k階輪換與對(duì)換格的對(duì)偶命題與對(duì)偶原理第四部分 圖論圖論基本定理——握手定理任意無向圖和有向圖的所有頂點(diǎn)度數(shù)之和都等于邊數(shù)的2倍,并且有向圖的所有頂點(diǎn)入度之和等于出度之和等于邊數(shù).推論

在任何無向圖和有向圖中，奇度頂點(diǎn)的個(gè)數(shù)必為偶數(shù).不存在具有奇數(shù)個(gè)面且每個(gè)面都具有奇數(shù)條棱的多面體.習(xí)題7.1,7.14,7.19,7.5,7.6;例7.8(六3)。五6第7章圖的基本概念7.1無向圖及有向圖(握手定理、自補(bǔ)圖是重點(diǎn))7.2通路、回路、圖的連通性(割集是重點(diǎn))7.3圖的矩陣表示(由有向圖的鄰接矩陣求通路數(shù)和回路數(shù)是重點(diǎn))7.4最短路徑(Dijkstra標(biāo)號(hào)法)與關(guān)鍵(最長)路徑7.1無向圖及有向圖重要概念：1）設(shè)G1=<V1,E1>,G2=<V2,E2>為兩個(gè)無向圖(有向圖),若存在雙射函數(shù)f:V1

V2,使得對(duì)于任意的vi,vj

V1,(vi,vj)

E1（<vi,vj>

E1）當(dāng)且僅當(dāng)(f(vi),f(vj))

E2（<f(vi),f(vj)>

E2），并且,(vi,vj)（<vi,vj>）與(f(vi),f(vj))（<f(vi),f(vj)>）的重?cái)?shù)相同，則稱G1與G2是同構(gòu)的，記作G1

G2.同構(gòu)的必要條件,但它們都不是充分條件:①邊數(shù)相同，頂點(diǎn)數(shù)相同②度數(shù)列相同(不計(jì)度數(shù)的順序)③對(duì)應(yīng)頂點(diǎn)的關(guān)聯(lián)集及鄰域的元素個(gè)數(shù)相同.2）既無平行邊也無環(huán)的圖稱為簡單圖.題7.13n階無向完全圖Kn:邊數(shù)m=n(n-1)/2,

=

=n-1.題7.7n階有向完全圖:邊數(shù)m=n(n-1),

=

=2(n-1),

+=

+=

-=

-=n-1.習(xí)題7.93）若G

G且V

=V，則稱G

為G的生成子圖.4）設(shè)G=<V,E>為n階無向簡單圖，以V為頂點(diǎn)集,所有使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱為G的補(bǔ)圖，記作.習(xí)題7.8若G

,則稱G是自補(bǔ)圖.習(xí)題7.20，7.12習(xí)題7.12，7.10；例7.107.1無向圖及有向圖(自補(bǔ)圖是重點(diǎn))7.2通路、回路、圖的連通性(了解)1）區(qū)分初級(jí)通路(路徑)與簡單通路,初級(jí)回路(圈)與簡單回路.2）u

v(連通,不一定直通).規(guī)定u與自身總連通.四6，11，12連通關(guān)系R={<u,v>|u,v

V且u

v}是V上的等價(jià)關(guān)系連通圖:平凡圖,任意兩點(diǎn)都連通的圖.G是連通圖

p(G)=1連通分支:V關(guān)于R的等價(jià)類的導(dǎo)出子圖.設(shè)V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是G的連通分支,其個(gè)數(shù)記作p(G)=k.3）D弱連通(連通):基圖為無向連通圖.D單向連通:

u,v

V，u可達(dá)v

或v可達(dá)u.D強(qiáng)連通:

u,v

V，u與v相互可達(dá)強(qiáng)連通

單向連通

弱連通.習(xí)題7.21，7.16(強(qiáng)連通判別法)D強(qiáng)連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的回路.(單向連通判別法)D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路割集（重點(diǎn)）記G

v:從G中刪除頂點(diǎn)v及關(guān)聯(lián)的邊.G

V

:從G中刪除V

中所有頂點(diǎn)及關(guān)聯(lián)的邊.G

e:從G中刪除邊e.G

E

:從G中刪除E

中所有邊.設(shè)無向圖G=<V,E>,V

V,若p(G

V

)>p(G)且

V

V

,p(G

V

)=p(G),稱V

為G的點(diǎn)割集.若{v}為點(diǎn)割集,稱v為割點(diǎn).V

為點(diǎn)割集且V

?V

V

∪V

非點(diǎn)割集.設(shè)無向圖G=<V,E>,E

E,若p(G

E

)>p(G)且

E

E

,p(G

E

)=p(G),稱E

為G的邊割集.若{e}為邊割集,稱e為割邊或橋.E

為邊割集且E

?E

E

∪E

非邊割集.Kn無點(diǎn)割集.n階零圖既無點(diǎn)割集，也無邊割集.若G連通，E

為邊割集，則p(G

E

)=2.例7.11若G連通，V

為點(diǎn)割集，則p(G

V

)

2.習(xí)題7.177.3圖的矩陣表示有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令aij(1)為頂點(diǎn)vi鄰接到頂點(diǎn)vj邊的條數(shù),稱(aij(1))m

n為D的鄰接矩陣,記作A(D),簡記為A.有向圖的鄰接矩陣（重點(diǎn)）定理設(shè)A為n階有向圖D的鄰接矩陣,則Al(l

1)中元素為D中vi到vj長度為l的通路數(shù)，為vi到自身長度為l的回路數(shù)，為D中長度為l的通路總數(shù)，為D中長度為l的回路總數(shù).習(xí)題7.18推論設(shè)Bl=A+A2+…+Al(l

1),則Bl中元素為D中長度小于或等于l的通路數(shù)，為D中長度小于或等于l的回路數(shù).7.4最短路徑與關(guān)鍵(最長)路徑帶權(quán)圖；最短路徑與Dijkstra標(biāo)號(hào)法.習(xí)題7.22。五4PERT圖(計(jì)劃評(píng)審技術(shù)圖)與關(guān)鍵路徑.關(guān)鍵路徑:PETR圖中從始點(diǎn)到終點(diǎn)的最長路徑vi的最早完成時(shí)間TE(vi):從始點(diǎn)v1沿最長路徑到vi所需的時(shí)間.TE(v1)=0 TE(vi)=max{TE(vj)+wji|vj

-(vi)},i=2,3,,nvi的最晚完成時(shí)間TL(vi):在保證終點(diǎn)vn的最早完成時(shí)間不增加的條件下,從始點(diǎn)v1最遲到達(dá)vi的時(shí)間

TL(vn)=TE(vn) TL(vi)=min{TL(vj)-wij|vj

+(vi)},i=n-1,n-2,,1vi的緩沖時(shí)間TS(vi)=TL(vi)-TE(vi),i=1,2,,nvi在關(guān)鍵路徑上

TS(vi)=0.習(xí)題7.23了解n階圖:n個(gè)頂點(diǎn)的圖.有限圖:V,E都是有窮集的圖.零圖:E=.平凡圖:1階零圖.空?qǐng)D:V=.端點(diǎn)(始點(diǎn),終點(diǎn)),關(guān)聯(lián)次數(shù),環(huán),孤立點(diǎn),相鄰,鄰接.鄰域(先驅(qū)元集∪后繼元集),閉鄰域,關(guān)聯(lián)集.v的度數(shù)d(v)=出度d+(v)+入度d

(v);懸掛頂點(diǎn),懸掛邊;G的最大度

(G),最小度

(G);D的最大出度

+(D),最小出度

+(D),最大入度

(D),最小入度

(D);度數(shù)列,出度列,入度列;平行邊,重?cái)?shù),多重圖;n階k正則圖;子圖,母圖,真子圖,導(dǎo)出子圖;連通度.可達(dá)矩陣P(D)主對(duì)角線上的元素全為1.關(guān)聯(lián)矩陣.D強(qiáng)連通當(dāng)且僅當(dāng)可達(dá)矩陣P(D)的元素全為1.第8章一些特殊的圖圖的類型(二部圖,歐拉圖,哈密頓圖,平面圖,樹)判別是重點(diǎn).習(xí)題8.18,8.21;例8.2~8.5.四148.1二部圖（了解匹配）8.2歐拉圖（前提連通）8.3哈密頓圖（前提連通）8.4平面圖（歐拉公式是重點(diǎn)，了解自對(duì)偶圖）8.1二部圖設(shè)無向圖G=<V,E>,若能將V分成V1和V2(V1

V2=V,V1

V2=),使得G中的每條邊的兩個(gè)端點(diǎn)都一個(gè)屬于V1,另一個(gè)屬于V2,則稱G為二部圖,記為<V1,V2,E>,稱V1和V2為互補(bǔ)頂點(diǎn)子集.又若G是簡單圖,且V1中每個(gè)頂點(diǎn)均與V2中每個(gè)頂點(diǎn)都相鄰,則稱G為完全二部圖,記為Kr,s,其中r=|V1|,s=|V2|.注:n階零圖為二部圖.題8.2,8.3定理無向圖G=<V,E>是二部圖當(dāng)且僅當(dāng)G中無奇圈.二部圖無環(huán)；平行邊不影響圖的二部性.匹配(邊獨(dú)立集):任2條邊均不相鄰的邊子集.習(xí)題8.4極大匹配,最大匹配,匹配數(shù)

1,(非)飽和點(diǎn),完美匹配.注：匹配不限于二部圖；完備匹配專門針對(duì)二部圖而言.滿足t條件

滿足相異性條件

存在完備匹配(Hall定理).8.2歐拉圖歐拉通路:圖中恰好經(jīng)過每條邊一次的通路.歐拉回路:圖中恰好經(jīng)過每條邊一次的回路.歐拉圖:有歐拉回路的圖.半歐拉圖:有歐拉通路而無歐拉回路的圖.定理有向圖D是歐拉圖當(dāng)且僅當(dāng)D連通且每個(gè)頂點(diǎn)的入度都等于出度.習(xí)題8.10有向圖D具有歐拉通路當(dāng)且僅當(dāng)D連通且恰有兩個(gè)奇度頂點(diǎn),其中一個(gè)入度比出度大1,另一個(gè)出度比入度大1,其余頂點(diǎn)的入度等于出度.歐拉通路是簡單通路,歐拉回路是簡單回路.規(guī)定平凡圖為歐拉圖.環(huán)不影響圖的歐拉性.哥尼斯堡七橋問題無歐拉通路也無歐拉回路.8.3哈密頓圖哈密頓通路:經(jīng)過圖中所有頂點(diǎn)恰好一次的通路.哈密頓回路:經(jīng)過圖中所有頂點(diǎn)恰好一次的回路.哈密頓圖:具有哈密頓回路的圖.半哈密頓圖:具有哈密頓通路而無哈密頓回路的圖.哈密頓通路是初級(jí)通路，哈密頓回路是初級(jí)回路.平凡圖是哈密頓圖.環(huán)與平行邊不影響圖的哈密頓性.定理(必要條件)設(shè)無向圖G=<V,E>是哈密頓圖,則對(duì)于任意V1

V且V1,均有p(G

V1)

|V1|.Kr,s當(dāng)s

r+1時(shí)不是哈密頓圖.設(shè)G為n階無向連通簡單圖,若G中有割點(diǎn)或橋,則G不是哈密頓圖.習(xí)題8.12無向哈密頓圖的一個(gè)充分條件定理

G是n階無向簡單圖,若任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和大于等于n

1,則G中存在哈密頓通路.當(dāng)n

3時(shí),若任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和大于等于n,則G中存在哈密頓回路,從而G為哈密頓圖.當(dāng)n

3時(shí),Kn均為哈密頓圖.習(xí)題8.11(四7),8.14,8.19當(dāng)r

2時(shí),Kr,r是哈密頓圖,而Kr,r+1是半哈密頓圖.哈密頓周游世界問題中存在哈密頓回路,故它是哈密頓圖.注意,并不滿足充分條件.8.4平面圖（歐拉公式是重點(diǎn)）如果能將圖G除頂點(diǎn)外邊不相交地畫在平面上,則稱G是平面圖.這個(gè)畫出的無邊相交的圖稱作G的平面嵌入.沒有平面嵌入的圖稱作非平面圖.平行邊與環(huán)不影響圖的平面性.設(shè)G

G,若G為平面圖,則G

也是平面圖;若G

為非平面圖,則G也是非平面圖.Kn(n

5),Km,n(m,n

3)都是非平面圖.定理平面圖各面的次數(shù)之和等于邊數(shù)的2倍.歐拉公式的推廣：n

m+r=p+1.習(xí)題8.16定理設(shè)G為簡單平面圖，則

(G)

5.六8庫拉圖斯基定理：G是平面圖

G中不含與K5,K3,3同胚收縮的子圖.習(xí)題8.23了解無限面(外部面)R0,有限面(內(nèi)部面),邊界,面Ri的次數(shù)deg(Ri)極大平面圖(習(xí)題8.20).若簡單平面圖中已無不相鄰頂點(diǎn),則是極大平面圖.K1,K2,K3,K4都是極大平面圖.極大平面圖必連通.n(n3)階極大平面圖中不可能有割點(diǎn)和橋.設(shè)G為n(n3)階極大平面圖,則G每個(gè)面的次數(shù)均為3.任何n(n

4)階極大平面圖G均有δ(G)

3.極小非平面圖：K5,K3,3都是極小非平面圖極小非平面圖必為簡單圖同胚與收縮平面圖G的對(duì)偶圖G*是平面圖,而且是平面嵌入.G*是連通圖.若邊e為G中的環(huán),則G*與e對(duì)應(yīng)的邊e*為橋;若e為橋,則G*中與e對(duì)應(yīng)的邊e*為環(huán).在多數(shù)情況下,G*含有平行邊.同構(gòu)的平面圖的對(duì)偶圖不一定同構(gòu).題17(1)n*=r;(2)m*=m;(3)r*=n-p+1;(4)d(vi*)=deg(Ri).題22第9章樹9.1無向樹及生成樹(利用Kruskal避圈法求最小生成樹是重點(diǎn)，并求對(duì)應(yīng)的基本回路系統(tǒng)和基本割集系統(tǒng))9.2根樹及其應(yīng)用(利用Huffman算法求最優(yōu)r元樹或最佳前綴碼是重點(diǎn),了解波蘭符號(hào)法與逆波蘭符號(hào)法)9.1無向樹及生成樹無向樹:連通無回路的無向圖.例9.5.平凡樹:平凡圖.森林:每個(gè)連通分支都是樹的非連通的無向圖.題9.3樹葉:樹中度數(shù)為1的頂點(diǎn).分支點(diǎn):度數(shù)

2的頂點(diǎn).n階無向樹的性質(zhì):1)(重要)邊數(shù)m=n

1;習(xí)題9.2,9.52)G中任意兩個(gè)頂點(diǎn)之間存在惟一的路徑;例9.113)G是連通的且G中任何邊均為橋;四1(2)，六64)G中沒有回路,但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊后所得圖中有惟一的一個(gè)含新邊的圈.定理

n階非平凡的無向樹T中