離散圖論部分習(xí)題ppt課件-資料下載頁(yè)
2025-04-29 03:20本頁(yè)面
【正文】 ,b4),(a4,b3)}。 (a3) 20 a1 a2 a3 a4 b1 b2 b3 b4 b5 V1 V2 (*) (a2) (a2) (b1) (b3) ④ 從 a3出發(fā) ， 把 b4標(biāo)記成 (a3)， 因?yàn)?b4是非飽和點(diǎn) ， 說明已找到一條增長(zhǎng)通路： a2b1a3b4。 再用增長(zhǎng)通路中不屬于 M的邊代替屬于 M的邊 ， 于是得到對(duì)集 。 M′= {(a1,b5),(a2,b1), (a3,b4),(a4,b3)}。 (a3) 從 M′= {(a1,b5),(a2,b1), (a3,b4),(a4,b3)}開始 ， 重復(fù)上述過程 ， 直到找不出 M的增長(zhǎng)通路為止 。 由于 V1中已沒有 M的非 飽和點(diǎn) ， 所以 M′就是所求的最大對(duì)集 。 21 a1 a2 a3 a4 b1 b2 b3 b4 b5 ↓ 從 M′ = {(a1,b5),(a2,b1), ),(a3,b4),(a4,b3)}開始 ， 重復(fù)上述過程 ， 直到找不出 M的增長(zhǎng)通路為止 。 由于 V1中已沒有 M的非 飽和點(diǎn) ， 所以 M′就是所求的最大對(duì)集 。 22 14. 完全二分圖 Km, n=(V1,V2,E)共有多少條邊 ? 解 : 因?yàn)?V1中每個(gè)頂點(diǎn)都與 V2 中每個(gè)頂點(diǎn)鄰接 , 所以 V1 中每個(gè)頂點(diǎn)關(guān)聯(lián) |V2| = n 條邊 。 而 V1 中有 m個(gè)頂點(diǎn) , 所以 Km, n共有 mn條邊。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1