版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、1離散數(shù)學(xué)離散數(shù)學(xué)11春圖論部分綜合練習輔導(dǎo)春圖論部分綜合練習輔導(dǎo)大家好!本學(xué)期的第二次教學(xué)輔導(dǎo)活動現(xiàn)在開始,本次活動主要是針對第二單元圖論的重點學(xué)習內(nèi)容進行輔導(dǎo),方式同樣是通過講解一些典型的綜合練習作業(yè)題目,幫助大家進一步理解和掌握圖論的基本概念和方法圖論作為離散數(shù)學(xué)的一部分,主要介紹圖論的基本概念、理論與方法教學(xué)內(nèi)容主要有圖的基本概念與結(jié)論、圖的連通性與連通度、圖的矩陣表示、最短路問題、歐拉圖與漢密爾頓圖、平面圖、對偶圖與著色、樹與
2、生成樹、根樹及其應(yīng)用等本次綜合練習主要是復(fù)習這一單元的主要概念與計算方法,與集合論一樣,也安排了五種類型,有單項選擇題、填空題,判斷說明題、計算題、證明題這樣的安排也是為了讓同學(xué)們熟悉期末考試的題型,能夠較好地完成這一部分主要內(nèi)容的學(xué)習下面是本學(xué)期第4,5次形考作業(yè)中的部分題目一、單項選擇題一、單項選擇題單項選擇題主要是第4次形考作業(yè)的部分題目第4次作業(yè)同樣也是由10個單項選擇題組成,每小題10分,滿分100分在每次作業(yè)在關(guān)閉之前,允許
3、大家反復(fù)多次練習,系統(tǒng)將保留您的最好成績,希望大家要多練幾次,爭取好成績需要提醒大家的是每次練習的作業(yè)題目可能不一樣,請大家一定要認真閱讀題目1設(shè)圖G=,v?V,則下列結(jié)論成立的是()Adeg(v)=2?E?Bdeg(v)=?E?CDEvVv2)deg(???EvVv???)deg(該題主要是檢查大家對握手定理掌握的情況復(fù)習握手定理:定理3.1.1設(shè)G是一個圖,其結(jié)點集合為V,邊集合為E,則???VvEv||2)deg(也就是說,無向圖
4、G的結(jié)點的度數(shù)之和結(jié)點的度數(shù)之和等于邊數(shù)的兩倍邊數(shù)的兩倍正確答案:C2設(shè)無向圖G的鄰接矩陣為,????????????????0101010010000011100100110則G的邊數(shù)為()A6B5C4D3主要是檢查對鄰接矩陣的概念理解是否到位大家要復(fù)習鄰接矩陣的定義,3C(c)是強連通的D(d)是強連通的我們先復(fù)習強連通的概念:定義3.2.5在簡單有向圖中,若在任何結(jié)點偶對中,至少從一個結(jié)點到另一個結(jié)點可達的,則稱圖G是單向(側(cè))連
5、通的;若在任何結(jié)點偶對中,兩結(jié)點對互相可達,則稱圖G是強連通的正確答案:A問:上面的圖中,哪個僅為弱連通的?請大家要復(fù)習“弱連通”的概念6設(shè)完全圖K有n個結(jié)點(n?2),m條邊,當()時,K中存在歐拉nn回路Am為奇數(shù)Bn為偶數(shù)Cn為奇數(shù)Dm為偶數(shù)我們先復(fù)習完全圖的概念:定義定義3.1.6簡單圖G=中,若每一對結(jié)點間都有邊相連,則稱該圖為完全圖完全圖有n個結(jié)點的無向完全圖記為Kn由定義可知,完全圖Kn中的任一結(jié)點v到其它結(jié)點都有一條邊,
6、共有n1條邊,即每個結(jié)點的度數(shù)是n1,當n為奇數(shù)時,n1為偶數(shù)由定理4.1.1的推論推論一個無向圖具有一條歐拉回路,當且僅當該圖是連通的,并且它的結(jié)點度數(shù)都是偶數(shù)所以,正確答案應(yīng)該是C7若G是一個漢密爾頓圖,則G一定是()A平面圖B對偶圖C歐拉圖D連通圖我們先復(fù)習漢密爾頓圖的概念:定義定義4.2.14.2.1給定圖G,若存在一條路經(jīng)過圖G的每個結(jié)點一次且僅一次,則該路稱為漢密爾頓路;若存在一條回路經(jīng)過圖G的每個結(jié)點一次且僅一次,則該回路
7、稱為漢密爾頓回路;具有漢密爾頓回路的圖稱為漢密爾頓圖由定義可知,漢密爾頓圖是連通圖所以,正確答案應(yīng)該是D問:漢密爾頓圖為什么不一定是歐拉圖嗎?8設(shè)G是連通平面圖,有v個結(jié)點,e條邊,r個面,則r=()Ae-v+2Bv+e-2Ce-v-2De+v+2本題主要檢查大家是否掌握了歐拉定理歐拉定理定理定理4.3.24.3.2(歐拉定理)(歐拉定理)設(shè)連通平面圖G的結(jié)點數(shù)為v,邊數(shù)為e,面數(shù)為r,則歐拉公式ver=2成立由歐拉公式ver=2,得到
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 離散數(shù)學(xué)圖論
- 離散數(shù)學(xué)第8章圖論
- 離散數(shù)學(xué)第7章-圖論-習題
- 《離散數(shù)學(xué)》總復(fù)習
- 離散數(shù)學(xué)復(fù)習 1
- 離散數(shù)學(xué)復(fù)習題
- 《離散數(shù)學(xué)》總復(fù)習 3
- 左孝凌離散數(shù)學(xué)課件7-圖論
- 離散數(shù)學(xué)復(fù)習資料
- 離散數(shù)學(xué)本科期末復(fù)習提要
- 離散數(shù)學(xué)本科期末復(fù)習提要
- 離散數(shù)學(xué)本科期末復(fù)習提要
- 離散數(shù)學(xué)復(fù)習思考題
- 離散數(shù)學(xué)
- 自考離散數(shù)學(xué)期末復(fù)習
- 《離散數(shù)學(xué)》復(fù)習題及答案
- 離散數(shù)學(xué)期末復(fù)習綱要
- 離散數(shù)學(xué)緒論
- 離散數(shù)學(xué) 7
- 離散數(shù)學(xué)基礎(chǔ)
評論
0/150
提交評論