離散數(shù)學期末復習大綱

1、復習復習大綱大綱一、關(guān)系的概念一、關(guān)系的概念1 1、關(guān)系的定義、關(guān)系的定義 集合集合A A到到B B的二元關(guān)系定義：設(shè)的二元關(guān)系定義：設(shè)A A，B B為集合，為集合， AxBAxB的任何子集的任何子集所確定的二元關(guān)系叫做從所確定的二元關(guān)系叫做從A A到到B B的二元關(guān)系的二元關(guān)系 當當A AB B時則叫做時則叫做A A上的二元關(guān)系上的二元關(guān)系2 2、關(guān)系的表示、關(guān)系的表示 1 1）集合表示）集合表示 R=xR=| P(x,y) y| P(x,y) 2 2）關(guān)系矩陣表示：有窮集合）關(guān)系矩陣表示：有窮集合A A上的二元關(guān)系可用上的二元關(guān)系可用布爾矩陣表示布爾矩陣表示 3 3）關(guān)系圖）關(guān)系圖G GR

2、 R表示：表示： 以以A A中的元素為結(jié)點，若中的元素為結(jié)點，若 R R，則從到畫一條有向弧，則從到畫一條有向弧3 3、關(guān)系的運算、關(guān)系的運算 1 1）關(guān)系的一般集合的運算：）關(guān)系的一般集合的運算：并、交、相對補、補及對稱差并、交、相對補、補及對稱差 2 2）關(guān)系的逆運算）關(guān)系的逆運算 R R-1-1 x | y | yR xR 3 3） 關(guān)系的復合運算關(guān)系的復合運算 1 1）定義：設(shè)）定義：設(shè)F F，G G為二元關(guān)系，為二元關(guān)系，G G對對F F的右復合記作的右復合記作F o G F o G ， F o G F o G x | y | t (x t (F F G )yG )等價關(guān)系部分復習等

3、價關(guān)系部分復習 4）關(guān)系的冪運算）關(guān)系的冪運算 定義：設(shè)定義：設(shè)R為為A上的關(guān)系，上的關(guān)系，n為自然數(shù)，則為自然數(shù)，則R的的n次冪定義為：次冪定義為： (1) R0 | xA = IA (2) Rn+1 R n o R 即對于即對于A上的任何關(guān)系上的任何關(guān)系Rl和和R2都有都有 R10 R20 IA 性質(zhì)性質(zhì): (類似于數(shù)的冪運算性質(zhì)類似于數(shù)的冪運算性質(zhì)) Rm o Rn = Rm+n ( Rm ) n = Rmn 4 4、關(guān)系的性質(zhì)、關(guān)系的性質(zhì)關(guān)系的性質(zhì)主要有以下五種：關(guān)系的性質(zhì)主要有以下五種：自反性，反自反性，對稱性，反對稱性和傳遞性自反性，反自反性，對稱性，反對稱性和傳遞性 (1) (1

4、) 若若 x( xA xx( xA R)xR)，則稱，則稱R R在在A A上是自反的上是自反的 具有自反性的關(guān)系矩陣的特征是：具有自反性的關(guān)系矩陣的特征是：主對角線上元素均為主對角線上元素均為1 1 具有自反性的關(guān)系圖的特征是：具有自反性的關(guān)系圖的特征是：每個結(jié)點均有環(huán)每個結(jié)點均有環(huán) (2) (2) 若若x ( xA xx ( xA R)xR) ，則稱，則稱R R在在A A上是反自反的上是反自反的 具有反自反性的關(guān)系矩陣的特征是：具有反自反性的關(guān)系矩陣的特征是：主對角線上元素均為主對角線上元素均為0 0 具有自反性的關(guān)系圖的特征是：具有自反性的關(guān)系圖的特征是：每個結(jié)點均沒有環(huán)每個結(jié)點均沒有環(huán)

5、（3 3）若）若 x x y y（x x，y A xy A R R RxR） 則稱則稱R R為為A A上的對稱的關(guān)系上的對稱的關(guān)系 具有對稱性的關(guān)系矩陣的特征是：具有對稱性的關(guān)系矩陣的特征是：是對稱矩陣是對稱矩陣 具有對稱性的關(guān)系圖的特征是：具有對稱性的關(guān)系圖的特征是：兩個互異結(jié)點之間有弧必有方向相反的兩條兩個互異結(jié)點之間有弧必有方向相反的兩條 （4 4）若）若 x x y y（x x，y A xy A R R RxR x = y x = y） 則稱則稱R R為為A A上的反對稱的關(guān)系上的反對稱的關(guān)系 具有反對稱性的關(guān)系矩陣的特征是：具有反對稱性的關(guān)系矩陣的特征是：是非對稱矩陣是非對稱矩陣 具

6、有反對稱性的關(guān)系圖的特征是：具有反對稱性的關(guān)系圖的特征是：兩個互異結(jié)點之間有弧僅有一條兩個互異結(jié)點之間有弧僅有一條（5 5）若）若x xy yz(xz(x，y y，zA xzA R R R R R )zR )， 則稱則稱 R R為為A A上傳遞的關(guān)系。上傳遞的關(guān)系。 以上性質(zhì)的定義中均使用了條件語句，當前件為假時，該語句為真。故當關(guān)系以上性質(zhì)的定義中均使用了條件語句，當前件為假時，該語句為真。故當關(guān)系R R不滿足某個性質(zhì)定義前件時，就可以確定不滿足某個性質(zhì)定義前件時，就可以確定R R滿足該性質(zhì)。滿足該性質(zhì)。二二、等價關(guān)系與劃分、等價關(guān)系與劃分1 1、等價關(guān)系定義等價關(guān)系定義：設(shè)設(shè)R R為非空集

7、合上的關(guān)系為非空集合上的關(guān)系 如果如果R R是自反的是自反的、對稱的對稱的和和傳遞的傳遞的，則稱，則稱R R為為A A上的等價關(guān)系。上的等價關(guān)系。 設(shè)設(shè)R R是一個等價關(guān)系，若是一個等價關(guān)系，若x Ry R，稱，稱x x等價于等價于y y，記作，記作x x y y 注：注：1 1）R R是等價關(guān)系必須是等價關(guān)系必須同時滿足三個性質(zhì)同時滿足三個性質(zhì) 2)R 2)R是等價關(guān)系的矩陣特征和圖特征是等價關(guān)系的矩陣特征和圖特征2 2、典型例子：、典型例子：定義定義整數(shù)集整數(shù)集上的關(guān)系上的關(guān)系R R： R Rx | xy | x，yA x y(mod 5) yA x y(mod 5) 其中其中x y(mo

8、d 5) x y(mod 5) 叫做叫做x x與與y y模模5 5相等相等，即，即x x除以除以5 5的余數(shù)與的余數(shù)與y y除以除以5 5的的余數(shù)相等余數(shù)相等3 3、等價類、等價類 1) 1)等價類定義：設(shè)等價類定義：設(shè)R R為非空集合為非空集合A A上的等價關(guān)系，上的等價關(guān)系，xAxA，令，令 x R y | y A x R y 或或 R 稱稱xxR R為為x x關(guān)于關(guān)于R R的等價類，簡稱為的等價類，簡稱為x x的等價類，簡記為的等價類，簡記為xxR R 注：注：xxR R是由是由A A中有與中有與x x有關(guān)系有關(guān)系R R 的元素組成的元素組成 （A A中所有與中所有與x x等價的元素等價

9、的元素構(gòu)成的集合）即所有與構(gòu)成的集合）即所有與x x 成為序?qū)Φ某沙蔀樾驅(qū)Φ某蓡T構(gòu)成。員構(gòu)成。 等價類的代表等價類的代表 x x R R可以是該集合內(nèi)的可以是該集合內(nèi)的任何元素任何元素4、等價類的性質(zhì)、等價類的性質(zhì)設(shè)設(shè)R為非空集合為非空集合A上的上的等價關(guān)系等價關(guān)系，則，則1 xA，x R 是是A的非空子集的非空子集2 x，yA，如果，如果 xRy ，則，則 x R y R3 x，yA，如果，如果x與與y不具有關(guān)系不具有關(guān)系R，則，則x R y R = 4 xR | x A= A 三個定義等價：三個定義等價： xRy x R y R xy 問題：同一集合上的等價關(guān)系的并及交是否還是等價關(guān)系？問

10、題：同一集合上的等價關(guān)系的并及交是否還是等價關(guān)系？5、商集、商集 1）商集定義：設(shè)）商集定義：設(shè)R為非空集合為非空集合A上的等價關(guān)系，以上的等價關(guān)系，以R的的所有等價所有等價類作為元素的集合類作為元素的集合稱為稱為A關(guān)于關(guān)于R的商集，記作的商集，記作AR， 即即 AR x R | xA 由由A上等價關(guān)系上等價關(guān)系R的的所有不同等價類所有不同等價類構(gòu)成的一個新集合構(gòu)成的一個新集合6 6、集合劃分的定義、集合劃分的定義 設(shè)設(shè)A A為非空集合，若為非空集合，若A A的子集構(gòu)成的集合族的子集構(gòu)成的集合族 ( ( p(A) p(A) 是是A A的子集構(gòu)成的集合的子集構(gòu)成的集合) )滿足下面的條件：滿足下

11、面的條件： 1) 1) 不屬于不屬于 （不空）（不空） 2 2 x xy(xy(x，y x y x y = y x y x y = ) ) 互異互異 3 = A 3 = A 則稱則稱 是是A A的一個劃分，稱的一個劃分，稱 中的元素為中的元素為A A的劃分塊的劃分塊集合集合A A的一個的一個劃分劃分與集合與集合A A上的一個上的一個等價關(guān)系等價關(guān)系R R的等價類的等價類的關(guān)系：的關(guān)系：1 1）由等價關(guān)系）由等價關(guān)系R R所確定的集合所確定的集合A A的的商集商集 A AR R是集合是集合A A的的一個劃分一個劃分 集合集合A A上的一個上的一個等價關(guān)系等價關(guān)系R R與集合與集合A A上的一個劃

12、分上的一個劃分是一一對應關(guān)系是一一對應關(guān)系2 2）集合）集合A A的不同劃分的不同劃分對應集合對應集合A A上的上的不同等價關(guān)系不同等價關(guān)系 對于集合對于集合A A的任何的任何一個劃分一個劃分均可確定均可確定A A上的上的一個等價關(guān)系一個等價關(guān)系R R 由由R R確定的關(guān)于確定的關(guān)于A A的商集等于此劃分的商集等于此劃分 需要掌握：給定需要掌握：給定A A上等價關(guān)系上等價關(guān)系RR確定確定A A的一個劃分（即確定商集）的一個劃分（即確定商集） 給定給定A A的一個劃分的一個劃分確定確定A A上的一個等價關(guān)系上的一個等價關(guān)系R R 有限集合上的所有等價關(guān)系（即有限集合的所有不同劃分）有限集合上的所

13、有等價關(guān)系（即有限集合的所有不同劃分）習題類型：習題類型： p133 33 p133 33、3636、4040 例：設(shè)例：設(shè)A A 1 1，2 2，3 3 求求A A上的所有等價關(guān)系上的所有等價關(guān)系 由于由于A A上的等價關(guān)系與上的等價關(guān)系與A A上的劃分是一一對上的劃分是一一對應關(guān)系，可從對應關(guān)系，可從對A A的劃分來確定相應的等價關(guān)系的劃分來確定相應的等價關(guān)系 三三、函數(shù)：、函數(shù)：作為作為特殊的二元關(guān)系特殊的二元關(guān)系來表示來表示1 1、函數(shù)定義：設(shè)、函數(shù)定義：設(shè)X X、Y Y為非空集合，為非空集合，f f X XY Y是是X X到到Y(jié) Y的二元關(guān)系的二元關(guān)系 滿足：對每個滿足：對每個x x

14、 X,X,都存在一個唯一的都存在一個唯一的y y Y Y 使使 f f則稱關(guān)系則稱關(guān)系f f為為X X到到Y(jié) Y的函數(shù)（映射）的函數(shù)（映射） 記作：記作：f: X f: X Y Y a a、存在性存在性：要且對任一：要且對任一x x X, X, f f 即即Dom(f)=XDom(f)=X b. b.唯一性唯一性：對于每個：對于每個x,x,存在唯一的存在唯一的y y, ,使使 f f2 2、若、若f f是是A A到到B B的函數(shù)，的函數(shù)，Dom(f)= A Dom(f)= A 集合集合A A稱為稱為f f的的定義域定義域， B B成為函數(shù)成為函數(shù)f f的陪域，的陪域，Ran(f) Ran(f)

15、 B, Ran(f) B, Ran(f)稱為稱為f f的值域的值域3 3、 若若 f ,f ,可記為可記為y=f(x),y=f(x),稱稱y y為為x x在在f f下的下的象點象點。 x x為為y y在在f f下的原象下的原象( (也可記為也可記為 x=f-1(y) x=f-1(y) ）。）。 Ran(f)Ran(f)稱為稱為函數(shù)的像函數(shù)的像 記為：記為： Ran(f)Ran(f) = f(A)= f(A) =y| y =y| y B B x( xx( x A A y=f(x) ) y=f(x) ) 4 4、若、若f f是是A A到到B B的函數(shù)的函數(shù),A1 ,A1 A, B1 A, B1 B

16、 B f(A1)=f(A1)=f(x)|x f(x)|x A1 A1 =B1=B1 為為A1A1在在f f下的像下的像( (是是B B的子集）的子集） f(A)f(A)為函數(shù)的像為函數(shù)的像 f f-1-1(B1)=x| x (B1)=x| x A A f(x)f(x) B1B1 為為B1B1在在f f下的下的完全原像完全原像( (是是A A的子集的子集) ) A1 A1 A A f(A1) f(A1) B B 的完全原像的完全原像 f-1(f(A1)f-1(f(A1)是是A A的子集的子集習題類型：習題類型： P160 1P160 1、 3 3、(b(b）對其中）對其中1 1道題熟悉即可道題熟

17、悉即可5 5、 所有定義在所有定義在A A到到B B上的函數(shù)上的函數(shù) 用集合用集合B BA A =f | f =f | f是是A A到到B B的函數(shù)的函數(shù) 習題八習題八 2 26 6、設(shè)、設(shè)f:A f:A B, B,函數(shù)：函數(shù)： 1 1）若）若Ran(f)=B Ran(f)=B 則稱則稱f f為為滿函數(shù)（滿函數(shù)滿函數(shù)（滿函數(shù)）f(A)=B f(A)=B 即：即： y y B , B , x x A A 使使 f f f f是滿函數(shù)的是滿函數(shù)的必要條件必要條件是是 B BA A 2 2）f:A f:A B B 若若: : x1 x2 x1 x2 A,A,當當x1x2x1x2時有時有,f(x1)f

18、(x2),f(x1)f(x2) 則稱則稱f f為單射函數(shù)為單射函數(shù) f f為單函數(shù)的為單函數(shù)的必要條件必要條件 B BA A 3 3） f:A f:A B B 若若f f即是單射函數(shù)又是滿射函數(shù)，則稱即是單射函數(shù)又是滿射函數(shù)，則稱f f為雙射函數(shù)為雙射函數(shù). . f f雙射必要條件：雙射必要條件： B BA A 當當f f是有限集合是有限集合A A上的單函數(shù)時上的單函數(shù)時 則則f f必是滿函數(shù)（雙射函數(shù)）必是滿函數(shù)（雙射函數(shù)）習題類型：習題八習題類型：習題八 5 5、10107 7、特殊函數(shù)、特殊函數(shù)1 1）常值函數(shù)：）常值函數(shù)： f:X f:X Y Y， x x X f(x)=yX f(x)

19、=y2 2）恒等函數(shù)）恒等函數(shù) ：Ix: Ix: X X X X x f(x)=x x f(x)=x 雙射函數(shù)雙射函數(shù) 性質(zhì)：性質(zhì)： f f是是X X Y Y的函數(shù)的函數(shù) f f Ix=Iy Ix=Iy f f3 3）自然映射：）自然映射：R R是是X X上的等價關(guān)系，上的等價關(guān)系，g:X g:X X/R , X/R , x x X,g(x)=xX,g(x)=xR R g g是是X X到商集的自然映射，是一個滿函數(shù)到商集的自然映射，是一個滿函數(shù) 8 8、函數(shù)的復合、函數(shù)的復合1 1）設(shè)）設(shè)f f是是X X到到Y(jié) Y的函數(shù)，的函數(shù)，g g是是Y Y到到Z Z的函數(shù)的函數(shù) 復合關(guān)系：復合關(guān)系：fo

20、g=| fog=| y(yy(y Y Y f f g)g) 稱為稱為f f與與g g的復合函數(shù)的復合函數(shù) fogfog是是X X到到Z Z的函數(shù)，且的函數(shù)，且 x x X, X, fog (x) = g( f(x) )fog (x) = g( f(x) ) 復合運算不滿足交換律（與一般關(guān)系相同）復合運算不滿足交換律（與一般關(guān)系相同） 若若f f是是X X上的函數(shù)，上的函數(shù)， f f f = f 2 f = f 2 fn fn 冪函數(shù)冪函數(shù)2 2）三類重要性質(zhì)函數(shù)的復合性質(zhì)）三類重要性質(zhì)函數(shù)的復合性質(zhì)證明的過程要理解證明的過程要理解 f:X f:X Y Y函數(shù)，函數(shù)， g:Y g:Y Z Z函數(shù)

21、函數(shù) 若若 f f g g 存在存在 i fi f與與g g均為滿函數(shù)均為滿函數(shù) ， f f g g也是滿函數(shù)也是滿函數(shù) ii fii f與與g g均為單函數(shù)，均為單函數(shù)， f f g g也是單函數(shù)也是單函數(shù) iii fiii f與與g g均為雙射函數(shù)，均為雙射函數(shù)， f f g g 也是雙射函數(shù)也是雙射函數(shù)如果如果 f f g g是單函數(shù)，能否確定是單函數(shù)，能否確定f f與與g g均是單函數(shù)？均是單函數(shù)？如果如果 f f g g是滿函數(shù)，能否確定是滿函數(shù)，能否確定f f與與g g均是滿函數(shù)？均是滿函數(shù)？習題類型：習題八習題類型：習題八 1616、1818、2222、26269 9、反函數(shù)、反

22、函數(shù)1 1）定義：設(shè)）定義：設(shè)f:X f:X Y Y 的雙射函數(shù)的雙射函數(shù)則：則：f f的逆關(guān)系的逆關(guān)系f f稱為：稱為：f f的反函數(shù)，記為：的反函數(shù)，記為：f f-1-1 若函數(shù)若函數(shù)f f存在反函數(shù)，則稱存在反函數(shù)，則稱f f是可逆函數(shù)。是可逆函數(shù)。11并非任何函數(shù)都是可逆函數(shù)并非任何函數(shù)都是可逆函數(shù)22若若f f是可逆函數(shù)，則是可逆函數(shù)，則f f一定是雙射函數(shù)一定是雙射函數(shù)3f 3f 是是X X Y Y 的雙射函數(shù)，則的雙射函數(shù)，則f f是可逆函數(shù)是可逆函數(shù)f f-1-1存在存在 且且f f-1-1是是Y Y X X的雙射函數(shù)。的雙射函數(shù)。44若若f f是是 X X到到Y(jié) Y 的可逆函

23、數(shù)，的可逆函數(shù)， g g是是Y Y 到到Z Z的可逆函數(shù)的可逆函數(shù) f f g g是可逆函數(shù)，且是可逆函數(shù)，且(f g) -1 = g -1 f-1 f f-1= ？ f-1 f=？四四、圖的基本概念、圖的基本概念1 1、圖的定義：一個無向圖是一個有序的二元組、圖的定義：一個無向圖是一個有序的二元組 V E ，記作，記作G G，其中，其中(1) (1) V V 稱為頂點集，其元素稱為頂點或結(jié)點稱為頂點集，其元素稱為頂點或結(jié)點(2) (2) E E稱為邊集稱為邊集，它是，它是無序積無序積V VV V的多重子集，其元素稱為無向邊，簡稱為邊的多重子集，其元素稱為無向邊，簡稱為邊 定義定義2 2 一個

24、有向圖是一個有序的二元組一個有向圖是一個有序的二元組VE，記作，記作D D，其中，其中(1) V (1) V 稱為頂點集，其元素稱為頂點或結(jié)點稱為頂點集，其元素稱為頂點或結(jié)點(2)E(2)E為邊集，它是為邊集，它是笛卡兒積笛卡兒積 V VV V的有窮多重子集，其元素稱為有向邊的有窮多重子集，其元素稱為有向邊( (弧弧) )2 2、有關(guān)圖的術(shù)語、有關(guān)圖的術(shù)語1 1）用）用G G表示無向圖，表示無向圖，D D表示有向圖有時用表示有向圖有時用V(G)V(G)，E(G)E(G)分別表示分別表示G G的頂點集和邊集的頂點集和邊集2 2）用）用 V(G)V(G) ，E(G)E(G)分別表示分別表示G G的

25、頂點數(shù)和邊數(shù)的頂點數(shù)和邊數(shù)( (有向圖類似）有向圖類似） 若若V(G)V(G) n n，則稱，則稱G G為為n n階圖。對有向圖可做類似規(guī)定階圖。對有向圖可做類似規(guī)定3 3）在圖）在圖G G中，若中，若邊集邊集E(G)E(G)，則稱，則稱G G為為零圖零圖 若若G G為為n n階圖，則稱階圖，則稱G G為為n n階零圖階零圖，記作，記作N Nn n，特別是稱，特別是稱N N1 1為為平凡圖平凡圖4) 4) 常用常用e ek k表示無向邊表示無向邊(vi(vi，vj)( vj)( 或有向邊或有向邊vi ) vj ) 設(shè)設(shè)G GV E 為無向圖，為無向圖，e ek k = (vi = (vi，vj

26、)Evj)E， 則稱則稱vjvj，vjvj為為e ek k的端點的端點， e ek k與與vivi、vjvj是彼此是彼此相關(guān)聯(lián)的相關(guān)聯(lián)的 起終點相同的邊稱為起終點相同的邊稱為環(huán)環(huán) 不與任何邊關(guān)聯(lián)的結(jié)點稱為不與任何邊關(guān)聯(lián)的結(jié)點稱為孤立點孤立點（包括有向向圖（包括有向向圖) )5 5）鄰接：）鄰接： 邊的相鄰邊的相鄰：e ek k，e el lEE若若e ek k與與e el l至少有一個公共端點，則稱至少有一個公共端點，則稱e ek k與與e el l是相鄰的是相鄰的 頂點的相鄰頂點的相鄰：兩個結(jié)點為一條邊的端點，則稱兩個結(jié)點：兩個結(jié)點為一條邊的端點，則稱兩個結(jié)點互為鄰接點互為鄰接點， 也稱也稱

27、邊關(guān)聯(lián)于這兩個結(jié)點邊關(guān)聯(lián)于這兩個結(jié)點，或稱兩個結(jié)點鄰接于此邊，或稱兩個結(jié)點鄰接于此邊。6 6）平行邊：）平行邊： 在無向圖中，關(guān)聯(lián)一對頂點的無向邊如果多于在無向圖中，關(guān)聯(lián)一對頂點的無向邊如果多于1 1條，則稱這些邊為平行邊，條，則稱這些邊為平行邊，平行邊的條數(shù)稱為重數(shù)平行邊的條數(shù)稱為重數(shù) 在有向圖中，關(guān)聯(lián)一對頂點的有向邊如果多于在有向圖中，關(guān)聯(lián)一對頂點的有向邊如果多于1 1條，并且這些邊的始點與條，并且這些邊的始點與終點相同終點相同( (也就是它們的方向相同也就是它們的方向相同) )，則稱這些邊為平行邊，則稱這些邊為平行邊 7 7）多重圖和簡單圖：）多重圖和簡單圖：含平行邊的圖稱為多重圖含平行

28、邊的圖稱為多重圖 既不含平行邊也不含環(huán)的圖稱為既不含平行邊也不含環(huán)的圖稱為簡單圖簡單圖3 3、結(jié)點的度、結(jié)點的度 設(shè)設(shè)G GVE為無向圖，為無向圖， v V v V，稱，稱v v作為邊的端點次數(shù)之和作為邊的端點次數(shù)之和為為v v的度數(shù)，簡記為的度數(shù)，簡記為d dG G(v)(v)即為：結(jié)點即為：結(jié)點v v 所關(guān)聯(lián)的邊的總條數(shù)所關(guān)聯(lián)的邊的總條數(shù) 關(guān)于有向圖關(guān)于有向圖D DV E 有：有： v Vv V，稱，稱v v 作為邊的作為邊的始點的次數(shù)之和始點的次數(shù)之和為為v v的出度，記作的出度，記作d d- - (v)(v)， 稱稱v v作為邊的終點的次數(shù)之和為作為邊的終點的次數(shù)之和為v v的入度，記

29、作的入度，記作d d+ + (v)(v)， 稱稱d d+ +(v) + d(v) + d- -( v)( v)為為 v v的度數(shù)，記作的度數(shù)，記作d dD D (v)(v) 4 4、結(jié)點的度、結(jié)點的度 1 1）定義）定義4 4 設(shè)設(shè)G GVE為無向圖，為無向圖， v V v V，稱，稱v v作為邊的端點次數(shù)之和作為邊的端點次數(shù)之和為為v v的度數(shù)，簡記為度記作的度數(shù)，簡記為度記作d d G G(v)(v)， 簡記為簡記為d dG G(v)(v)即為：結(jié)點即為：結(jié)點v v 所關(guān)聯(lián)的邊的總條數(shù)所關(guān)聯(lián)的邊的總條數(shù) 關(guān)于有向圖關(guān)于有向圖D DV E 有：有： v Vv V，稱，稱v v 作為邊的作為邊

30、的始點的次數(shù)之和始點的次數(shù)之和為為v v的出度，記作的出度，記作d d- - (v)(v)， 稱稱v v作為邊的終點的次數(shù)之和為作為邊的終點的次數(shù)之和為v v的入度，記作的入度，記作d d+ + (v)(v)， 稱稱d d+ +(v) + d(v) + d- -( v)( v)為為 v v的度數(shù)，記作的度數(shù)，記作d dD D (v)(v) 2) 2) 稱度數(shù)為稱度數(shù)為1 1的頂點為懸掛頂點，與它關(guān)聯(lián)的邊稱為懸掛邊的頂點為懸掛頂點，與它關(guān)聯(lián)的邊稱為懸掛邊5 5、握手定理（歐拉）、握手定理（歐拉）1)1)設(shè)設(shè)G G為任意無向圖為任意無向圖,V,Vvv1 1，v v2 2，v vn n,E E =

31、m = m， 則則 d(vd(vi i) ) 2 m ( 2 m (所有結(jié)點的度數(shù)值和為邊數(shù)的所有結(jié)點的度數(shù)值和為邊數(shù)的2 2倍倍) )2)2)設(shè)設(shè)D D為任意有向圖為任意有向圖,V,Vvv1 1，v v2 2，v vn n,|E| = m ,|E| = m ， 則則 d d+ +(v(vi i) ) d d- -(v(vi i) = m) = m 且且d(vd(vi i) )2 m2 m3) 3) 推論推論 任何圖任何圖( (無向的或有向的無向的或有向的) )中，中，奇度頂點的個數(shù)是偶數(shù)奇度頂點的個數(shù)是偶數(shù)4) 4) 結(jié)點的度數(shù)序列結(jié)點的度數(shù)序列 (1) (1) 設(shè)設(shè)G GVE為一個為一個n

32、 n階無向圖，階無向圖，V Vvv1 1，v v2 2，v vn n 稱稱d(vd(v1 1) )，d(vd(v2 2) )， ，d(vd(vn n) ) 為為G G的度數(shù)列的度數(shù)列 條件：條件：奇度數(shù)奇度數(shù)的結(jié)點個數(shù)應該是的結(jié)點個數(shù)應該是偶數(shù)個偶數(shù)個 （2 2）序列的可圖化：）序列的可圖化： d=(dd=(d1 1,d,d2 2, ,d dn n) ) 對一個整數(shù)序列對一個整數(shù)序列d,d,若存在以若存在以n n個頂點的個頂點的n n階無向圖階無向圖G G，有，有d(vd(vi i)=d)=di i 稱該序列是可圖化的稱該序列是可圖化的（3 3）設(shè)非負整數(shù)列）設(shè)非負整數(shù)列d d(d1(d1，d

33、2d2，dn)dn)則則d d是可圖化的當且僅當是可圖化的當且僅當 ddi i = 0 (mod 2) = 0 (mod 2) ( (序列之和必須是偶數(shù)序列之和必須是偶數(shù)) )（4 4）結(jié)論：）結(jié)論：n n個結(jié)點的個結(jié)點的簡單圖簡單圖中結(jié)點的最大中結(jié)點的最大度數(shù)（度數(shù)（G)G)）應小于）應小于等于等于n-1n-16 6、圖的同構(gòu)、圖的同構(gòu)定義定義: :兩個圖的各結(jié)點之間，如果存在著一一對應關(guān)系兩個圖的各結(jié)點之間，如果存在著一一對應關(guān)系f f 這種對應關(guān)系又保持了這種對應關(guān)系又保持了結(jié)點間的鄰接關(guān)系結(jié)點間的鄰接關(guān)系，那么這兩個圖就是，那么這兩個圖就是同構(gòu)的同構(gòu)的 在有向圖的情況下，在有向圖的情況

34、下，f f不但應該保持結(jié)點間的鄰接關(guān)系，還應該不但應該保持結(jié)點間的鄰接關(guān)系，還應該保持邊的方向保持邊的方向注：注：1) 1) 互為互為同構(gòu)的兩個圖（必要條件）同構(gòu)的兩個圖（必要條件） 有有相同樣的階數(shù)相同樣的階數(shù)（結(jié)點）和（結(jié)點）和同樣數(shù)量的邊數(shù)同樣數(shù)量的邊數(shù)及頂點的及頂點的度數(shù)序列度數(shù)序列 2)2)圖之間的圖之間的同構(gòu)關(guān)系同構(gòu)關(guān)系可看成全體圖集合上的二元關(guān)系可看成全體圖集合上的二元關(guān)系同構(gòu)的圖為一個等價類，在同構(gòu)的圖為一個等價類，在同構(gòu)的意義之下都可以看成是一個圖。同構(gòu)的意義之下都可以看成是一個圖。 畫出畫出4 4階階3 3條邊的所有非同構(gòu)的條邊的所有非同構(gòu)的無向簡單圖無向簡單圖主要掌握：給

35、出邊集主要掌握：給出邊集E E，能表示出圖，能表示出圖 簡單圖的判斷簡單圖的判斷 握手定理的應用握手定理的應用習題類型：習題類型： 習題十四習題十四 3 3、5 5、8 8 7 7、完全圖定義、完全圖定義 設(shè)設(shè)G G為為n n階無向簡單圖，若階無向簡單圖，若G G中每個頂點均與其余的中每個頂點均與其余的n n1 1個頂點相鄰，則稱個頂點相鄰，則稱G G為為n n階無向完全圖，簡稱階無向完全圖，簡稱n n階完全圖階完全圖，記作記作KnKn(n1)(n1) 設(shè)設(shè)D D為為n n階有向簡單圖，若階有向簡單圖，若D D中每個頂點都中每個頂點都鄰接到鄰接到其余的其余的n n1 1個頂個頂點，又點，又鄰接

36、于鄰接于其余的其余的n n1 1個頂點，則稱個頂點，則稱D D是是n n階階有向完全圖有向完全圖完全圖的性質(zhì)：完全圖的性質(zhì)： n n階無向完全圖階無向完全圖G G的邊數(shù)與結(jié)點的關(guān)系的邊數(shù)與結(jié)點的關(guān)系 m = m = n (n-1)/2n (n-1)/2 n n階有向完全圖階有向完全圖G G的邊數(shù)與結(jié)點的關(guān)系的邊數(shù)與結(jié)點的關(guān)系 m = m = n (n-1)n (n-1)8 8、通路：首尾相接的邊的序列、通路：首尾相接的邊的序列L L稱為通路稱為通路 2 2、序列中、序列中首尾結(jié)點相同首尾結(jié)點相同，則稱，則稱L L為回路為回路 3 3、通路的表示：邊的集合表示、通路的表示：邊的集合表示 可僅用通

37、路中的可僅用通路中的邊序列表示邊序列表示：e e1 1e e2 2e ek k 也可僅用通路中所經(jīng)過的也可僅用通路中所經(jīng)過的結(jié)點的序列表示結(jié)點的序列表示：v v1 1v v2 2v v4 4v v1 1v v3 3 4 4、邊序列中的、邊序列中的各條邊全都是互不相同各條邊全都是互不相同的通路，稱為的通路，稱為簡單通路簡單通路 5 5、序列中的、序列中的每一個結(jié)點僅出現(xiàn)一次每一個結(jié)點僅出現(xiàn)一次的通路，稱為的通路，稱為初級通路初級通路 6 6、序列中、序列中首尾結(jié)點相同首尾結(jié)點相同，則稱通路為，則稱通路為初級回路或圈初級回路或圈。 7 7、序列中、序列中邊的條數(shù)邊的條數(shù)稱為它的稱為它的長度長度 8

38、 8、關(guān)系：有向圖中的每一條、關(guān)系：有向圖中的每一條初級通路初級通路，也都，也都必定是簡單通路必定是簡單通路。 反之不成立反之不成立 9 9、在、在n n階圖階圖D D中，若從頂點中，若從頂點vivi到到vjvj存在簡單通路存在簡單通路，則，則vivi到到vjvj一定一定存在長度小于或等于存在長度小于或等于n n1 1的初級通路的初級通路 10 10、在一個、在一個n n階圖階圖D D中，若存在中，若存在vivi到自身的到自身的簡單回路簡單回路，則一定存，則一定存在在vivi到自身到自身長度長度小于或等于小于或等于n n的初級回路（圈）的初級回路（圈） 掌握：初級通路與簡單通路的判斷，及其關(guān)系

39、掌握：初級通路與簡單通路的判斷，及其關(guān)系9 9、圖的連通性、圖的連通性1 1）無向圖的連通性）無向圖的連通性 結(jié)點的連通：結(jié)點的連通： 設(shè)無向圖設(shè)無向圖G GVE， u,v V u,v V，若，若u u，v v之間之間存在通路則稱存在通路則稱u,vu,v是連通的是連通的記作記作u uv v， u V u V，規(guī)定，規(guī)定u uu u 結(jié)點的連通關(guān)系是等價關(guān)系結(jié)點的連通關(guān)系是等價關(guān)系 若定義：若定義： u uv u，vVvV且且 u u與與v v之間有通路之間有通路 此關(guān)系是此關(guān)系是自反，對稱的，傳遞的，自反，對稱的，傳遞的，因而是因而是V V上的上的等價關(guān)系等價關(guān)系2 2）無向圖的連通圖）無向圖

40、的連通圖 若無向圖若無向圖G G中中任何兩個頂點都是連通的任何兩個頂點都是連通的，則稱，則稱G G為連通圖，為連通圖， 否則稱否則稱G G為非連通圖或分離圖（各子圖為為非連通圖或分離圖（各子圖為連通分支連通分支- - 等價類等價類）3 3）結(jié)點之間的距離）結(jié)點之間的距離 設(shè)設(shè)u u，v v為無向圖為無向圖G G中任意兩個頂點中任意兩個頂點, ,若若u uv v，稱，稱u u，v v之間長度最短之間長度最短的通路為的通路為u u，v v之間的短程線之間的短程線 短程線的長度稱為短程線的長度稱為u u，v v之間的之間的距離距離，記作，記作 d(u d(u，v)v) 當當u u，v v不連通時，規(guī)

41、定不連通時，規(guī)定d(ud(u，v)v) 4 4）有向圖的連通性）有向圖的連通性1 1、結(jié)點的可達性結(jié)點的可達性：設(shè)設(shè)D DVE為一個有向圖為一個有向圖 vi,vj V vi,vj V，若，若從從vivi到到vjvj存在通路存在通路, ,則稱則稱vivi可達可達vj,vj, 記作記作vi vj vi vj 。 規(guī)定規(guī)定vivi總是可總是可達自身的達自身的，即，即vi vivi vi2 2、結(jié)點的相互可達、結(jié)點的相互可達 若若vi vj vi vj 且且vj vi vj vi 則稱則稱vivi與與vjvj是相互可達的，是相互可達的， 記作記作: vi : vi vj ( vj (規(guī)定規(guī)定vi vi

42、 vi) vi)3 3、 結(jié)點的可達關(guān)系可結(jié)點的可達關(guān)系可為為V V上的二元關(guān)系，但上的二元關(guān)系，但不是等價關(guān)系不是等價關(guān)系4 4、有向圖中結(jié)點的距離定義：設(shè)、有向圖中結(jié)點的距離定義：設(shè)D DVE為有向圖為有向圖 vi,vj V vi,vj V，若，若 vi vj vi vj，稱，稱vivi到到vivi長度最短的通路為長度最短的通路為vivi到到vjvj的短程線的短程線 短程線的長度為短程線的長度為vivi到到vjvj的的距離距離，記作，記作dvidvj 一般地：一般地：dvid vj dvjd vi （可能（可能d d 不存在）不存在） 5 5）設(shè)）設(shè)D DVV，E)E)為一個有向圖為一個有

43、向圖 若若D D的的作為無向圖是連通圖作為無向圖是連通圖，則稱，則稱D D是弱連通圖是弱連通圖，簡稱為，簡稱為連通圖連通圖 若若 vi,vj V vi,vj V , vi vj, vi vj與與vj vivj vi至少成立其一至少成立其一，則稱，則稱D D是是單單向連通圖向連通圖 若若 vi,vj V vi,vj V，均有，均有vi vi vj vj，則稱，則稱D D是是強連通圖強連通圖 三種圖的關(guān)系：三種圖的關(guān)系：強連通圖一定是強連通圖一定是單向連通圖單向連通圖，反之不成立，反之不成立 單向連通圖一定是單向連通圖一定是弱連通圖弱連通圖反之不成立反之不成立 掌握：對有向圖和無向圖連通的判斷掌握

44、：對有向圖和無向圖連通的判斷 連通關(guān)系與可達關(guān)系的性質(zhì)連通關(guān)系與可達關(guān)系的性質(zhì) 1010、圖的矩陣表示、圖的矩陣表示1 1）無向圖的關(guān)聯(lián)矩陣無向圖的關(guān)聯(lián)矩陣令令m mijij為頂點為頂點v vi i與邊與邊e ej j的關(guān)聯(lián)次數(shù)的關(guān)聯(lián)次數(shù)，則稱則稱(m(mijij) )為為G G的關(guān)聯(lián)矩陣，記作的關(guān)聯(lián)矩陣，記作 M(G) M(G)2 2）關(guān)聯(lián)矩陣的性質(zhì)）關(guān)聯(lián)矩陣的性質(zhì): : 關(guān)聯(lián)矩陣是關(guān)聯(lián)矩陣是n n行（結(jié)點數(shù)）行（結(jié)點數(shù)）m m列（邊數(shù)）列（邊數(shù)）的矩陣的矩陣 (1 (1）M(G)M(G)每列元素之和均為每列元素之和均為2 2，這正說明每條邊關(guān)聯(lián)兩個頂點，這正說明每條邊關(guān)聯(lián)兩個頂點( (環(huán)所

45、關(guān)聯(lián)的兩個環(huán)所關(guān)聯(lián)的兩個端點重合端點重合) )mij = 2 (j = 1mij = 2 (j = 1，2 2，m)m)(2(2）M(G)M(G)第第i i行元素之和為結(jié)點行元素之和為結(jié)點vivi的度數(shù)，的度數(shù)，i i1 1，2 2，nn(3) (3) 所有行的和（即矩陣所有元素之和）等于邊數(shù)的所有行的和（即矩陣所有元素之和）等于邊數(shù)的2 2倍。倍。 d(vi) d(vi)mij= 2 mij= 2 2m 2m，這個結(jié)果滿足，這個結(jié)果滿足握手定理握手定理（4 4）第）第j j列與第列與第k k列相同，當且僅當邊列相同，當且僅當邊ejej與與ekek是平行邊是平行邊 (5) (5) 某行某行i

46、i的和為的和為0 0（即（即 mij = 0 mij = 0）, ,當且僅當當且僅當vivi是孤立點是孤立點3 3）有向圖的）有向圖的關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣設(shè)有向圖設(shè)有向圖D DVE中無環(huán)，中無環(huán)，V Vvv1 1，v v2 2，v vn n 。 E Eeel l，e e2 2, ,，e em m ，令令 1 v1 vi i為邊為邊e ej j的起點的起點 m mijij = = 0 v0 vi i為邊為邊e ej j不關(guān)聯(lián)不關(guān)聯(lián) 1 v1 vi i為邊為邊e ej j的終點的終點 則稱則稱(m(mijij) )nxmnxm，為，為D D的關(guān)聯(lián)矩陣，記作的關(guān)聯(lián)矩陣，記作M(DM(D）4)4)有向圖關(guān)

47、聯(lián)矩陣的性質(zhì)有向圖關(guān)聯(lián)矩陣的性質(zhì) （1 1） mij= 0 mij= 0，j j1 1，2 2，m m，從而，從而mij = 0mij = 0，這說明，這說明M(D)M(D)中所有元中所有元素之和為素之和為0 0 (2) M(D) (2) M(D)中，負中，負1 1的個數(shù)等于正的個數(shù)等于正1 1的個數(shù)，都等于邊數(shù)的個數(shù)，都等于邊數(shù)m m，這正是有向圖握手定，這正是有向圖握手定理的內(nèi)容（入度之和等于出度之和）理的內(nèi)容（入度之和等于出度之和） （3 3）第）第i i行中，正行中，正1 1的個數(shù)等于的個數(shù)等于d+(vi)d+(vi)（結(jié)點的入度），負（結(jié)點的入度），負1 1的個數(shù)等于的個數(shù)等于d-(

48、vi)d-(vi)（結(jié)點的出度）（結(jié)點的出度） （4 4）平行邊所對應的列相同）平行邊所對應的列相同 關(guān)聯(lián)矩陣要求掌握：定義及性質(zhì)關(guān)聯(lián)矩陣要求掌握：定義及性質(zhì)5 5）有向圖的）有向圖的鄰接矩陣鄰接矩陣 設(shè)有向圖設(shè)有向圖D DVE，V Vv1v1，v2v2，vnvn，E Ee1e1，e2e2，emem 令：令： aijaij為頂點為頂點vivi鄰接到頂點鄰接到頂點vjvj邊的條數(shù)邊的條數(shù) 稱稱(aij)nxn(aij)nxn為為D D的鄰接矩陣，記作的鄰接矩陣，記作A(D)A(D) 鄰接矩陣的性質(zhì)鄰接矩陣的性質(zhì) 每列元素之和為每列元素之和為結(jié)點的入度結(jié)點的入度，即，即 aij aijd d+ +

49、(vi)(vi)，i i1 1，2 2，n n 所有所有列的和列的和 aij aij d d+ +(vi) (vi) m m ，等于邊數(shù)，等于邊數(shù) 每行元素之和為結(jié)點的出度每行元素之和為結(jié)點的出度，所有行的和也等于邊數(shù)，所有行的和也等于邊數(shù) 鄰接矩陣中元素鄰接矩陣中元素 aij aij 反映了反映了有向圖中結(jié)點有向圖中結(jié)點vivi到到vjvj通路長度為通路長度為1 1的的條數(shù)條數(shù)A(D)A(D)中所有元素之和為中所有元素之和為D D中長度為中長度為1 1的（邊）通路總條數(shù)的（邊）通路總條數(shù)。 主對角線的元素值為圖中結(jié)點主對角線的元素值為圖中結(jié)點vivi長度為長度為1 1 的的環(huán)的條數(shù)環(huán)的條數(shù)

50、利用利用A(D)A(D)確定出確定出D D中中長度為長度為L L的通路數(shù)和回路數(shù)的通路數(shù)和回路數(shù), ,就需要用到鄰接矩就需要用到鄰接矩陣的陣的冪次運算冪次運算A A2 2中的元素值中的元素值bijbij是結(jié)點是結(jié)點vivi到到vjvj長度為長度為2 2 的通路條數(shù)的通路條數(shù)：A A3 3矩陣中的矩陣中的C Cijij元素值，表示了從到長度恰為元素值，表示了從到長度恰為3 3的通路條數(shù)目的通路條數(shù)目A A的的L L次冪次冪A AL L(L1)(L1)中元素中元素c cijij為為D D中中vivi到到vjvj長度為長度為L L的通路數(shù)，的通路數(shù)， 其中其中ciicii為為vivi到自身長度為到自

51、身長度為L L的回路數(shù)的回路數(shù)設(shè)設(shè)B BL LA + AA + A2 2十十+A+AL L (L1) (L1)， 則則BLBL中元素中元素 bij bij為為D D中長度小于或等于中長度小于或等于L L的的通路數(shù)通路數(shù)， 其中主對角線上元素值為其中主對角線上元素值為D D中長度小于或等于中長度小于或等于L L的回路數(shù)的回路數(shù)主要掌握：對于給出的圖能準確得到其鄰接矩陣主要掌握：對于給出的圖能準確得到其鄰接矩陣 能計算鄰接矩陣各次冪能計算鄰接矩陣各次冪 能利用鄰接矩陣及其各次冪得出圖的各結(jié)點到另外結(jié)點能利用鄰接矩陣及其各次冪得出圖的各結(jié)點到另外結(jié)點長度為長度為d d的通路（回路）條數(shù)的通路（回路）

52、條數(shù) 各個結(jié)點的出度及入度各個結(jié)點的出度及入度習題：習題：P291 1P291 1、3 3、5 5、8 8、1414、4343、4444、4545、4646、4747 11 11、歐拉圖與哈密頓圖、歐拉圖與哈密頓圖1 1）歐拉圖）歐拉圖定義：給定一個無向圖定義：給定一個無向圖G G= 。( (a a) )穿程圖穿程圖G G中的每條邊一次且僅一次中的每條邊一次且僅一次的通路，定義為該圖的通路，定義為該圖G G的歐拉通路。的歐拉通路。( (b b) )穿程圖穿程圖G G中的每條邊一次且僅一次的回路，定義為該圖中的每條邊一次且僅一次的回路，定義為該圖G G的歐拉回路。的歐拉回路。( (c c) )具

53、有具有歐拉回路歐拉回路的圖，稱為的圖，稱為歐拉圖歐拉圖 具有具有歐拉通路歐拉通路而無歐拉回路的圖稱為而無歐拉回路的圖稱為半歐拉圖半歐拉圖2 2）性質(zhì)）性質(zhì) 每一個歐拉圖都必定是個連通無向圖每一個歐拉圖都必定是個連通無向圖連通無向圖連通無向圖G G中中沒有奇度結(jié)點沒有奇度結(jié)點，當且僅當圖，當且僅當圖G G是個歐拉圖是個歐拉圖 無向圖無向圖G G是半歐拉圖當且僅當是半歐拉圖當且僅當G G是連通的且是連通的且G G中中恰有兩個奇度數(shù)結(jié)點恰有兩個奇度數(shù)結(jié)點3 3）哈密頓圖）哈密頓圖定義：給定一個無向圖定義：給定一個無向圖G G= ( (a a) )穿程圖穿程圖G G中的中的每個結(jié)點一次且僅一次的每個結(jié)

54、點一次且僅一次的通路，稱為該圖通路，稱為該圖G G的哈密頓通路的哈密頓通路(b)(b)穿程圖穿程圖G G中的中的每個結(jié)點一次且僅一次的回路每個結(jié)點一次且僅一次的回路，定義為該圖，定義為該圖G G的哈密頓回路。的哈密頓回路。(c)(c)具有哈密頓回路的圖。稱為哈密頓圖。具有哈密頓通路但不具有哈密頓回具有哈密頓回路的圖。稱為哈密頓圖。具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密頓圖路的圖稱為半哈密頓圖4 4）性質(zhì)：）性質(zhì)： 每一個哈密頓圖都必定是個連通無向圖每一個哈密頓圖都必定是個連通無向圖 哈密頓通路是一條初級通路哈密頓通路是一條初級通路 哈密頓回路是初級回路哈密頓回路是初級回路要求掌握：定義

55、及其性質(zhì)要求掌握：定義及其性質(zhì)1212、樹、樹1 1）定義：）定義： 連通無回路連通無回路（初級回路或簡單回路）的無向圖稱為無向（初級回路或簡單回路）的無向圖稱為無向樹，或簡稱樹。常用樹，或簡稱樹。常用T T表示樹，平凡圖稱為平凡樹表示樹，平凡圖稱為平凡樹 在無向樹中，在無向樹中，懸掛頂點稱為樹葉懸掛頂點稱為樹葉，度數(shù)大于或等于，度數(shù)大于或等于2 2的頂點稱為的頂點稱為分支結(jié)點分支結(jié)點 樹的等價定義樹的等價定義 (2) G (2) G中任中任意兩個頂點之間存在惟一的路徑意兩個頂點之間存在惟一的路徑 (3) G (3) G中中無回路且無回路且 m = n - 1 m = n - 1 (4) G

56、(4) G是是連通的且連通的且 m = n - 1 m = n - 12 2）樹的性質(zhì)）樹的性質(zhì) 對于給定的無向圖對于給定的無向圖樹是樹是邊數(shù)最小的連通圖邊數(shù)最小的連通圖（mn-1mn-1mn-1則有回路）則有回路） 結(jié)點的度：結(jié)點的度： d(vi) = 2 m =d(vi) = 2 m =2(n-1)2(n-1) 設(shè)設(shè)T T是是n n階非平凡的無向樹，則階非平凡的無向樹，則T T中至少有兩片樹葉中至少有兩片樹葉 主要掌握：主要掌握：樹的定義樹的定義 樹的性質(zhì)樹的性質(zhì) 習題類型：習題類型： p318 2 p318 2、4 4、1313五、五、代數(shù)結(jié)構(gòu)部分代數(shù)結(jié)構(gòu)部分1 1、二元運算的一般性質(zhì)、

57、二元運算的一般性質(zhì)對以下的各個性質(zhì)要有四個實際的運算作為模型來理解對以下的各個性質(zhì)要有四個實際的運算作為模型來理解）交換律：）交換律： 如果對于任意的如果對于任意的x x，ySyS都有都有 x xy = yy = yx x 則稱運算在則稱運算在S S上是可交換的，或者說運算在上是可交換的，或者說運算在S S上適合交換律。上適合交換律。2 2）結(jié)合律）結(jié)合律 設(shè)為設(shè)為S S上的二元運算，如果對于任意的上的二元運算，如果對于任意的x x，y y，zSzS都有都有: : (x (xy) y) z = xz = x(y (y z) z) 則稱運算則稱運算 在在S S上是可結(jié)合的，或者說運算上是可結(jié)合的

58、，或者說運算 在在S S上適合結(jié)合律上適合結(jié)合律3 3）等冪律）等冪律 設(shè)設(shè) 為為S S上的二元運算，如果對于任意的上的二元運算，如果對于任意的xSxS都有都有 x xx xx x 則稱該運算則稱該運算 適合冪等律適合冪等律如果如果S S中的某些中的某些x x滿足滿足x xx=xx=x，則稱，則稱x x為運算的冪等元為運算的冪等元如果如果S S上的二元運算適合冪等律，則上的二元運算適合冪等律，則S S中的所有元素都是冪等元中的所有元素都是冪等元 4 4）分配律（一種運算對另一種運算而言）分配律（一種運算對另一種運算而言） 設(shè)設(shè) 和和 o o 是是S S上的兩個二元運算，上的兩個二元運算， 如果

59、對任意的如果對任意的x x，y y，zSzS有有 x x(y o z)(y o z)(x(xy) o(xy) o(xz) (z) (左分配律左分配律) ) (y o z) (y o z) x = (y x = (yx) o(zx) o(zx) (x) (右分配律右分配律) ) 則稱運算對則稱運算對 o o 是可分配的，也稱對是可分配的，也稱對 o o 適合分配律適合分配律5 5）吸收律）吸收律 （一種運算對另一種運算而言）（一種運算對另一種運算而言） 設(shè)設(shè) o o 和是和是S S上兩個可交換的二元運算，上兩個可交換的二元運算，如果對于任意的如果對于任意的x x，ySyS都有都有 x x(x o

60、 y)(x o y)x x o(xx x o(xy )=xy )=x 則稱則稱o o和滿足吸收律和滿足吸收律 對以上的各個公理要有四個實際的運算作為模型來對以上的各個公理要有四個實際的運算作為模型來6 6）單位元（幺元）單位元（幺元）對任何對任何xSxS都有都有: : e el l x = x x = x ( (或或 x x e er r = x = x ) ) 則稱則稱e el l( (或或e er r) )是是S S中關(guān)于運算的一個中關(guān)于運算的一個左單位元左單位元( (或或右單位元右單位元) )若若eSeS關(guān)于運算既是左單位元又是右單位元，關(guān)于運算既是左單位元又是右單位元， 則稱則稱e e