離散數(shù)學(xué)圖論復(fù)習(xí)

《離散數(shù)學(xué)圖論復(fù)習(xí)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

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

2、選擇題、填空題，判斷說明題、計(jì)算題、證明題．這樣的安排也是為了讓同學(xué)們熟悉期末考試的題型，能夠較好地完成這一部分主要內(nèi)容的學(xué)習(xí)．下面是本學(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)將保留您的最好成績，希望大家要多練幾次，爭取好成績．需要提醒大家的是每次練習(xí)的作業(yè)題目可能不一樣，請大家一定要認(rèn)真閱讀題目．1．設(shè)圖G＝，v?V，則下列結(jié)論成立的是()．

3、A．deg(v)=2?E?B．deg(v)=?E?C．D．該題主要是檢查大家對握手定理掌握的情況．復(fù)習(xí)握手定理：定理3.1.1設(shè)G是一個(gè)圖，其結(jié)點(diǎn)集合為V，邊集合為E，則也就是說，無向圖G的結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的兩倍．正確答案：C2．設(shè)無向圖G的鄰接矩陣為，則G的邊數(shù)為()．A．6B．5C．4D．3主要是檢查對鄰接矩陣的概念理解是否到位．8大家要復(fù)習(xí)鄰接矩陣的定義，要記住當(dāng)給定的簡單圖是無向圖時(shí)，鄰接矩陣為對稱的．即當(dāng)結(jié)點(diǎn)vi與vj相鄰時(shí)，結(jié)點(diǎn)vj與vi也相鄰，所以連接結(jié)點(diǎn)vi與vj的一條邊在鄰接矩陣的第i行第j列處和

4、第j行第i列處各有一個(gè)1，題中給出的鄰接矩陣中共有10個(gè)1，故有10?2=5條邊．ooooabcdoe正確答案：B3．如右圖所示，以下說法正確的是()．A．{(a,e)}是割邊B．{(a,e)}是邊割集C．{(a,e),(b,c)}是邊割集D．{(d,e)}是邊割集先復(fù)習(xí)割邊、邊割集的定義：定義3.2.9設(shè)無向圖G=為連通圖，若有邊集E1ìE，使圖G刪除了E1的所有邊后，所得的子圖是不連通圖，而刪除了E1的任何真子集后，所得的子圖是連通圖，則稱E1是G的一個(gè)邊割集．若某個(gè)邊構(gòu)成一個(gè)邊割集，則稱該邊為割邊（或橋）

5、因?yàn)閯h除答案A或B或C中的邊后，得到的圖是還是連通圖，因此答案A、B、C是錯(cuò)誤的．正確答案：Doooabcdo4．圖G如由圖所示，以下說法正確的是()．A．a(chǎn)是割點(diǎn)B．{b,c}是點(diǎn)割集C．{b,d}是點(diǎn)割集D．{c}是點(diǎn)割集主要是檢查對點(diǎn)割集、割點(diǎn)的概念理解的情況．定義3.2.7設(shè)無向圖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)割集，則稱該結(jié)點(diǎn)為割點(diǎn)．從圖二中刪除結(jié)點(diǎn)b,c，

6、得到的子圖是由不連通圖，而只刪除結(jié)點(diǎn)b或結(jié)點(diǎn)c，得到的子圖仍然是連通的，由定義可以知道，{b,c}是點(diǎn)割集．所以正確答案：B5．設(shè)有向圖（a）、（b）、（c）與（d）如下圖所示，則下列結(jié)論成立的是()．A．（a）是強(qiáng)連通的B．（b）是強(qiáng)連通的8C．（c）是強(qiáng)連通的D．（d）是強(qiáng)連通的我們先復(fù)習(xí)強(qiáng)連通的概念：定義3.2.5在簡單有向圖中，若在任何結(jié)點(diǎn)偶對中，至少從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)可達(dá)的，則稱圖G是單向（側(cè)）連通的；若在任何結(jié)點(diǎn)偶對中，兩結(jié)點(diǎn)對互相可達(dá)，則稱圖G是強(qiáng)連通的．正確答案：A問：上面的圖中，哪個(gè)僅為弱連通的？請

7、大家要復(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簡單圖G=中，若每一對結(jié)點(diǎn)間都有邊相連，則稱該圖為完全圖．有n個(gè)結(jié)點(diǎn)的無向完全圖記為Kn．由定義可知，完全圖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ù)．由定理4.1.1的推論一個(gè)無向圖具有一條歐拉回路，當(dāng)且僅當(dāng)該圖是連通的，并且它的結(jié)點(diǎn)度數(shù)都是偶數(shù)．所以，正確答案

8、應(yīng)該是C．7．若G是一個(gè)漢密爾頓圖，則G一定是()．A．平面圖B．對偶圖C．歐拉圖D．連通圖我們先復(fù)習(xí)漢密爾頓圖的概念：定義4.2.1給定圖G，若存在一條路經(jīng)過圖G的每個(gè)結(jié)點(diǎn)一次且僅一次，則該路稱為漢密爾頓路；若存在一條回路經(jīng)過圖G的每個(gè)結(jié)點(diǎn)一次且僅一次，則該回路稱為漢密爾頓回路；具有漢密爾頓回路的圖稱為漢密爾頓圖．