離散數(shù)學(xué)圖論部分綜合練習(xí)(編輯修改稿)
2024-09-01 10:36 本頁面
【文章內(nèi)容簡(jiǎn)介】 4，a3, a1，a4, a5，a5, a2}（1）試給出G的圖形表示；（2）判斷圖G是強(qiáng)連通圖、單側(cè)連通圖還是弱連通圖？2．設(shè)圖G=V，E，V={ v1，v2，v3，v4，v5}，E={ (v1, v2)，(v1, v3)，(v2, v3)，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) }，試（1）畫出G的圖形表示； （2）求出每個(gè)結(jié)點(diǎn)的度數(shù)；（3）畫出圖G的補(bǔ)圖的圖形．3．設(shè)G=V，E，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，試（1）給出G的圖形表示；（2）求出每個(gè)結(jié)點(diǎn)的度數(shù)；（3）畫出其補(bǔ)圖的圖形．4．圖G=V, E，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，對(duì)應(yīng)邊的權(quán)值依次為4及5，試（1）畫出G的圖形； （2）求出G權(quán)最小的生成樹及其權(quán)值．5．設(shè)有一組權(quán)為2,3,5,7,11,13,17,19,23,29,31,試（1）畫出相應(yīng)的最優(yōu)二叉樹； （2）計(jì)算它們的權(quán)值．6．畫一棵帶權(quán)為1, 2, 2, 3, 4的最優(yōu)二叉樹,計(jì)算它的權(quán)．五、證明題1．若無向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)一定是連通的．2．設(shè)G是一個(gè)n階無向簡(jiǎn)單圖，n是大于等于2的奇數(shù)．證明圖G與它的補(bǔ)圖中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等． 3．設(shè)連通圖G有k個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加條邊才能使其成為歐拉圖．參考解答一、單項(xiàng)選擇題1．C 2．C 3．A 4．D 5．D 6．C 7．A 8．D 9．A 10．A二、填空題1．15 2．{f}，{c，e} 3．W163。|S|4．所有結(jié)點(diǎn)的度數(shù)全為偶數(shù) 5．等于出度6．n為奇數(shù) 7．ve+r =2 8．3 9．e=v1 10．4 11．512．3 13．0三、判斷說明題 1．解：正確． 因?yàn)閳DG為連通的，且其中每個(gè)頂點(diǎn)的度數(shù)為偶數(shù)． 2．解：（1）圖G1是歐拉圖． 因?yàn)閳DG1中每個(gè)結(jié)點(diǎn)的度數(shù)都是偶數(shù)．圖G2是漢密爾頓圖．因?yàn)閳DG2存在一條漢密爾頓回路（不惟一
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1