離散圖論部分習(xí)題ppt課件(參考版)
2025-05-02 03:20本頁(yè)面
【正文】 而 V1 中有 m個(gè)頂點(diǎn) , 所以 Km, n共有 mn條邊。 由于 V1中已沒(méi)有 M的非 飽和點(diǎn) ， 所以 M′就是所求的最大對(duì)集 。 由于 V1中已沒(méi)有 M的非 飽和點(diǎn) ， 所以 M′就是所求的最大對(duì)集 。 M′= {(a1,b5),(a2,b1), (a3,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) ， 說(shuō)明已找到一條增長(zhǎng)通路： a2b1a3b4。 再用增長(zhǎng)通路中不屬于 M的邊代替屬于 M的邊 ， 于是得到對(duì)集 。 ③ 從 b1出發(fā) ， 把 a3標(biāo)記成 (b1)， 從 b3出發(fā)把 a4標(biāo)記成 (b3)。 ① 用 (*)標(biāo)記 V1中所有 M的非飽和點(diǎn) (只有一點(diǎn) a2)。 （ ） （ 1） 1， 1， 2， 3， 5 （ 2） 1， 2， 3， 4， 5 （ 3） 1， 3， 1， 3， 2 （ 4） 1， 2， 3， 4， 6 答案（ 2） 19 13. 如圖是二部圖 ， 求其最大匹配 。 解 : 由于頂點(diǎn)為 n的無(wú)向完全圖的邊數(shù)為 . 2)1( ?nn設(shè) G的自補(bǔ)圖為 G’,則 G與 G’的邊數(shù)相等 . 設(shè)它們的邊數(shù)各為 m,于是有 m+m= 2)1( ?nn即 m=n(n1)/4, 而 m為正整數(shù) ,所以要么 n=4k或 n=4k+1, 所以不存在 3個(gè)頂點(diǎn)和 6個(gè)頂點(diǎn)的自補(bǔ)圖 . 9. 是否存在 3個(gè)頂點(diǎn)和 6個(gè)頂點(diǎn)的自補(bǔ)圖？ 證明 :由于度數(shù)為奇數(shù)的頂點(diǎn)必為偶數(shù)個(gè) ,所以度數(shù)為 5
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1