離散數(shù)學(xué)復(fù)習(xí)華師計(jì)算機(jī)學(xué)院PPT課件

1、1第三部分 代數(shù)結(jié)構(gòu) 主要內(nèi)容l 代數(shù)系統(tǒng): 二元運(yùn)算及其性質(zhì)、代數(shù)系統(tǒng)和子代數(shù)l 半群與群: 半群、獨(dú)異點(diǎn)、群l 環(huán)與域: 環(huán)、整環(huán)、域第1頁(yè)/共76頁(yè)2第九章 代數(shù)系統(tǒng) 主要內(nèi)容 二元運(yùn)算及其性質(zhì)l 一元和二元運(yùn)算定義及其實(shí)例l 二元運(yùn)算的性質(zhì) 代數(shù)系統(tǒng)l 代數(shù)系統(tǒng)定義及其實(shí)例l 子代數(shù)l 積代數(shù) 代數(shù)系統(tǒng)的同態(tài)與同構(gòu)第2頁(yè)/共76頁(yè)3基本要求l 判斷給定集合和運(yùn)算能否構(gòu)成代數(shù)系統(tǒng)l 判斷給定二元運(yùn)算的性質(zhì)l 求而二元運(yùn)算的特異元素l 了解同類型和同種代數(shù)系統(tǒng)的概念l 了解子代數(shù)的基本概念l 計(jì)算積代數(shù)l 判斷函數(shù)是否為同態(tài)映射和同構(gòu)映射第3頁(yè)/共76頁(yè)4一、二元運(yùn)算及其性質(zhì) 定義9.1

2、設(shè)S為集合，函數(shù)f：SSS 稱為S上的二元運(yùn)算，簡(jiǎn) 稱為二元運(yùn)算l S中任何兩個(gè)元素都可以進(jìn)行運(yùn)算，且運(yùn)算的結(jié)果惟一l S中任何兩個(gè)元素的運(yùn)算結(jié)果都屬于S，即S對(duì)該運(yùn)算封閉 定義9.2 設(shè)S為集合，函數(shù) f:SS 稱為S上的一元運(yùn)算，簡(jiǎn) 稱一元運(yùn)算. 第4頁(yè)/共76頁(yè)5二元運(yùn)算的性質(zhì) 定義9.3 設(shè)為S上的二元運(yùn)算, (1) 若對(duì)任意x,yS 有 xy=yx, 則稱運(yùn)算在S上滿足交換律. (2) 若對(duì)任意x,y,zS有 (xy)z=x(yz), 則稱運(yùn)算在S上滿足結(jié) 合律. (3) 若對(duì)任意xS 有 xx=x, 則稱運(yùn)算在S上滿足冪等律.定義9.4 設(shè)和 為S上兩個(gè)不同的二元運(yùn)算, (1) 若

3、對(duì)任意x,y,zS有 (x y)z=(xz) (yz)， z(x y)=(zx) (zy), 則稱運(yùn)算對(duì) 運(yùn)算滿足分配律. (2) 若 和 都可交換,且對(duì)任意x,yS有 x(x y)=x，x (xy)=x, 則稱和 運(yùn)算滿足吸收律. 第5頁(yè)/共76頁(yè)6特異元素：?jiǎn)挝辉?、零?定義9.5 設(shè)為S上的二元運(yùn)算, (1) 如果存在el (或er)S，使得對(duì)任意 xS 都有 elx = x (或 xer = x)， 則稱el (或er)是S中關(guān)于運(yùn)算的左(或右)單位元. 若eS關(guān)于運(yùn)算既是左單位元又是右單位元，則稱e為S上 關(guān)于運(yùn)算的單位元. 單位元也叫做幺元. (2) 如果存在 l (或 r)S，使

4、得對(duì)任意 xS 都有 l x = l (或 x r = r)， 則稱 l (或 r)是S 中關(guān)于運(yùn)算的左(或右)零元. 若 S 關(guān)于運(yùn)算既是左零元又是右零元，則稱為S上關(guān) 于運(yùn)算的零元.第6頁(yè)/共76頁(yè)7可逆元素和逆元 (3) 設(shè)為S上的二元運(yùn)算, 令e為S中關(guān)于運(yùn)算的單位元. 對(duì)于xS，如果存在yl (或yr)S使得 ylx=e（或xyr=e） 則稱yl (或 yr)是x的左逆元（或右逆元）. 關(guān)于運(yùn)算，若yS 既是 x 的左逆元又是 x 的右逆元，則稱 y為x的逆元. 如果 x 的逆元存在，就稱 x 是可逆的.第7頁(yè)/共76頁(yè)8惟一性定理 定理9.1 設(shè)為S上的二元運(yùn)算，el和er分別為S

5、中關(guān)于運(yùn)算的 左和右單位元，則el = er = e為S上關(guān)于運(yùn)算的惟一的單位元. 類似地可以證明關(guān)于零元的惟一性定理. 注意：l 當(dāng) |S| 2，單位元與零元是不同的；l 當(dāng) |S| = 1時(shí)，這個(gè)元素既是單位元也是零元. 定理9.2 設(shè)為S上可結(jié)合的二元運(yùn)算, e為該運(yùn)算的單位元, 對(duì)于xS 如果存在左逆元 yl 和右逆元 yr, 則有 yl = yr= y, 且 y 是 x 的惟一的逆元.第8頁(yè)/共76頁(yè)99.2 代數(shù)系統(tǒng) 定義9.6 非空集合S和S上k個(gè)一元或二元運(yùn)算f1, f2, fk組成 的系統(tǒng)稱為代數(shù)系統(tǒng), 簡(jiǎn)稱代數(shù)，記做. 構(gòu)成代數(shù)系統(tǒng)的成分：l 集合（也叫載體，規(guī)定了參與運(yùn)算

6、的元素）l 運(yùn)算（這里只討論有限個(gè)二元和一元運(yùn)算）l 代數(shù)常數(shù)（通常是與運(yùn)算相關(guān)的特異元素：如單位元等） 研究代數(shù)系統(tǒng)時(shí)，如果把運(yùn)算具有它的特異元素也作為系統(tǒng) 的性質(zhì)之一，那么這些特異元素可以作為系統(tǒng)的成分，叫做 代數(shù)常數(shù). 第9頁(yè)/共76頁(yè)10子代數(shù)系統(tǒng) 定義9.8設(shè)V=是代數(shù)系統(tǒng)，B是S的非空子 集，如果B對(duì)f1, f2, , fk 都是封閉的，且B和S含有相同的代 數(shù)常數(shù)，則稱是V的子代數(shù)系統(tǒng)，簡(jiǎn)稱子代 數(shù). 有時(shí)將子代數(shù)系統(tǒng)簡(jiǎn)記為B.說(shuō)明：l 子代數(shù)和原代數(shù)是同種的代數(shù)系統(tǒng)l 對(duì)于任何代數(shù)系統(tǒng)V=，其子代數(shù)一定存在. 第10頁(yè)/共76頁(yè)11第十章 群與環(huán) 主要內(nèi)容l 群的定義與性質(zhì)l

7、子群與群的陪集分解l 循環(huán)群與置換群l 環(huán)與域第11頁(yè)/共76頁(yè)12基本要求l 判斷或證明給定集合和運(yùn)算是否構(gòu)成半群、獨(dú)異點(diǎn)和群l 熟悉群的基本性質(zhì)l 能夠證明G的子集構(gòu)成G的子群l 熟悉陪集的定義和性質(zhì)l 熟悉拉格朗日定理及其推論，學(xué)習(xí)簡(jiǎn)單應(yīng)用l 會(huì)求循環(huán)群的生成元及其子群l 熟悉n元置換的表示方法、乘法以及n元置換群l 能判斷給定代數(shù)系統(tǒng)是否為環(huán)和域 第12頁(yè)/共76頁(yè)13l 半群、獨(dú)異點(diǎn)與群的定義l 半群、獨(dú)異點(diǎn)、群的實(shí)例l 群中的術(shù)語(yǔ)l 群的基本性質(zhì)10.1 群的定義與性質(zhì)第13頁(yè)/共76頁(yè)14半群、獨(dú)異點(diǎn)與群的定義 定義10.1 (1) 設(shè)V=是代數(shù)系統(tǒng)， 為二元運(yùn)算，如果 運(yùn)算是可

8、 結(jié)合的，則稱V為半群. (2) 設(shè)V=是半群，若eS是關(guān)于 運(yùn)算的單位元，則稱V 是含幺半群，也叫做獨(dú)異點(diǎn). 有時(shí)也將獨(dú)異點(diǎn)V 記作 V=. (3) 設(shè)V=是獨(dú)異點(diǎn)，eS關(guān)于 運(yùn)算的單位元，若 aS，a1S，則稱V是群. 通常將群記作G. 第14頁(yè)/共76頁(yè)15有關(guān)群的術(shù)語(yǔ) 定義10.2 (1) 若群G是有窮集，則稱G是有限群，否則稱為無(wú) 限群. 群G 的基數(shù)稱為群 G 的階，有限群G的階記作|G|. (2) 只含單位元的群稱為平凡群. (3) 若群G中的二元運(yùn)算是可交換的，則稱G為交換群或阿貝 爾 (Abel) 群.定義10.4 設(shè)G是群，aG，使得等式 ak=e 成立的最小正整數(shù)k 稱為

9、a 的階，記作|a|=k，稱 a 為 k 階元. 若不存在這樣的正整數(shù) k，則稱 a 為無(wú)限階元.第15頁(yè)/共76頁(yè)16群的性質(zhì)：冪運(yùn)算規(guī)則 定理10.1 設(shè)G 為群，則G中的冪運(yùn)算滿足： (1) aG，(a1)1=a (2) a,bG，(ab)1=b1a1 (3) aG，anam = an+m，n, mZ (4) aG，(an)m = anm，n, mZ (5) 若G為交換群，則 (ab)n = anbn.第16頁(yè)/共76頁(yè)17群的性質(zhì)：消去律；元素的階 定理10.3 G為群，則G中適合消去律，即對(duì)任意a,b,cG 有 (1) 若 ab = ac，則 b = c. (2) 若 ba = ca

10、，則 b = c. 例例 5 設(shè)設(shè)G是群，是群，a,bG是有限階元是有限階元. 證明證明 (1) |b 1ab| = |a| (2) |ab| = |ba|定理10.4 G為群，aG且 |a| = r. 設(shè)k是整數(shù)，則 (1) ak = e當(dāng)且僅當(dāng)r | k (2 )|a 1| = |a|第17頁(yè)/共76頁(yè)1810.2 子群與群的陪集分解 定義10.5 設(shè)G是群，H是G的非空子集， (1) 如果H關(guān)于G中的運(yùn)算構(gòu)成群，則稱H是G的子群, 記作HG. (2) 若H是G的子群，且HG，則稱H是G的真子群，記作HG.例如 nZ (n是自然數(shù)) 是整數(shù)加群 的子群. 當(dāng)n1時(shí),nZ是Z的真子群.對(duì)任何

11、群G都存在子群. G和e都是G的子群，稱為G的平凡子群. 第18頁(yè)/共76頁(yè)19子群判定定理 定理10.5（判定定理一） 設(shè)G為群，H是G的非空子集，則H是G的子群當(dāng)且僅當(dāng) (1) a,bH有abH (2) aH有a1H.定理定理10.6 （判定定理二）（判定定理二）設(shè)設(shè)G為群，為群，H是是G的非空子集的非空子集. H是是G的子群當(dāng)且僅當(dāng)?shù)淖尤寒?dāng)且僅當(dāng) a,bH有有ab 1H. 定理定理10.7 （判定定理三）（判定定理三） 設(shè)設(shè)G為群，為群，H是是G的的非空非空有窮子集，則有窮子集，則H是是G的子群當(dāng)且僅當(dāng)?shù)淖尤寒?dāng)且僅當(dāng) a,bH有有abH. 第19頁(yè)/共76頁(yè)20典型子群的實(shí)例定義10.6

12、 設(shè)G為群，aG，令H=ak| kZ，則H是G的子群，稱為由 a 生成的子群，記作.定義定義10.7 設(shè)設(shè)G為群為群,令令 C=a| aG xG(ax=xa)，則則C是是G的子群，稱為的子群，稱為G的的中心中心. 例例6 設(shè)設(shè)G是群，是群，H,K是是G的子群的子群. 證明證明(1) HK也是也是G的子群的子群(2) HK是是G的子群當(dāng)且僅當(dāng)?shù)淖尤寒?dāng)且僅當(dāng) H K 或或 K H第20頁(yè)/共76頁(yè)21陪集 定義10.9 設(shè)H是G的子群，aG.令Ha=ha | hH 稱Ha是子群H在G中的右陪集. 稱a為Ha的代表元素. 定理定理10.8 設(shè)設(shè)H是群是群G的子群，則的子群，則 (1) He = H(

13、2) aG 有有aHa定理定理10.9 設(shè)設(shè)H是群是群G的子群，則的子群，則 a,bG有有 aHb ab 1H Ha=Hb第21頁(yè)/共76頁(yè)22推論 推論 設(shè)H是群G的子群, 則 (1) a,bG，Ha = Hb 或 HaHb = (2) Ha | aG = G 證明：由等價(jià)類性質(zhì)可得. 定理定理10.10 設(shè)設(shè)H是群是群G的子群，在的子群，在G上定義二元關(guān)系上定義二元關(guān)系R： a,bG, R ab 1H則則 R是是G上的等價(jià)關(guān)系，且上的等價(jià)關(guān)系，且aR = Ha.第22頁(yè)/共76頁(yè)23左陪集的定義與性質(zhì) 設(shè)G是群，H是G的子群，H 的左陪集，即aH = ah | hH，aG 關(guān)于左陪集有下述

14、性質(zhì)： (1) eH = H (2) aG，aaH (3) a,bG，abH b1aH aH=bH (4) 若在G上定義二元關(guān)系R， a,bG，R b1aH 則R是G上的等價(jià)關(guān)系，且aR = aH. (5) aG，H aH 第23頁(yè)/共76頁(yè)24Lagrange定理 定理10.12 （Lagrange）設(shè)G是有限群，H是G的子群，則 |G| = |H|G:H 其中G:H 是H在G中的不同右陪集(或左陪集) 數(shù)，稱為H在 G 中的指數(shù). 推論1 設(shè)G是n階群，則 aG，|a|是n的因子，且有an = e.推論2 對(duì)階為素?cái)?shù)的群G，必存在aG使得G = . 第24頁(yè)/共76頁(yè)25Lagrange定

15、理的應(yīng)用 命題：如果群 G 只含 1 階和 2 階元，則 G 是Abel群. 例8 證明 6 階群中必含有 3 階元. 證 設(shè)a為G中任意元素，有a 1 = a. 任取 x, yG，則 xy = (xy) 1 = y 1x 1 = yx， 因此G是Abel群. 證 設(shè)G是6 階群，則G中元素只能是1階、2階、3階或6階.若G中含有6 階元，設(shè)為a，則 a2是3 階元. 若G中不含6 階元，下面證明G中必含有3階元. 如若不然，G中只含1階和2階元，即 aG，有a2=e，由命題知G是Abel群. 取G中2階元 a 和 b，a b，令 H = e, a, b, ab，則H 是 G的子群，但 |H|

16、 = 4，|G| = 6，與拉格朗日定理矛盾. 第25頁(yè)/共76頁(yè)2610.3 循環(huán)群與置換群 定義10.10 設(shè)G是群，若存在aG使得 G=ak| kZ 則稱G是循環(huán)群，記作G=，稱 a 為G 的生成元. 循環(huán)群的分類：n 階循環(huán)群和無(wú)限循環(huán)群. 設(shè)G=是循環(huán)群，若a是n 階元，則 G = a0=e, a1, a2, , an 1 那么|G| = n，稱 G 為 n 階循環(huán)群. 若a 是無(wú)限階元，則 G = a0=e, a1, a2, 稱 G 為無(wú)限循環(huán)群. 第26頁(yè)/共76頁(yè)27循環(huán)群的生成元 定理10.13 設(shè)G=是循環(huán)群. (1) 若G是無(wú)限循環(huán)群，則G只有兩個(gè)生成元，即a和a1. (

17、2) 若G是 n 階循環(huán)群，則G含有(n)個(gè)生成元. 對(duì)于任何小 于n且與 n 互質(zhì)的數(shù)r0,1,n-1, ar是G的生成元.(n)成為歐拉函數(shù)，例如 n=12，小于或等于12且與12互素的 正整數(shù)有4個(gè)： 1, 5, 7, 11， 所以(12)=4.第27頁(yè)/共76頁(yè)28循環(huán)群的子群 定理10.14 設(shè)G=是循環(huán)群. (1) 設(shè)G=是循環(huán)群，則G的子群仍是循環(huán)群. (2) 若G=是無(wú)限循環(huán)群，則G的子群除e以外都是無(wú)限 循環(huán)群. (3) 若G=是n階循環(huán)群，則對(duì)n的每個(gè)正因子d，G恰好含 有一個(gè)d 階子群.第28頁(yè)/共76頁(yè)2910.4 環(huán)與域 定義10.12 設(shè)是代數(shù)系統(tǒng)，+和是二元運(yùn)算.

18、 如果滿足 以下條件: (1) 構(gòu)成交換群 (2) 構(gòu)成半群 (3) 運(yùn)算關(guān)于+運(yùn)算適合分配律 則稱是一個(gè)環(huán). 通常稱+運(yùn)算為環(huán)中的加法，運(yùn)算為環(huán)中的乘法. 環(huán)中加法單位元記作 0，乘法單位元（如果存在）記作1. 對(duì)任何元素 x，稱 x 的加法逆元為負(fù)元，記作x. 若 x 存在乘法逆元的話，則稱之為逆元，記作x1. 第29頁(yè)/共76頁(yè)30定理10.16 設(shè)是環(huán)，則 (1) aR，a0 = 0a = 0(2) a,bR，( a)b = a( b) = ab(3) a,b,cR，a(b c) = ab ac， (b c)a = ba ca(4) a1,a2,.,an,b1,b2,.,bmR (n,

19、m2) babajnimjimjjnii 1111)()(環(huán)的運(yùn)算性質(zhì) 第30頁(yè)/共76頁(yè)31特殊的環(huán) 定義10.13 設(shè)是環(huán) (1) 若環(huán)中乘法 適合交換律，則稱R是交換環(huán) (2) 若環(huán)中乘法 存在單位元，則稱R是含幺環(huán) (3) 若a,bR，ab=0 a=0b=0，則稱R是無(wú)零因子環(huán) (4) 若R既是交換環(huán)、含幺環(huán)、無(wú)零因子環(huán)，則稱R是整環(huán) (5) 設(shè)R是整環(huán)，且R中至少含有兩個(gè)元素. 若aR*，其中 R*=R0，都有a1R，則稱R是域.第31頁(yè)/共76頁(yè)32第五部分 圖論本部分主要內(nèi)容l 圖的基本概念l 歐拉圖、哈密頓圖l 樹(shù)l 平面圖l 支配集、覆蓋集、獨(dú)立集、匹配與著色第32頁(yè)/共76

20、頁(yè)33第十四章 圖的基本概念 主要內(nèi)容l 圖l 通路與回路l 圖的連通性l 圖的矩陣表示l 圖的運(yùn)算 預(yù)備知識(shí)l 多重集合元素可以重復(fù)出現(xiàn)的集合l 無(wú)序集AB=(x,y) | xAyB第33頁(yè)/共76頁(yè)34基本要求l 深刻理解握手定理及推論的內(nèi)容并能靈活地應(yīng)用它們l 深刻理解圖同構(gòu)、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖、二部圖的概念以及它們的性質(zhì)及相互之間的關(guān)系l 記住通路與回路的定義、分類及表示法l 深刻理解與無(wú)向圖連通性、連通度有關(guān)的諸多概念l 會(huì)判別有向圖連通性的類型l 熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會(huì)求可達(dá)矩陣 第34頁(yè)/共76頁(yè)35相關(guān)概念1. 圖 可用G泛指圖

21、（無(wú)向的或有向的） V(G), E(G), V(D), E(D) n階圖2. 有限圖3. n 階零圖與平凡圖（1階零圖）4. 空?qǐng)D5. 用 ek 表示無(wú)向邊或有向邊6. 頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系 關(guān)聯(lián)、關(guān)聯(lián)次數(shù) 環(huán) 孤立點(diǎn)7. 頂點(diǎn)之間的相鄰與鄰接關(guān)系第35頁(yè)/共76頁(yè)36多重圖與簡(jiǎn)單圖 定義14.3 (1) 無(wú)向圖中的平行邊（大于1條）及重?cái)?shù) (2) 有向圖中的平行邊及重?cái)?shù)（注意方向性） (3) 多重圖（含平行邊的圖） (4) 簡(jiǎn)單圖（既不含邊，也不含環(huán)的圖） 在定義14.3中定義的簡(jiǎn)單圖是極其重要的概念 第36頁(yè)/共76頁(yè)37頂點(diǎn)的度數(shù)定義14.4 (1) 設(shè)G=為無(wú)向圖, vV, d(v)v的

22、度數(shù), 簡(jiǎn)稱度 (2) 設(shè)D=為有向圖, vV, d+(v)v的出度 d(v)v的入度 d(v)v的度或度數(shù) (3) (G), (G) (4) +(D), +(D), (D), (D), (D), (D) (5) 奇頂點(diǎn)度與偶度頂點(diǎn)第37頁(yè)/共76頁(yè)38mvdnii2)(1 mvdvdmvdniiniinii 111)()(,2)(且且定理定理14.1 設(shè)設(shè)G=為任意無(wú)向圖，為任意無(wú)向圖，V=v1,v2,vn, |E|=m, 則則推論 任何圖 (無(wú)向或有向) 中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù).握手定理定理14.2 設(shè)D=為任意有向圖，V=v1,v2,vn, |E|=m, 則第38頁(yè)/共76頁(yè)39圖的度

23、數(shù)列1 . V=v1, v2, , vn為無(wú)向圖G的頂點(diǎn)集，稱d(v1), d(v2), , d(vn)為G的度數(shù)列 2. V=v1, v2, , vn為有向圖D的頂點(diǎn)集， D的度數(shù)列：d(v1), d(v2), , d(vn) D的出度列：d+(v1), d+(v2), , d+(vn) D的入度列：d(v1), d(v2), , d(vn) 3. 非負(fù)整數(shù)列d=(d1, d2, , dn)是可圖化的，是可簡(jiǎn)單圖化的.易知：(2, 4, 6, 8, 10)，(1, 3, 3, 3, 4) 是可圖化的，后者又是可簡(jiǎn)單圖化的，而(2, 2, 3, 4, 5)，(3, 3, 3, 4) 都不是可簡(jiǎn)

24、單圖化的，特別是后者也不是可圖化的第39頁(yè)/共76頁(yè)40n 階完全圖與競(jìng)賽圖 定義14.6 (1) n (n1) 階無(wú)向完全圖每個(gè)頂點(diǎn)與其余頂點(diǎn)均相鄰的無(wú)向簡(jiǎn)單圖，記作 Kn. 簡(jiǎn)單性質(zhì)：邊數(shù) (2) n (n1)階有向完全圖每對(duì)頂點(diǎn)之間均有兩條方向相反的有向邊的有向簡(jiǎn)單圖. 簡(jiǎn)單性質(zhì)： (3) n (n1) 階競(jìng)賽圖基圖為Kn的有向簡(jiǎn)單圖. 簡(jiǎn)單性質(zhì)：邊數(shù)1,2)1( nnnm 1),1(2),1( nnnnm 1,2)1( nnnm 第40頁(yè)/共76頁(yè)41子圖 定義14.8 G=, G= (1) GG G為G的子圖，G為G的母圖 (2) 若GG且V=V，則稱G為G的生成子圖 (3) 若VV

25、或EE，稱G為G的真子圖 (4) V（VV且V）的導(dǎo)出子圖，記作GV (5) E（EE且E）的導(dǎo)出子圖，記作GE第41頁(yè)/共76頁(yè)42補(bǔ)圖定義14.9 設(shè)G=為n階無(wú)向簡(jiǎn)單圖，以V為頂點(diǎn)集，以所有使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱為G的補(bǔ)圖，記作 .若G , 則稱G是自補(bǔ)圖. GG第42頁(yè)/共76頁(yè)4314.2 通路與回路定義14.11 給定圖G=（無(wú)向或有向的），G中頂點(diǎn)與邊的交替序列 = v0e1v1e2elvl，vi1, vi 是 ei 的端點(diǎn).(1) 通路與回路： 為通路；若 v0=vl， 為回路，l 為回路長(zhǎng) 度.(2) 簡(jiǎn)單通路與回路：所有邊各異， 為簡(jiǎn)單通路，又若

26、v0=vl， 為簡(jiǎn)單回路(3) 初級(jí)通路(路徑)與初級(jí)回路(圈)： 中所有頂點(diǎn)各異，則稱 為初級(jí)通路(路徑)，又若除v0=vl，所有的頂點(diǎn)各不相同且所有的邊各異，則稱 為初級(jí)回路(圈)(4) 復(fù)雜通路與回路：有邊重復(fù)出現(xiàn)第43頁(yè)/共76頁(yè)44通路與回路的長(zhǎng)度 定理14.5 在n 階圖G中，若從頂點(diǎn)vi 到vj（vivj）存在通路， 則從vi 到 vj 存在長(zhǎng)度小于或等于n1 的通路. 推論 在 n 階圖G中，若從頂點(diǎn)vi 到 vj（vivj）存在通路，則 從vi 到vj 存在長(zhǎng)度小于或等于n1的初級(jí)通路（路徑）. 定理14.6 在一個(gè)n 階圖G中，若存在 vi 到自身的回路，則一 定存在vi

27、到自身長(zhǎng)度小于或等于 n 的回路. 推論 在一個(gè)n 階圖G中，若存在 vi 到自身的簡(jiǎn)單回路，則一 定存在長(zhǎng)度小于或等于n 的初級(jí)回路.第44頁(yè)/共76頁(yè)4514.3 圖的連通性無(wú)向圖的連通性(1) 頂點(diǎn)之間的連通關(guān)系：G=為無(wú)向圖 若 vi 與 vj 之間有通路，則 vivj 是V上的等價(jià)關(guān)系 R=| u,v V且uv (2) G的連通性與連通分支 若u,vV，uv，則稱G連通 V/R=V1,V2,Vk，稱GV1, GV2, ,GVk為連通分 支，其個(gè)數(shù) p(G)=k (k1)； k=1，G連通第45頁(yè)/共76頁(yè)46無(wú)向圖的連通度1. 刪除頂點(diǎn)及刪除邊 Gv 從G中將v及關(guān)聯(lián)的邊去掉 GV從

28、G中刪除V中所有的頂點(diǎn) Ge 將e從G中去掉 GE刪除E中所有邊 2. 點(diǎn)割集與邊割集 點(diǎn)割集與割點(diǎn)定義14.16 G=, VV V為點(diǎn)割集p(GV)p(G)且有極小性 v為割點(diǎn)v為點(diǎn)割集定義14.17 G=, EE E是邊割集p(GE)p(G)且有極小性 e是割邊（橋）e為邊割集第46頁(yè)/共76頁(yè)47有向圖的連通性 定義14.20 D=為有向圖 vi vj（vi 可達(dá) vj）vi 到vj 有通路 vi vj（vi 與vj 相互可達(dá)） 性質(zhì) 具有自反性(vi vi)、傳遞性 具有自反性、對(duì)稱性、傳遞性 vi 到vj 的短程線與距離 類似于無(wú)向圖中，只需注意距離表示法的不同 (無(wú)向圖中d(vi,

29、vj)，有向圖中d) 及 d無(wú)對(duì)稱性第47頁(yè)/共76頁(yè)48有向圖的連通性及分類 定義14.22 D=為有向圖 D弱連通(連通)基圖為無(wú)向連通圖 D單向連通vi,vjV，vivj 或 vjvi D強(qiáng)連通vi,vjV，vivj 易知，強(qiáng)連通單向連通弱連通 判別法 定理14.8 D強(qiáng)連通當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次 的回路 定理14.9 D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一 次的通路第48頁(yè)/共76頁(yè)49二部圖定義14.23 設(shè) G=為一個(gè)無(wú)向圖，若能將 V分成 V1和V2(V1V2=V，V1V2=)，使得 G 中的每條邊的兩個(gè)端點(diǎn)都是一個(gè)屬于V1，另一個(gè)屬于V2，則稱 G 為二部圖

30、 ( 或稱二分圖、偶圖等 )，稱V1和V2為互補(bǔ)頂點(diǎn)子集，常將二部圖G記為. 又若G是簡(jiǎn)單二部圖，V1中每個(gè)頂點(diǎn)均與V2中所有的頂點(diǎn)相鄰，則稱G為完全二部圖，記為 Kr,s，其中r=|V1|，s=|V2|. 注意，n 階零圖為二部圖. 第49頁(yè)/共76頁(yè)50有向圖的鄰接矩陣（無(wú)限制）定義14.26 設(shè)有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令為頂點(diǎn) vi 鄰接到頂點(diǎn) vj 邊的條數(shù)，稱為D的鄰接矩陣，記作A(D)，或簡(jiǎn)記為A. 性質(zhì) 的回路數(shù)的回路數(shù)中長(zhǎng)度為中長(zhǎng)度為的通路數(shù)的通路數(shù)中長(zhǎng)度為中長(zhǎng)度為1)4(1)3(,.,2 , 1),()2(,.,2 , 1

31、),()1(1)1(,)1(1)1(1)1(DaDmanjvdanivdaniiijiijjniijinjij 第50頁(yè)/共76頁(yè)51推論 設(shè)Bl=A+A2+Al（l 1），則 Bl中元素為D中長(zhǎng)度為 l 的通路總數(shù)，)(lija)(liia ninjlija11)( niliia1)( ninjlijb11)( niliib1)(定理14.11 設(shè) A為有向圖 D 的鄰接矩陣，V=v1, v2, , vn為頂點(diǎn)集，則 A 的 l 次冪 Al（l 1）中元素為D中vi 到vj長(zhǎng)度為 l 的通路數(shù)，其中為vi到自身長(zhǎng)度為 l 的回路數(shù)，而為D中長(zhǎng)度小于或等于 l 的回路數(shù)為D中長(zhǎng)度小于或等于 l

32、 的通路數(shù). 鄰接矩陣的應(yīng)用為D 中長(zhǎng)度為 l 的回路總數(shù). 第51頁(yè)/共76頁(yè)52 否否則則可可達(dá)達(dá), 1, 0jiijvvp 1101110111110001P定義14.27 設(shè)D=為有向圖. V=v1, v2, , vn, 令 有向圖的可達(dá)矩陣（無(wú)限制）稱 (pij)n n 為D的可達(dá)矩陣，記作P(D)，簡(jiǎn)記為P. 由于 vi V，vivi，所以P(D)主對(duì)角線上的元素全為1. 由定義不難看出, D 強(qiáng)連通當(dāng)且僅當(dāng) P(D)為全1矩陣. 下圖所示有向圖 D 的可達(dá)矩陣為第52頁(yè)/共76頁(yè)53第十五章 歐拉圖與哈密頓圖 主要內(nèi)容l 歐拉通路、歐拉回路、歐拉圖、半歐拉圖及其判別法l 哈密頓通

33、路、哈密頓回路、哈密頓圖、半哈密頓圖l 帶權(quán)圖、貨郎擔(dān)問(wèn)題第53頁(yè)/共76頁(yè)54基本要求 基本要求l 深刻理解歐拉圖、半歐拉圖的定義及判別定理l 深刻理解哈密頓圖、半哈密頓圖的定義. l 會(huì)用哈密頓圖的必要條件判斷某些圖不是哈密頓圖. l 會(huì)用充分條件判斷某些圖是哈密頓圖. 要特別注意的是，不能將必要條件當(dāng)作充分條件，也不要將充分條件當(dāng)必要條件. 第54頁(yè)/共76頁(yè)55歐拉圖定義 定義15.1 (1) 歐拉通路經(jīng)過(guò)圖中每條邊一次且僅一次行遍所有頂點(diǎn)的通路. (2) 歐拉回路經(jīng)過(guò)圖中每條邊一次且僅一次行遍所有頂點(diǎn)的回路. (3) 歐拉圖具有歐拉回路的圖. (4) 半歐拉圖具有歐拉通路而無(wú)歐拉回路

34、的圖. 幾點(diǎn)說(shuō)明： 規(guī)定平凡圖為歐拉圖. 歐拉通路是生成的簡(jiǎn)單通路，歐拉回路是生成的簡(jiǎn)單回路. 環(huán)不影響圖的歐拉性.第55頁(yè)/共76頁(yè)56無(wú)向歐拉圖的判別法 定理15.1 無(wú)向圖G是歐拉圖當(dāng)且僅當(dāng)G連通且無(wú)奇度數(shù)頂點(diǎn). 定理15.2 無(wú)向圖G是半歐拉圖當(dāng)且僅當(dāng)G 連通且恰有兩個(gè)奇 度頂點(diǎn).第56頁(yè)/共76頁(yè)57有向歐拉圖的判別法 定理15.3 有向圖D是歐拉圖當(dāng)且僅當(dāng)D是強(qiáng)連通的且每個(gè)頂 點(diǎn)的入度都等于出度. 定理15.4 有向圖D是半歐拉圖當(dāng)且僅當(dāng)D是單向連通的，且 D中恰有兩個(gè)奇度頂點(diǎn)，其中一個(gè)的入度比出度大1，另一個(gè) 的出度比入度大1，而其余頂點(diǎn)的入度都等于出度. 定理15.5 G是非平

35、凡的歐拉圖當(dāng)且僅當(dāng)G是連通的且為若干 個(gè)邊不重的圈之并. 第57頁(yè)/共76頁(yè)58哈密頓圖與半哈密頓圖 定義15.2 (1) 哈密頓通路經(jīng)過(guò)圖中所有頂點(diǎn)一次僅一次的通路. (2) 哈密頓回路經(jīng)過(guò)圖中所有頂點(diǎn)一次僅一次的回路. (3) 哈密頓圖具有哈密頓回路的圖. (4) 半哈密頓圖具有哈密頓通路且無(wú)哈密頓回路的圖. 幾點(diǎn)說(shuō)明： 平凡圖是哈密頓圖. 哈密頓通路是初級(jí)通路，哈密頓回路是初級(jí)回路. 環(huán)與平行邊不影響哈密頓性. 哈密頓圖的實(shí)質(zhì)是能將圖中的所有頂點(diǎn)排在同一個(gè)圈上第58頁(yè)/共76頁(yè)59無(wú)向哈密頓圖的一個(gè)必要條件 定理15.6 設(shè)無(wú)向圖G=是哈密頓圖，對(duì)于任意V1V且 V1，均有 p(GV1)

36、 |V1|推論 設(shè)無(wú)向圖G=是半哈密頓圖，對(duì)于任意的V1 V且V1均有 p(G V1) |V1|+1第59頁(yè)/共76頁(yè)60無(wú)向哈密頓圖的一個(gè)充分條件 定理15.7 設(shè)G是n階無(wú)向簡(jiǎn)單圖，若對(duì)于任意不相鄰的頂點(diǎn)vi,vj，均有 d(vi)+d(vj) n1 () 則G 中存在哈密頓通路. 推論 設(shè)G為n (n3) 階無(wú)向簡(jiǎn)單圖，若對(duì)于G中任意兩個(gè) 不相鄰的頂點(diǎn)vi,vj，均有 d(vi)+d(vj) n （） 則G中存在哈密頓回路，從而G為哈密頓圖.第60頁(yè)/共76頁(yè)61第十六章 樹(shù) 主要內(nèi)容l 無(wú)向樹(shù)及其性質(zhì)l 生成樹(shù)、最小生成樹(shù)、基本回路系統(tǒng)、基本割集系統(tǒng)l 根樹(shù)及其分類、最優(yōu)樹(shù)、最佳前綴碼

37、、波蘭符號(hào)法、逆波蘭符號(hào)法第61頁(yè)/共76頁(yè)62基本要求 基本要求l 深刻理解無(wú)向樹(shù)的定義及性質(zhì)l 熟練地求解無(wú)向樹(shù)l 準(zhǔn)確地求出給定帶權(quán)連通圖的最小生成樹(shù)l 深刻理解基本回路、基本割集的概念，并會(huì)計(jì)算l 理解根樹(shù)及其分類等概念l 會(huì)畫(huà)n階（n較小）非同構(gòu)的無(wú)向樹(shù)及根樹(shù)（1n6）l 熟練掌握求最優(yōu)樹(shù)及最佳前綴碼的方法l 掌握波蘭符號(hào)法與逆波蘭符號(hào)法第62頁(yè)/共76頁(yè)6316.1 無(wú)向樹(shù)及其性質(zhì)定義16.1 (1) 無(wú)向樹(shù)連通無(wú)回路的無(wú)向圖(2) 平凡樹(shù)平凡圖(3) 森林至少由兩個(gè)連通分支（每個(gè)都是樹(shù)）組成(4) 樹(shù)葉1度頂點(diǎn)(5) 分支點(diǎn)度數(shù)2的頂點(diǎn) 第63頁(yè)/共76頁(yè)64無(wú)向樹(shù)的等價(jià)定義 定

38、理16.1 設(shè)G=是n階m條邊的無(wú)向圖，則下面各命題 是等價(jià)的： (1) G 是樹(shù) (2) G 中任意兩個(gè)頂點(diǎn)之間存在惟一的路徑. (3) G 中無(wú)回路且 m=n1. (4) G 是連通的且 m=n1. (5) G 是連通的且 G 中任何邊均為橋. (6) G 中沒(méi)有回路，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得圖中得到惟一的一個(gè)含新邊的圈. 定理16.2 設(shè)T是n階非平凡的無(wú)向樹(shù)，則T 中至少有兩片樹(shù)葉. 第64頁(yè)/共76頁(yè)65不一定連通，也不一定不含回路，如圖所示不一定連通，也不一定不含回路，如圖所示T定義16.2 設(shè)G為無(wú)向圖(1) G的樹(shù)T 是G 的子圖并且是樹(shù)(2) G的生成樹(shù)T

39、 是G 的生成子圖并且是樹(shù)(3) 生成樹(shù)T的樹(shù)枝T 中的邊(4) 生成樹(shù)T的弦不在T 中的邊(5) 生成樹(shù)T的余樹(shù) 全體弦組成的集合的導(dǎo)出子圖T16.2 生成樹(shù)第65頁(yè)/共76頁(yè)66推論2 的邊數(shù)為m n+1. T推論3 為G的生成樹(shù)T的余樹(shù)，C為G中任意一個(gè)圈，則C與 一定有公共邊. .證 否則，C中的邊全在T中，這與T為樹(shù)矛盾. TT定理16.3 無(wú)向圖G具有生成樹(shù)當(dāng)且僅當(dāng)G連通.生成樹(shù)存在條件推論1 G為n階m條邊的無(wú)向連通圖，則m n 1. 證 必要性顯然.充分性用破圈法（注意：在圈上刪除任何一條邊，不破壞連通性）第66頁(yè)/共76頁(yè)67基本回路系統(tǒng)定理16.4 設(shè)T為G的生成樹(shù)，e為T(mén)

40、的任意一條弦，則Te中含一個(gè)只有一條弦其余邊均為T(mén)的樹(shù)枝的圈. 不同的弦對(duì)應(yīng)的圈也不同. 定義16.3 設(shè)T是n階m條邊的無(wú)向連通圖G的一棵生成樹(shù)，設(shè)e 1, e 2, , e m n+1為T(mén) 的弦. 設(shè)Cr為T(mén) 添加弦e r 產(chǎn)生的只含弦e r、其余邊均為樹(shù)枝的圈. 稱Cr為G的對(duì)應(yīng)樹(shù)T 的弦e r的基本回路或基本圈，r=1, 2, , m n+1. 并稱C1, C2, ,Cm n+1為G對(duì)應(yīng)T 的基本回路系統(tǒng)，稱m n+1為G的圈秩，記作 (G). 第67頁(yè)/共76頁(yè)68基本割集的存在 定理16.5 設(shè)T是連通圖G的一棵生成樹(shù)，e為T(mén)的樹(shù)枝，則G 中存在只含樹(shù)枝e，其余邊都是弦的割集，且不

41、同的樹(shù)枝對(duì) 應(yīng)的割集也不同.定義定義16.4 設(shè)設(shè)T是是n階連通圖階連通圖G的一棵生成樹(shù)，的一棵生成樹(shù)，e 1, e 2, , e n 1為為T(mén) 的樹(shù)枝，的樹(shù)枝，Si是是G的只含樹(shù)枝的只含樹(shù)枝e i的割集，則稱的割集，則稱Si為為G的對(duì)應(yīng)的對(duì)應(yīng)于生成樹(shù)于生成樹(shù)T由樹(shù)枝由樹(shù)枝e i生成的生成的基本割集基本割集，i=1, 2, , n 1. 并稱并稱S1,S2, , Sn 1為為G 對(duì)應(yīng)對(duì)應(yīng)T 的的基本割集系統(tǒng)基本割集系統(tǒng)，稱，稱n 1為為G的的割割集秩集秩，記作，記作 (G). 第68頁(yè)/共76頁(yè)69最小生成樹(shù)定義16.5 T是G=的生成樹(shù)(1) W(T)T各邊權(quán)之和(2) 最小生成樹(shù)G的所有生成樹(shù)中權(quán)最小的求最小生成樹(shù)的一個(gè)算法避圈法（Kruskal）設(shè)G=，將G中非環(huán)邊按權(quán)從小到大排序：e1,