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

1、1離散數(shù)學(xué)離散數(shù)學(xué)11春圖論部分綜合練習(xí)輔導(dǎo)春圖論部分綜合練習(xí)輔導(dǎo)大家好！本學(xué)期的第二次教學(xué)輔導(dǎo)活動(dòng)現(xiàn)在開(kāi)始，本次活動(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ì)偶圖與著色、樹(shù)與

2、生成樹(shù)、根樹(shù)及其應(yīng)用等本次綜合練習(xí)主要是復(fù)習(xí)這一單元的主要概念與計(jì)算方法，與集合論一樣，也安排了五種類型，有單項(xiàng)選擇題、填空題，判斷說(shuō)明題、計(jì)算題、證明題這樣的安排也是為了讓同學(xué)們熟悉期末考試的題型，能夠較好地完成這一部分主要內(nèi)容的學(xué)習(xí)下面是本學(xué)期第4，5次形考作業(yè)中的部分題目一、單項(xiàng)選擇題一、單項(xiàng)選擇題單項(xiàng)選擇題主要是第4次形考作業(yè)的部分題目第4次作業(yè)同樣也是由10個(gè)單項(xiàng)選擇題組成，每小題10分，滿分100分在每次作業(yè)在關(guān)閉之前，允許

3、大家反復(fù)多次練習(xí)，系統(tǒng)將保留您的最好成績(jī)，希望大家要多練幾次，爭(zhēng)取好成績(jī)需要提醒大家的是每次練習(xí)的作業(yè)題目可能不一樣，請(qǐng)大家一定要認(rèn)真閱讀題目1設(shè)圖G＝，v?V，則下列結(jié)論成立的是()Adeg(v)=2?E?Bdeg(v)=?E?CDEvVv2)deg(???EvVv???)deg(該題主要是檢查大家對(duì)握手定理掌握的情況復(fù)習(xí)握手定理：定理3.1.1設(shè)G是一個(gè)圖，其結(jié)點(diǎn)集合為V，邊集合為E，則???VvEv||2)deg(也就是說(shuō)，無(wú)向圖

4、G的結(jié)點(diǎn)的度數(shù)之和結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的兩倍邊數(shù)的兩倍正確答案：C2設(shè)無(wú)向圖G的鄰接矩陣為，????????????????0101010010000011100100110則G的邊數(shù)為()A6B5C4D3主要是檢查對(duì)鄰接矩陣的概念理解是否到位大家要復(fù)習(xí)鄰接矩陣的定義，3C（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è)）連

5、通的；若在任何結(jié)點(diǎn)偶對(duì)中，兩結(jié)點(diǎn)對(duì)互相可達(dá)，則稱圖G是強(qiáng)連通的正確答案：A問(wèn)：上面的圖中，哪個(gè)僅為弱連通的？請(qǐng)大家要復(fù)習(xí)“弱連通”的概念6設(shè)完全圖K有n個(gè)結(jié)點(diǎn)(n?2)，m條邊，當(dāng)（）時(shí)，K中存在歐拉nn回路Am為奇數(shù)Bn為偶數(shù)Cn為奇數(shù)Dm為偶數(shù)我們先復(fù)習(xí)完全圖的概念：定義定義3.1.6簡(jiǎn)單圖G=中，若每一對(duì)結(jié)點(diǎn)間都有邊相連，則稱該圖為完全圖完全圖有n個(gè)結(jié)點(diǎn)的無(wú)向完全圖記為Kn由定義可知，完全圖Kn中的任一結(jié)點(diǎn)v到其它結(jié)點(diǎn)都有一條邊，

6、共有n1條邊，即每個(gè)結(jié)點(diǎn)的度數(shù)是n1，當(dāng)n為奇數(shù)時(shí)，n1為偶數(shù)由定理4.1.1的推論推論一個(gè)無(wú)向圖具有一條歐拉回路，當(dāng)且僅當(dāng)該圖是連通的，并且它的結(jié)點(diǎn)度數(shù)都是偶數(shù)所以，正確答案應(yīng)該是C7若G是一個(gè)漢密爾頓圖，則G一定是()A平面圖B對(duì)偶圖C歐拉圖D連通圖我們先復(fù)習(xí)漢密爾頓圖的概念：定義定義4.2.14.2.1給定圖G，若存在一條路經(jīng)過(guò)圖G的每個(gè)結(jié)點(diǎn)一次且僅一次，則該路稱為漢密爾頓路；若存在一條回路經(jīng)過(guò)圖G的每個(gè)結(jié)點(diǎn)一次且僅一次，則該回路

7、稱為漢密爾頓回路；具有漢密爾頓回路的圖稱為漢密爾頓圖由定義可知，漢密爾頓圖是連通圖所以，正確答案應(yīng)該是D問(wèn)：漢密爾頓圖為什么不一定是歐拉圖嗎？8設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r=()Ae－v＋2Bv＋e－2Ce－v－2De＋v＋2本題主要檢查大家是否掌握了歐拉定理歐拉定理定理定理4.3.24.3.2（歐拉定理）（歐拉定理）設(shè)連通平面圖G的結(jié)點(diǎn)數(shù)為v，邊數(shù)為e，面數(shù)為r，則歐拉公式ver=2成立由歐拉公式ver=2，得到