離散數(shù)學(xué)圖論作業(yè)

離散數(shù)學(xué)圖論作業(yè)

ID:34816735

大?。?61.50 KB

頁(yè)數(shù):9頁(yè)

時(shí)間:2019-03-11

離散數(shù)學(xué)圖論作業(yè)_第1頁(yè)
離散數(shù)學(xué)圖論作業(yè)_第2頁(yè)
離散數(shù)學(xué)圖論作業(yè)_第3頁(yè)
離散數(shù)學(xué)圖論作業(yè)_第4頁(yè)
離散數(shù)學(xué)圖論作業(yè)_第5頁(yè)
資源描述:

《離散數(shù)學(xué)圖論作業(yè)》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)

1、離散數(shù)學(xué)11春圖論部分綜合練習(xí)輔導(dǎo)大家好!本學(xué)期的第二次教學(xué)輔導(dǎo)活動(dòng)現(xiàn)在開始,本次活動(dòng)主要是針對(duì)第二單元圖論的重點(diǎn)學(xué)習(xí)內(nèi)容進(jìn)行輔導(dǎo),方式同樣是通過(guò)講解一些典型的綜合練習(xí)作業(yè)題目,幫助大家進(jìn)一步理解和掌握?qǐng)D論的基本概念和方法.圖論作為離散數(shù)學(xué)的一部分,主要介紹圖論的基本概念、理論與方法.教學(xué)內(nèi)容主要有圖的基本概念與結(jié)論、圖的連通性與連通度、圖的矩陣表示、最短路問(wèn)題、歐拉圖與漢密爾頓圖、平面圖、對(duì)偶圖與著色、樹與生成樹、根樹及其應(yīng)用等.矚慫潤(rùn)厲釤瘞睞櫪廡賴。本次綜合練習(xí)主要是復(fù)習(xí)這一單元的主要概念與計(jì)算方法,與集合論一樣,也安排了五種類型,有

2、單項(xiàng)選擇題、填空題,判斷說(shuō)明題、計(jì)算題、證明題.這樣的安排也是為了讓同學(xué)們熟悉期末考試的題型,能夠較好地完成這一部分主要內(nèi)容的學(xué)習(xí).聞創(chuàng)溝燴鐺險(xiǎn)愛(ài)氌譴凈。下面是本學(xué)期第4,5次形考作業(yè)中的部分題目.一、單項(xiàng)選擇題單項(xiàng)選擇題主要是第4次形考作業(yè)的部分題目.第4次作業(yè)同樣也是由10個(gè)單項(xiàng)選擇題組成,每小題10分,滿分100分.在每次作業(yè)在關(guān)閉之前,允許大家反復(fù)多次練習(xí),系統(tǒng)將保留您的最好成績(jī),希望大家要多練幾次,爭(zhēng)取好成績(jī).需要提醒大家的是每次練習(xí)的作業(yè)題目可能不一樣,請(qǐng)大家一定要認(rèn)真閱讀題目.殘騖樓諍錈瀨濟(jì)溆塹籟。1.設(shè)圖G=,v

3、?V,則下列結(jié)論成立的是().A.deg(v)=2?E?B.deg(v)=?E?C.D.該題主要是檢查大家對(duì)握手定理掌握的情況.復(fù)習(xí)握手定理:定理3.1.1設(shè)G是一個(gè)圖,其結(jié)點(diǎn)集合為V,邊集合為E,則也就是說(shuō),無(wú)向圖G的結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的兩倍.正確答案:C2.設(shè)無(wú)向圖G的鄰接矩陣為,則G的邊數(shù)為().A.6B.5C.4D.3釅錒極額閉鎮(zhèn)檜豬訣錐。9主要是檢查對(duì)鄰接矩陣的概念理解是否到位.大家要復(fù)習(xí)鄰接矩陣的定義,要記住當(dāng)給定的簡(jiǎn)單圖是無(wú)向圖時(shí),鄰接矩陣為對(duì)稱的.即當(dāng)結(jié)點(diǎn)vi與vj相鄰時(shí),結(jié)點(diǎn)vj與vi也相鄰,所以連接結(jié)點(diǎn)vi與vj的

4、一條邊在鄰接矩陣的第i行第j列處和第j行第i列處各有一個(gè)1,題中給出的鄰接矩陣中共有10個(gè)1,故有10?2=5條邊.彈貿(mào)攝爾霽斃攬磚鹵廡。ooooabcdoe正確答案:B3.如右圖所示,以下說(shuō)法正確的是().A.{(a,e)}是割邊B.{(a,e)}是邊割集C.{(a,e),(b,c)}是邊割集D.{(d,e)}是邊割集先復(fù)習(xí)割邊、邊割集的定義:定義3.2.9設(shè)無(wú)向圖G=為連通圖,若有邊集E1ìE,使圖G刪除了E1的所有邊后,所得的子圖是不連通圖,而刪除了E1的任何真子集后,所得的子圖是連通圖,則稱E1是G的一個(gè)邊割集.若某個(gè)邊

5、構(gòu)成一個(gè)邊割集,則稱該邊為割邊(或橋)謀蕎摶篋飆鐸懟類蔣薔。因?yàn)閯h除答案A或B或C中的邊后,得到的圖是還是連通圖,因此答案A、B、C是錯(cuò)誤的.正確答案:Doooabcdo4.圖G如由圖所示,以下說(shuō)法正確的是().A.a(chǎn)是割點(diǎn)B.{b,c}是點(diǎn)割集C.{b,d}是點(diǎn)割集D.{c}是點(diǎn)割集主要是檢查對(duì)點(diǎn)割集、割點(diǎn)的概念理解的情況.定義3.2.7設(shè)無(wú)向圖G=為連通圖,若有點(diǎn)集V1ìV,使圖G刪除了V1的所有結(jié)點(diǎn)后,所得的子圖是不連通圖,而刪除了V1的任何真子集后,所得的子圖是連通圖,則稱V1是G的一個(gè)點(diǎn)割集.若某個(gè)結(jié)點(diǎn)構(gòu)成一個(gè)點(diǎn)割集,

6、則稱該結(jié)點(diǎn)為割點(diǎn).廈礴懇蹣駢時(shí)盡繼價(jià)騷。從圖二中刪除結(jié)點(diǎn)b,c,得到的子圖是由不連通圖,而只刪除結(jié)點(diǎn)b或結(jié)點(diǎn)c,得到的子圖仍然是連通的,由定義可以知道,{b,c}是點(diǎn)割集.所以煢楨廣鰳鯡選塊網(wǎng)羈淚。正確答案:B5.設(shè)有向圖(a)、(b)、(c)與(d)如下圖所示,則下列結(jié)論成立的是().9A.(a)是強(qiáng)連通的B.(b)是強(qiáng)連通的C.(c)是強(qiáng)連通的D.(d)是強(qiáng)連通的我們先復(fù)習(xí)強(qiáng)連通的概念:定義3.2.5在簡(jiǎn)單有向圖中,若在任何結(jié)點(diǎn)偶對(duì)中,至少?gòu)囊粋€(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)可達(dá)的,則稱圖G是單向(側(cè))連通的;鵝婭盡損鵪慘歷蘢鴛賴。若在任何結(jié)點(diǎn)偶對(duì)

7、中,兩結(jié)點(diǎn)對(duì)互相可達(dá),則稱圖G是強(qiáng)連通的.正確答案:A問(wèn):上面的圖中,哪個(gè)僅為弱連通的?請(qǐng)大家要復(fù)習(xí)“弱連通”的概念.6.設(shè)完全圖K有n個(gè)結(jié)點(diǎn)(n32),m條邊,當(dāng)()時(shí),K中存在歐拉回路.A.m為奇數(shù)B.n為偶數(shù)C.n為奇數(shù)D.m為偶數(shù)我們先復(fù)習(xí)完全圖的概念:定義3.1.6簡(jiǎn)單圖G=中,若每一對(duì)結(jié)點(diǎn)間都有邊相連,則稱該圖為完全圖.有n個(gè)結(jié)點(diǎn)的無(wú)向完全圖記為Kn.籟叢媽羥為贍僨蟶練淨(jìng)。由定義可知,完全圖Kn中的任一結(jié)點(diǎn)v到其它結(jié)點(diǎn)都有一條邊,共有n-1條邊,即每個(gè)結(jié)點(diǎn)的度數(shù)是n-1,當(dāng)n為奇數(shù)時(shí),n-1為偶數(shù).預(yù)頌圣鉉儐歲齦訝驊

8、糴。由定理4.1.1的推論一個(gè)無(wú)向圖具有一條歐拉回路,當(dāng)且僅當(dāng)該圖是連通的,并且它的結(jié)點(diǎn)度數(shù)都是偶數(shù).所以,正確答案應(yīng)該是C.7.若G是一個(gè)漢密爾頓圖,則G一定是().A.平面圖B.對(duì)偶圖C.

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無(wú)此問(wèn)題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫(kù)負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無(wú)法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。