路與回路ppt課件-文庫(kù)吧資料
2025-05-09 18:30本頁(yè)面
【正文】 ) 。 ? 割邊 定義 設(shè)無(wú)向 圖 G =V,E是 連通圖 ,若有邊集 E1?E，使圖 G中刪除了 E1的所有邊后，所得到的子圖是不連通圖，而刪除了 E1的任何真子集后，所得到的子圖仍是連通圖，則稱(chēng) E1是 G的一個(gè) 邊割集(cutset of edges) 。 任取 u?V1，w?V2， 因?yàn)?G是連通的，故在 G中必有一條連結(jié) u和 w的路 C，但 u和 w在 G’中屬于兩個(gè)不同的連通分支，故 u和 w必不連通，因此 C必須通過(guò) v， 故 u和 w之間的任意一條路都通過(guò) v 。 (1)若 G是平凡圖則 V1=?， k(G)=0 (2)k(Kn)=n1 (3)若圖存在割點(diǎn)，則 k(G)=1 (4)規(guī)定非連通圖的連通度 k(G)=0 v5 v1 v2 v3 v4 v5 v1 v3 v4 點(diǎn)割集 V1={v2} 一個(gè)連通 無(wú)向圖 G的結(jié)點(diǎn) v是割點(diǎn)的充分必要條件是存在兩個(gè)結(jié)點(diǎn) u和 w,使得結(jié)點(diǎn) u和 w的每一條路都通過(guò) v 。 s a b c d a b c d b a 上圖中 :{b,f}, {b,g}, {f,k},{k,g}以及 {a,d,i,l}是點(diǎn)割集 . 不存在割點(diǎn) . 點(diǎn)連通度：是為了產(chǎn)生一個(gè)不連通圖需要?jiǎng)h去的點(diǎn)的最少數(shù)目，也稱(chēng)為連通度，記為 k(G) 。 若某一個(gè)點(diǎn)構(gòu)成一個(gè)點(diǎn)割集，則稱(chēng)該點(diǎn)為 割點(diǎn) 。 刪除邊 ： 所謂在圖中刪除某條邊 ，即是把該邊刪除。 見(jiàn) 281頁(yè)圖 圖 (a)是連通圖 對(duì)于連通圖，常常由于刪除了圖中的點(diǎn)或邊，而影響了圖的連通性。否則稱(chēng) G是非連通圖或分離圖。 把子圖 G(V1) , G(V2) , … , G(Vm)稱(chēng)為圖 G的 連通分支 （ connected ponents） ,圖 G的連通分支數(shù)記為 W(G) 。 （ 2）由定義不難看出，無(wú)向圖中結(jié)點(diǎn)之間的連通關(guān)系 R={u,v|u,v∈ V且 u與 v連通 }是自反的，對(duì)稱(chēng)的，傳遞的，因而 R是 V上的 等價(jià)關(guān)系 。 v1到 v3最短的路為 v1e2v3 二、無(wú)向圖的連通性 連通 定義 在無(wú)向 圖 G中，如果從結(jié)點(diǎn) u和結(jié)點(diǎn) v之間若 存在一條路，則稱(chēng)結(jié)點(diǎn) u和結(jié)點(diǎn) v是連通的 （ connected） 。 如在圖 5個(gè)結(jié)點(diǎn)。 定理 : Vs Vk Vj Vs Vs Vk Vj Vj Vk ? 定理 如果從結(jié)點(diǎn) vj到 vk存在一條路，該路上的結(jié)點(diǎn)序列是 vj…v i…v k，如果在這條路中有 L條邊，則序列中必有 L+1個(gè)結(jié)點(diǎn)，若 Ln1，則必有結(jié)點(diǎn) vs，它在序列中不止出現(xiàn)一次，即必有結(jié)點(diǎn)序列 vj…v s…v s…v k，在路中去掉從 vs到 vs的這些邊，仍是 vj到 vk的一條路，但此路比原來(lái)的路邊數(shù)要少，如此重復(fù)進(jìn)行下去，必可得到一條從 vj到 vk的不多于 n1條邊的路。 結(jié)點(diǎn)數(shù) =邊數(shù) +1 0v 1v 2v nvne1?iv ivie回路 (closed walk) : 當(dāng) v0=vn時(shí) v0e1 v1e2 … vi1eivi… envn 結(jié)點(diǎn)數(shù) =邊數(shù) 0v1?nv1?iv iv1v 2vne1eneie2env圖 路： v1e2v3e3v2e3v3e4v2e6v5e7v3 跡
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1