離散數(shù)學(xué)圖論部分綜合練習(xí)-資料下載頁(yè)
2025-08-05 10:36本頁(yè)面
【正文】 十六所示：ooooooooo3271355111734oo1602910ooo231942oo17o24o5331ooo9565方法（Huffman）：從2,3,5,7,11,13,17,19,23,29,31中選2,3為最低層結(jié)點(diǎn)，并從權(quán)數(shù)中刪去，再添上他們的和數(shù)，即5,5,7,11,13,17,19,23,29,31； 再?gòu)?,5,7,11,13,17,19,23,29,31中選5,5為倒數(shù)第2層結(jié)點(diǎn)，并從上述數(shù)列中刪去，再添上他們的和數(shù)，即7,10,11,13,17,19,23,29,31；然后，從7,10,11,13,17,19,23,29,31中選7,10和11,13為倒數(shù)第3層結(jié)點(diǎn)，并從 如圖十六上述數(shù)列中刪去，再添上他們的和數(shù)，即17,17,24,19,23,29,31； ……（2）權(quán)值為：2180。6+3180。6+5180。5+7180。4+11180。4+13180。4+17180。3+19180。3+23180。3+29180。3+31180。2 =12+18+25+28+44+52+51+57+69+87+62=5056．ooooooooo1223347512解：最優(yōu)二叉樹(shù)如圖十七 如圖十七它的權(quán)為：1180。3+2180。3+2180。2+3180。2+4180。2=27五、證明題1．證明：用反證法．設(shè)G中的兩個(gè)奇數(shù)度結(jié)點(diǎn)分別為u和v．假設(shè)u和v不連通，即它們之間無(wú)任何通路，則G至少有兩個(gè)連通分支G1，G2，且u和v分別屬于G1和G2，于是G1和G2各含有一個(gè)奇數(shù)度結(jié)點(diǎn)．．因而u和v一定是連通的．2．證明：設(shè)，．則是由n階無(wú)向完全圖的邊刪去E所得到的．所以對(duì)于任意結(jié)點(diǎn)，u在G和中的度數(shù)之和等于u在中的度數(shù)．由于n是大于等于2的奇數(shù)，從而的每個(gè)結(jié)點(diǎn)都是偶數(shù)度的（度），于是若在G中是奇數(shù)度結(jié)點(diǎn)，則它在中也是奇數(shù)度結(jié)點(diǎn)．故圖G與它的補(bǔ)圖中的奇數(shù)度結(jié)點(diǎn)個(gè)數(shù)相等． 3．證明：，任何圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)必是偶數(shù)，可知k是偶數(shù)．，圖G是歐拉圖的充分必要條件是圖G不含奇數(shù)度結(jié)點(diǎn)．因此只要在每對(duì)奇數(shù)度結(jié)點(diǎn)之間各加一條邊，使圖G的所有結(jié)點(diǎn)的度數(shù)變?yōu)榕紨?shù)，成為歐拉圖．故最少要加條邊到圖G才能使其成為歐拉圖．8
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1