下載本文檔
版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、圖論復(fù)習(xí)題答案一、 判斷題,對(duì)打,錯(cuò)打1 無(wú)向完全圖是正則圖。( )2 零圖是平凡圖。( )3 連通圖的補(bǔ)圖是連通圖. ( )4 非連通圖的補(bǔ)圖是非連通圖。( )5 若連通無(wú)向簡(jiǎn)單圖G中無(wú)圈,則每條邊都是割邊。( )6 若無(wú)向簡(jiǎn)單圖G是(n,m)圖,并且m=n-1,則G是樹(shù)。( )7 任何樹(shù)都至少有2片樹(shù)葉。( )8 任何無(wú)向圖G都至少有一個(gè)生成樹(shù)。( )9 非平凡樹(shù)是二分圖 。( )10 所有樹(shù)葉的級(jí)均相同的二元樹(shù)是完全二元樹(shù)。( )11任何一個(gè)位置二元樹(shù)的樹(shù)葉都對(duì)應(yīng)唯一一個(gè)前綴碼。( )12是歐拉圖也是哈密頓圖。( )13 二分圖的對(duì)偶圖是歐拉圖。()14平面圖的對(duì)偶圖是連通圖。( )15
2、設(shè)G*是平面圖G的對(duì)偶圖,則G*的面數(shù)等于G的頂點(diǎn)數(shù)。( )二、填空題1無(wú)向完全圖K6有 15 條邊。2有三個(gè)頂點(diǎn)的所有互不同構(gòu)的簡(jiǎn)單無(wú)向圖有 4 個(gè)。3設(shè)樹(shù)T中有2個(gè)3度頂點(diǎn)和3個(gè)4度頂點(diǎn),其余的頂點(diǎn)都是樹(shù)葉,則T中有 10 片樹(shù)葉。4若連通無(wú)向圖G是(n,m)圖,T是G的生成樹(shù),則基本割集有 n-1 個(gè),基本圈有 m-n+1 個(gè)。5設(shè)連通無(wú)向圖G有k個(gè)奇頂點(diǎn),要使G變成歐拉圖,在G中至少要加 k / 2 條邊。6連通無(wú)向圖G是(n,m)圖,若G是平面圖,則G有 m-n+2 個(gè)面。abcde圖1三、解答題1有向圖D如圖1所示,利用D的鄰接矩陣及其冪運(yùn)算求解下列問(wèn)題:(1) D中長(zhǎng)度等于3的通
3、路和回路各有多少條。(2) 求D的可達(dá)性矩陣。(3) 求D的強(qiáng)分圖。解: (1)abcde圖1M= M2= M3= M4=由M3可知,D中長(zhǎng)度等于3的通路有5條,長(zhǎng)度等于3的回路有3條。(2)I+M+M2+M3+M4=+ + = D的可達(dá)性矩陣為R=B(I+M+M2+M3+M4)=(3)RT = RRT =由矩陣RRT可知,該有向圖的強(qiáng)分圖有:a, b,d,e, c2 畫(huà)出有1個(gè)4次頂點(diǎn),2個(gè)2次頂點(diǎn),4個(gè)1次頂點(diǎn)的所有非同構(gòu)的樹(shù)。3 用Kruskal算法求圖2所示帶權(quán)圖的最小生成樹(shù),并計(jì)算它的權(quán)。1294368571011C(T)=2512336227541394 試畫(huà)出帶權(quán)為1,2,3, 4,5,7,的最優(yōu)二元樹(shù),并計(jì)算它的權(quán)。m(T)=(1+2)4+33+(7+4+5)2=535 出席某次國(guó)際學(xué)術(shù)報(bào)告會(huì)的六個(gè)成員被分在一組。他們的情況是:會(huì)講漢語(yǔ)、法語(yǔ)和日語(yǔ);會(huì)講德語(yǔ)、日語(yǔ)和俄語(yǔ);會(huì)講英語(yǔ)和法語(yǔ);會(huì)講漢語(yǔ)和西班牙語(yǔ);會(huì)講英語(yǔ)和德語(yǔ);會(huì)講俄語(yǔ)和西班牙語(yǔ)。怎樣把他們安排在一張圓桌旁坐下,使得每個(gè)人都能和他兩旁的人交談?解 構(gòu)造無(wú)向圖,其中,則得無(wú)向圖如圖所示。由該圖得一條哈密頓回路:,即為滿足要求的安排。四、證明題1 設(shè)T是完全二元樹(shù),T中有m條弧和t片樹(shù)葉,證明:m = 2(t-1)。證明: 設(shè)完全二元樹(shù)T有n個(gè)頂點(diǎn)。因?yàn)樗衪片樹(shù)葉,所以除樹(shù)葉以外的頂點(diǎn)有個(gè)。由于完全二元
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 停車(chē)位建設(shè)項(xiàng)目可行性報(bào)告
- 大學(xué)生讀書(shū)心得筆記
- 租房合同范本集錦15篇
- 啟動(dòng)儀式領(lǐng)導(dǎo)講話稿(集合15篇)
- 手機(jī)銷(xiāo)售辭職報(bào)告15篇
- 關(guān)于小學(xué)個(gè)人教師述職報(bào)告十篇
- 數(shù)學(xué)教學(xué)心得體會(huì)
- 房地產(chǎn)銷(xiāo)售個(gè)人工作總結(jié)(匯編15篇)
- 幼兒園班主任辭職報(bào)告錦集7篇
- 新媒體營(yíng)銷(xiāo)(第三版) 課件 項(xiàng)目二 新媒體營(yíng)銷(xiāo)定位與策劃
- 有機(jī)肥料及微生物肥料生產(chǎn)技術(shù)的創(chuàng)新與發(fā)展
- 銀行市場(chǎng)份額提升方案
- 鎮(zhèn)海煉化線上測(cè)評(píng)試題
- 2024寧夏高級(jí)電工證考試題庫(kù)電工理論考試試題(全國(guó)通用)
- 浙江省溫州市2022-2023學(xué)年八年級(jí)上學(xué)期數(shù)學(xué)期末試題(含答案)
- 2023年客訴工程師年度總結(jié)及下一年計(jì)劃
- 廣東省佛山市2022-2023學(xué)年三年級(jí)上學(xué)期語(yǔ)文期末試卷(含答案)
- 網(wǎng)絡(luò)運(yùn)維從入門(mén)到精通29個(gè)實(shí)踐項(xiàng)目詳解
- 2024屆黃岡市啟黃中學(xué)中考試題猜想數(shù)學(xué)試卷含解析
- 揚(yáng)州育才小學(xué)2023-2024一年級(jí)上冊(cè)數(shù)學(xué)期末復(fù)習(xí)卷(一)及答案
- 04某污水處理廠630kW柔性支架光伏發(fā)電項(xiàng)目建議書(shū)
評(píng)論
0/150
提交評(píng)論