特殊圖習(xí)題及答案

第六章特殊圖題六一.判斷圖一哪些是歐拉圖？對(duì)不是歐拉圖至少要加多少條邊才能成為歐拉圖？圖一解答:,一,二二.畫一個(gè)無(wú)向歐拉圖使它具有:(一)偶數(shù)個(gè)頂點(diǎn),偶數(shù)條邊。(二)奇數(shù)個(gè)頂點(diǎn),奇數(shù)條邊。(三)偶數(shù)個(gè)頂點(diǎn),奇數(shù)條邊。(四)奇數(shù)個(gè)頂點(diǎn),偶數(shù)條邊。解答:(一)四四(二)（三(三)(四)三.判斷彼得松圖是否為歐拉圖,是否為哈密頓圖。若不是,至少加幾條新邊才能使它成為歐拉圖？又至少加幾條新邊才能使它變成哈密頓圖?五條新邊可以成為歐拉圖加一條邊可以成為哈密頓圖。四.判斷圖二所示四個(gè)圖是否能一筆畫出。一三零離散數(shù)學(xué)圖二解答:五.(一)畫一個(gè)歐拉回路與哈密頓回路地;(二)畫一個(gè)歐拉回路,但沒(méi)有哈密頓回路圖;(三)畫一個(gè)沒(méi)有歐拉回路,但有哈密頓回路地;(四)畫一個(gè)既沒(méi)有歐拉回路也沒(méi)有哈密頓回路地解答:(一)三（三(二)(三)(四)六.設(shè)有a,b,c,d,e,,g七個(gè),它們分別會(huì)講如下各種語(yǔ)言:a會(huì)講英語(yǔ)b會(huì)講漢語(yǔ)與英c會(huì)講英語(yǔ)西班牙語(yǔ)與俄語(yǔ)d會(huì)講漢語(yǔ)與日語(yǔ)e會(huì)講德語(yǔ)與西班牙語(yǔ)f會(huì)講法語(yǔ),日語(yǔ)與俄語(yǔ)g地座位安排在圓桌旁使得每個(gè)均能與它身邊談。解答:分別用a,,c,,e,,g七個(gè)結(jié)點(diǎn)表示七個(gè),若兩可以談（使用同一種語(yǔ)言）,則在代表它們地結(jié)點(diǎn)之間連一條無(wú)向邊如下圖a地座位安排在圓桌旁使得每個(gè)均能與它身邊談只需找出一條哈密頓回路如abdfgeca。七.際象棋地馬走日字,即在x,y格子地馬可以走到xy,xy二地任何一個(gè)走遍所有地格子且每個(gè)格子只走一次稱作馬周游。證明:一三一第六章特殊圖(一)在三四棋盤上存在馬地周游。(二)在三三棋盤上不存在馬周游。兩個(gè)頂點(diǎn)之間相鄰當(dāng)且僅當(dāng)馬可以從對(duì)應(yīng)一個(gè)格子跳到另一個(gè)格子。因此,地周游問(wèn)題等價(jià)于圖地哈密頓通路存在問(wèn)題。(一)三四棋盤可以使用以下走法（格子數(shù)字代表走一一二三四九六七二一零五八(二)三三棋盤不可能存在哈密頓通路,因此心格子對(duì)應(yīng)頂點(diǎn)是孤立點(diǎn)。八.一棵無(wú)向樹T有五片樹葉,三個(gè)二度分支點(diǎn),其余地分支點(diǎn)都是三度結(jié)點(diǎn),問(wèn)T有幾個(gè)結(jié)點(diǎn)？T有n個(gè)結(jié)點(diǎn)根據(jù)握手定理有三二三(n五二(n得。九.無(wú)向樹T有八片樹葉二個(gè)三度分支點(diǎn)其余分支點(diǎn)都是四度頂點(diǎn)問(wèn)有幾個(gè)頂點(diǎn)？解答:假設(shè)T有n個(gè)頂點(diǎn),根據(jù)握手定理有得=一二一零.一棵無(wú)向樹T有ii,k)個(gè)i度分支點(diǎn)其余頂點(diǎn)都是樹葉問(wèn)有幾片樹葉？T有n個(gè)頂點(diǎn)xnxnnn根據(jù)握手定理,二三kk有二(nx二nn從而得xnkn二二in。二三k三kii三若n(n階無(wú)向樹T最大度T至少為幾最多為幾？解答:至少為二至多為n-一。T三所示。回答以下問(wèn)題:(一)T是幾叉樹？(二)T樹高為幾？(三)T有幾個(gè)內(nèi)點(diǎn)？(四)T有幾個(gè)分支點(diǎn)？一三二離散數(shù)學(xué)圖三解答:(一)T是四叉樹。(二)T樹高為四。(三)T有八個(gè)內(nèi)點(diǎn)。(四)T有七個(gè)分支點(diǎn)。畫一棵權(quán)為最優(yōu)二叉樹并計(jì)算出它權(quán)。四)四六七)三九)二。下面給出各符號(hào)串集合哪些是前綴碼？一二三四b,c,dd,dc,aba,abb,五b,c,a,aa,ac,abc,abb,解答:A:是A:是A:否A:是A:否。一二三四五四地二叉樹產(chǎn)生一個(gè)二元前綴碼。圖四解答:{零零零,零零一,一零零零,一零一,。設(shè)七個(gè)字母在通信出現(xiàn)地頻率如下:一三三第六章特殊圖a:三五%b:二零%c:一五%d:一零%e:一零%f:五%g:五%構(gòu)造一組表示它們二元前綴碼使得傳送地二制位最少。二元前綴碼為{零零零零,零零零一,零零一,零一,一零零,一零一,。圖五地二叉樹表示一個(gè)算式。(一)用序遍歷法還原算式。(二)用前序遍歷法寫出該算式波蘭符號(hào)法表達(dá)式。(三)用后序遍歷法寫出該算式逆波蘭符號(hào)法表達(dá)式。圖五解答:(一)(二)(三)一八.用二叉有序正則樹表示代數(shù)表達(dá)式解答:一三四離散數(shù)學(xué)一九.六所示圖,重新找面嵌入,使外部面次數(shù)分別為三與。圖六解答:外部面次數(shù)為三外部面地次數(shù)為四七所示兩面圖面邊界與次數(shù)并驗(yàn)證歐拉公式。圖七地次數(shù)為D(r)D(r)D(r)D(r)D(r)D(r)。一二三四五六右圖各面次數(shù)為D(r)D(r)D(r)D(