【正文】 a3 a4 b1 b2 b3 b4 b5 V1 V2 15. 當(dāng) n取何值時(shí)，完全圖 Kn是歐拉圖？ 16. 證明：對(duì)于任意一個(gè)無(wú)向連通圖，必能從任意一點(diǎn)出發(fā)經(jīng)過(guò)圖中每邊恰好兩次再回到出發(fā)點(diǎn)。 (a3) 從 M′= {(a1,b5),(a2,b1), (a3,b4),(a4,b3)}開(kāi)始 ， 重復(fù)上述過(guò)程 ， 直到找不出 M的增長(zhǎng)通路為止 。 M′={(a1,b5),(a2,b1),(a3,b4),(a4,b3)}。 三、掌握有向完全圖和無(wú)向完全圖及推論 2)1( ?nn推論 1： n階無(wú)向完全圖 Kn 共有 條邊。 ③ 從 b1出發(fā) ， 把 a3標(biāo)記成 (b1)， 從 b3出發(fā)把 a4標(biāo)記成 (b3)。 由于 V1中已沒(méi)有 M的非 飽和點(diǎn) ， 所以 M′就是所求的最大對(duì)集 。 解 : 由于頂點(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的頂點(diǎn)個(gè)數(shù)必為偶數(shù) ,即可能為 0、 9個(gè)頂點(diǎn) ,所以 6度的頂點(diǎn)個(gè)數(shù)分別為 1,于是圖 G中至少有 5個(gè) 6度的頂點(diǎn)或至少有 6個(gè) 5度的頂點(diǎn) . 10. 無(wú)向圖 G中有 9個(gè)頂點(diǎn) ,每個(gè)頂點(diǎn)的度數(shù)不是 5就是 6, 證明 :圖 G中至少有 5個(gè) 6度的頂點(diǎn)或至少有 6個(gè) 5度的頂點(diǎn) . 11. 設(shè)有向簡(jiǎn)單 D的度數(shù)列為 2， 2， 3， 3，入度列為 0， 0， 2， 3，試求 D的出度列。 至多有 15個(gè)頂點(diǎn) : 3個(gè) 4度點(diǎn) ,4個(gè) 3