離散數(shù)學圖論部分綜合練習-資料下載頁
2025-08-05 10:36本頁面
【正文】 十六所示：ooooooooo3271355111734oo1602910ooo231942oo17o24o5331ooo9565方法（Huffman）：從2,3,5,7,11,13,17,19,23,29,31中選2,3為最低層結點，并從權數(shù)中刪去，再添上他們的和數(shù)，即5,5,7,11,13,17,19,23,29,31； 再從5,5,7,11,13,17,19,23,29,31中選5,5為倒數(shù)第2層結點，并從上述數(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層結點，并從 如圖十六上述數(shù)列中刪去，再添上他們的和數(shù)，即17,17,24,19,23,29,31； ……（2）權值為：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)二叉樹如圖十七 如圖十七它的權為：1180。3+2180。3+2180。2+3180。2+4180。2=27五、證明題1．證明：用反證法．設G中的兩個奇數(shù)度結點分別為u和v．假設u和v不連通，即它們之間無任何通路，則G至少有兩個連通分支G1，G2，且u和v分別屬于G1和G2，于是G1和G2各含有一個奇數(shù)度結點．．因而u和v一定是連通的．2．證明：設，．則是由n階無向完全圖的邊刪去E所得到的．所以對于任意結點，u在G和中的度數(shù)之和等于u在中的度數(shù)．由于n是大于等于2的奇數(shù)，從而的每個結點都是偶數(shù)度的（度），于是若在G中是奇數(shù)度結點，則它在中也是奇數(shù)度結點．故圖G與它的補圖中的奇數(shù)度結點個數(shù)相等． 3．證明：，任何圖中度數(shù)為奇數(shù)的結點必是偶數(shù)，可知k是偶數(shù)．，圖G是歐拉圖的充分必要條件是圖G不含奇數(shù)度結點．因此只要在每對奇數(shù)度結點之間各加一條邊，使圖G的所有結點的度數(shù)變?yōu)榕紨?shù)，成為歐拉圖．故最少要加條邊到圖G才能使其成為歐拉圖．8
環(huán)評公示相關推薦
鄂ICP備17016276號-1