離散圖論部分習(xí)題ppt課件-wenkub
2023-05-14 03:20:40 本頁(yè)面
【正文】 Kn 共有 條邊。 推論 2： n階有向完全圖， 共有 n(n1) 條邊。 Km, n=(V1,V2,E)共有多少條邊 ? 1. 有 9個(gè)人一起打乒乓球，已知他們每人至少與其中另外3個(gè)人各打過(guò)一場(chǎng)球，試證明至少有一人不止和 3個(gè)人打過(guò)球 . 證明 : 用 9 個(gè)頂點(diǎn) vi表示 9個(gè)人 ,頂點(diǎn)間的一條邊表示這兩人打過(guò)一場(chǎng)球 ,可構(gòu)成一個(gè)無(wú)向圖 ,若每個(gè)人僅和其余 3個(gè)人各打過(guò)一場(chǎng)球，則 d(vi) =3,而此時(shí)圖 G的奇數(shù)度點(diǎn)是 9個(gè) ,即奇數(shù)個(gè) ,因此產(chǎn)生矛盾 ,于是至少有一人不止和 3個(gè)人打過(guò)球 . 思考題答案： G有 12條邊， G中有 6個(gè) 3度結(jié)點(diǎn)，其余結(jié)點(diǎn)度數(shù) 均為 2，問 G中有多少個(gè)結(jié)點(diǎn)？ 解 :設(shè)圖中有 x個(gè)結(jié)點(diǎn) ,由握手定理可得 : 6 3+(x6) 2=2 12 于是 x=9, 所以 G中有 9個(gè)結(jié)點(diǎn) . 3. 設(shè) n階圖 G中有 m條邊 ,每個(gè)頂點(diǎn)的度數(shù)不是 k就是 k+1,若 G中有 Nk個(gè) k度頂點(diǎn) ,Nk+1個(gè) k+1度的頂點(diǎn) ,試求出頂點(diǎn)個(gè)數(shù) Nk的表達(dá)式 . 解 :由于 Nk k+(nNk) (k+1)=2m 于是 :Nk=n(k+1)2m. 4. 試畫出 4階 3條邊的所有非同構(gòu)的無(wú)向簡(jiǎn)單圖 5. 判斷下述每一對(duì)圖是否同構(gòu) : (1) 度數(shù)列不同 不同構(gòu) (2) 不同構(gòu) 入 (出 )度列不同 (3) 度數(shù)列相同 但不同構(gòu) 解 : 根據(jù)自補(bǔ)圖的定義其對(duì)應(yīng)的完全圖的邊數(shù)是 2m. 6. 一個(gè)圖是自補(bǔ)圖 ,設(shè)頂點(diǎn)數(shù)為 n,其邊數(shù)為 m,其對(duì)應(yīng)的 完全圖的邊數(shù)是多少 ? 7. 設(shè)無(wú)向簡(jiǎn)單連通圖 G有 16條邊 ,有 3個(gè) 4度頂點(diǎn) ,4個(gè) 3度頂點(diǎn) ,其余頂點(diǎn)的度數(shù)都小于 3,問 G至少有多少個(gè)頂點(diǎn) ,至多有多少個(gè)頂點(diǎn) ? 解 : 由題設(shè)可知 ,圖 G中有 16條邊 ,所以圖 G中各點(diǎn)的度數(shù) 之和為 32. 又由于圖 G中有 3個(gè) 4度頂點(diǎn)和 4個(gè) 3度頂點(diǎn) ,這 7個(gè)點(diǎn)的度數(shù) 之和為 24,而圖 G中其余點(diǎn)的度數(shù)小于 3,即圖 G中其余點(diǎn)的 度數(shù)只可能是 2或 1(由于圖 G是連通圖 ,所以無(wú)零度點(diǎn) ). 由此
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1