離散數(shù)學圖論復習

1、1離散數(shù)學離散數(shù)學11春圖論部分綜合練習輔導春圖論部分綜合練習輔導大家好！本學期的第二次教學輔導活動現(xiàn)在開始，本次活動主要是針對第二單元圖論的重點學習內(nèi)容進行輔導，方式同樣是通過講解一些典型的綜合練習作業(yè)題目，幫助大家進一步理解和掌握圖論的基本概念和方法圖論作為離散數(shù)學的一部分，主要介紹圖論的基本概念、理論與方法教學內(nèi)容主要有圖的基本概念與結(jié)論、圖的連通性與連通度、圖的矩陣表示、最短路問題、歐拉圖與漢密爾頓圖、平面圖、對偶圖與著色、樹與

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

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

4、G的結(jié)點的度數(shù)之和結(jié)點的度數(shù)之和等于邊數(shù)的兩倍邊數(shù)的兩倍正確答案：C2設無向圖G的鄰接矩陣為，????????????????0101010010000011100100110則G的邊數(shù)為()A6B5C4D3主要是檢查對鄰接矩陣的概念理解是否到位大家要復習鄰接矩陣的定義，3C（c）是強連通的D（d）是強連通的我們先復習強連通的概念：定義3.2.5在簡單有向圖中，若在任何結(jié)點偶對中，至少從一個結(jié)點到另一個結(jié)點可達的，則稱圖G是單向（側(cè)）連

5、通的；若在任何結(jié)點偶對中，兩結(jié)點對互相可達，則稱圖G是強連通的正確答案：A問：上面的圖中，哪個僅為弱連通的？請大家要復習“弱連通”的概念6設完全圖K有n個結(jié)點(n?2)，m條邊，當（）時，K中存在歐拉nn回路Am為奇數(shù)Bn為偶數(shù)Cn為奇數(shù)Dm為偶數(shù)我們先復習完全圖的概念：定義定義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ù)所以，正確答案應該是C7若G是一個漢密爾頓圖，則G一定是()A平面圖B對偶圖C歐拉圖D連通圖我們先復習漢密爾頓圖的概念：定義定義4.2.14.2.1給定圖G，若存在一條路經(jīng)過圖G的每個結(jié)點一次且僅一次，則該路稱為漢密爾頓路；若存在一條回路經(jīng)過圖G的每個結(jié)點一次且僅一次，則該回路

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