離散試卷有答案-(1)(完整版)
【正文】 權(quán) （ ） 注：哈夫曼算法見書本（P292） 6．解：設(shè)T有x個4度結(jié)點，則T的結(jié)點總數(shù) ，邊數(shù) 由握手定理 得 解得 所以結(jié)點總數(shù) 7． （1）－++d－h(huán)247。4．畫圖:(1)一個既沒有歐拉回路，又沒有哈密爾頓回路的圖； （2）一個具有歐拉回路和哈密爾頓回路的圖，并具體指出這兩個回路。6．用kruskal算法求得下圖G的一棵最小生成樹為 。 C．平面圖的子圖一定是平面圖 。 D．樹的子圖一定是樹。v8圖Gv1v2v3v4v512961248105711v6v737．設(shè)連通平面圖G有4個面，9條邊，則G有 個結(jié)點。 ,3,6，8,10,11的最優(yōu)二元樹并計算此最優(yōu)樹的權(quán)。gji＋247。若存在一條邊 （u,v）, u,v , 由于樹中任意兩個結(jié)點之間僅存在唯一一條基本通路，故這條基本通路就是他們之間的短程線，設(shè)v0到u 的短程線為 ，則其長度為k+1,是偶數(shù)，因為（u,v），所以 ，v 是 到 v 的一條通路，且該通路的長度k+2 為奇數(shù)，從而它不是基本通路， 故v必與某個相同，從而 是G中的一條基本通路，這與G 是樹矛盾。證明： (1)
外語相關(guān)推薦
鄂ICP備17016276號-1