離散數(shù)學(xué)-第16章-樹PPT課件

1、 (1)(2) 如果如果G是樹是樹，則，則G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑。 存在性。存在性。 由由G的連通性及定理的連通性及定理14.514.5的推論（的推論（在在n階圖階圖G中，若從頂點(diǎn)中，若從頂點(diǎn)vi到到 vj( (vi vj) )存在通路，則存在通路，則vi到到vj 一定存在長度小于等于一定存在長度小于等于n-1-1的初的初 級(jí)通路級(jí)通路( (路徑路徑) )）可知，）可知， u, ,vV，u與與v之間存在路徑。之間存在路徑。 唯一性唯一性（反證法）。（反證法）。 若路徑不是唯一的，設(shè)若路徑不是唯一的，設(shè)1 1與與2 2都是都是u到到v的路徑，的路徑，

2、易知必存在由易知必存在由1 1和和2 2上的邊構(gòu)成的回路，上的邊構(gòu)成的回路， 這與這與G中無回路矛盾。中無回路矛盾。 (2)(3) 如果如果G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑， 則則G中無回路且中無回路且mn- -1 1。 首先證明首先證明 G中無回路。中無回路。 若若G中存在關(guān)聯(lián)某頂點(diǎn)中存在關(guān)聯(lián)某頂點(diǎn)v的環(huán)，的環(huán)， 則則v到到v存在長為存在長為0 0和和1 1的兩條路經(jīng)的兩條路經(jīng) ( (注意初級(jí)回路是路徑的特殊情況注意初級(jí)回路是路徑的特殊情況) )， 這與已知矛盾。這與已知矛盾。 若若G中存在長度大于或等于中存在長度大于或等于2 2的圈，的圈， 則圈上任何兩個(gè)

3、頂點(diǎn)之間都存在兩條不同的路徑，則圈上任何兩個(gè)頂點(diǎn)之間都存在兩條不同的路徑， 這也與已知矛盾。這也與已知矛盾。 (2)(3) 如果如果G中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑中任意兩個(gè)頂點(diǎn)之間存在唯一的路徑， 則則G中無回路且中無回路且mn- -1 1。 其次證明其次證明 mn-1-1。（歸納法）。（歸納法） n1 1時(shí)，時(shí)，G為平凡圖，結(jié)論顯然成立。為平凡圖，結(jié)論顯然成立。 設(shè)設(shè)nk( (k1)1)時(shí)結(jié)論成立，時(shí)結(jié)論成立， 當(dāng)當(dāng)n= =k+1+1時(shí)，設(shè)時(shí)，設(shè)e( (u, ,v) )為為G中的一條邊，中的一條邊， 由于由于G中無回路，所以中無回路，所以G- -e e為兩個(gè)連通分支為兩個(gè)連通分支G1 1

4、、G2 2。 設(shè)設(shè)ni、mi分別為分別為Gi中的頂點(diǎn)數(shù)和邊數(shù)，則中的頂點(diǎn)數(shù)和邊數(shù)，則nik ，i1,21,2， 由歸納假設(shè)可知由歸納假設(shè)可知mini-1-1，于是，于是 mm1 1+ +m2 2+1+1n1 1-1+-1+n2 2-1+1-1+1n1 1+ +n2 2-1-1n-1-1。 只需證明只需證明G是連通的。（采用反證法）是連通的。（采用反證法） 假設(shè)假設(shè)G是不連通的，由是不連通的，由s( (s2) )個(gè)連通分支個(gè)連通分支G1,G2,Gs組成組成 ，并且并且Gi中均無回路，因而中均無回路，因而Gi全為樹全為樹。 由由(1)(1)( (2)2)( (3)3)可知可知，mini- -1。于

5、是于是， 由于由于s2，與與mn- -1矛盾矛盾。 111 (1) sss iii iii mmnnsns (3)(4) 如果如果G中無回路且中無回路且mn-1-1，則，則G是連通的且是連通的且mn -1-1。 如果G是連通的且mn1，則G是連通的且G中 任何邊均為橋。 只需證明只需證明G中每條邊均為橋中每條邊均為橋。 eE，均有均有| |E( (G- -e)|)|n- -1- -1n- -2， 由習(xí)題十四題由習(xí)題十四題49（若若G是是n階階m條邊的無向連通圖，則條邊的無向連通圖，則mn- -1）可可 知知，G- -e已不是連通圖已不是連通圖， 所以所以，e為橋?yàn)闃颉?(4)(5) 如果G是連

6、通的且G中任何邊均為橋，則G中沒有回路， 但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊，在所得 圖中得到唯一的一個(gè)含新邊的圈。 因?yàn)橐驗(yàn)镚中每條邊均為橋，刪掉任何邊，將使中每條邊均為橋，刪掉任何邊，將使G變成不連通圖，變成不連通圖， 所以，所以，G中沒有回路，也即中沒有回路，也即G中無圈。中無圈。 又由于又由于G連通，所以連通，所以G為樹，由為樹，由(1) (2)可知，可知， u,vV，且且uv，則則u與與v之間存在唯一的路徑之間存在唯一的路徑， 則則( (u,v) )（( (u,v) )為加的新邊為加的新邊）為為G中的圈，中的圈， 顯然圈是唯一的。顯然圈是唯一的。 (5)(6) 如果G中沒有回路，但

7、在任何兩個(gè)不同的頂點(diǎn)之 間加一條新邊，在所得圖中得到唯一的一個(gè)含 新邊的圈，則G是樹。 只需證明只需證明G是連通的。是連通的。 u,vV，且且uv，則新邊則新邊( (u,v) )G產(chǎn)生唯一的圈產(chǎn)生唯一的圈C， 顯然有顯然有C -(-(u,v) )為為G中中u到到v的通路，故的通路，故uv， 由由u,v的任意性可知，的任意性可知，G是連通的。是連通的。 (6)(1) 第二節(jié) 生成樹 對(duì)應(yīng)生成樹的弦分別為對(duì)應(yīng)生成樹的弦分別為 e6 6, ,e7 7, ,e8 8, ,e10 10, ,e1111。 。 設(shè)它們對(duì)應(yīng)的基本回路分別設(shè)它們對(duì)應(yīng)的基本回路分別 為為C1 1, ,C2 2, ,C3 3, ,

8、C4 4, ,C5 5，從對(duì)應(yīng)，從對(duì)應(yīng) 的弦開始，按逆時(shí)針（也可的弦開始，按逆時(shí)針（也可 都按順時(shí)針）的順序?qū)懗鏊及错槙r(shí)針）的順序?qū)懗鏊?們，分別為們，分別為 此圖的圈秩為此圖的圈秩為5 5，基本回路系統(tǒng)為，基本回路系統(tǒng)為 C1 1, ,C2 2, ,C3 3, ,C4 4, ,C5 5 。 無向連通圖無向連通圖G的圈秩與生成樹的選取無關(guān)，但不同生成樹的圈秩與生成樹的選取無關(guān)，但不同生成樹 對(duì)應(yīng)的基本回路系統(tǒng)可能不同。對(duì)應(yīng)的基本回路系統(tǒng)可能不同。 求下圖中的求下圖中的基本回路系統(tǒng)。基本回路系統(tǒng)。 舉例 C1e6e4e5C2e7e2e1C3e8e9e2e1C4e10e3e5e2C5e11e3e

9、5e2e9 樹枝為樹枝為e1 1, ,e2 2, ,e3 3, ,e4 4, ,e5 5, ,e9 9。 設(shè)它們對(duì)應(yīng)的基本割集分別為設(shè)它們對(duì)應(yīng)的基本割集分別為 S1 1, ,S2 2, ,S3 3, ,S4 4, ,S5 5, ,S6 6。 此圖的割集秩為此圖的割集秩為6 6，基本割集系統(tǒng)為，基本割集系統(tǒng)為 S1 1, ,S2 2, ,S3 3, ,S4 4, ,S5 5, ,S6 6 。 S1 1 e1,e7 7,e8 8 無向連通圖無向連通圖G的割集秩與生成樹的選取無關(guān)，但不同生成的割集秩與生成樹的選取無關(guān)，但不同生成 樹對(duì)應(yīng)的基本割集系統(tǒng)可能不同。樹對(duì)應(yīng)的基本割集系統(tǒng)可能不同。 求下圖中的求下圖中的基本基本割集割集系統(tǒng)。系統(tǒng)。 舉例 S2 2 e2,e7 7,e8 8,e10 10,e1111 S3 3 e3,e10 10,e1111 S4