離散數學圖論部分綜合練習輔導本次活動是本學期的第二次活動(2023.11.18)，重要是針對第二單元圖論的重點學習內容進行輔導，方式是通過講解一些典型的綜合練習題目，幫助大家進一步理解和掌握圖論的基本概念和方法。圖論作為離散數學的一部分，重要介紹圖論的基本概念、理論與方法。教學內容重要有圖的基本概念與結論、圖的連通性與連通度、圖的矩陣表達、最短路問題、歐拉圖與漢密爾頓圖、平面圖、對偶圖與著色、樹與生成樹、根樹及其應用等。本次綜合練習重要是復習這一部分的重要概念與計算方法，與集合論同樣，也安排了五種類型，有單項選擇題、填空題，判斷說明題、計算題、證明題。這樣的安排也是為了讓同學們熟悉期末考試的題型，可以較好地完畢這一部分重要內容的學習。下面分別講解。一、單項選擇題1．設圖G的鄰接矩陣為 則G的邊數為()．A．5B．6C．3對的答案：D上學期的作業中，有的同學選擇答案B。重要是對鄰接矩陣的概念理解不到位。我們復習定義：定義3.3.1設G=<V，E>是一個簡樸圖，其中V={v1，v2，…，vn}，則n階方陣A（G）=（aij）稱為G的鄰接矩陣．其中各元素而當給定的簡樸圖是無向圖時，鄰接矩陣為對稱的．即當結點vi與vj相鄰時，結點vj與vi也相鄰，所以連接結點vi與vj的一條邊在鄰接矩陣的第i行第j列處和第j行第i列處各有一個1，題中給出的鄰接矩陣中共有8個1，故有82=4條邊。2．設圖G＝<V,E>，則下列結論成立的是()．A．deg(V)=2EB．deg(V)=EC．D．對的答案：C該題重要是檢查大家對握手定理掌握的情況。復習握手定理：定理3.1.1設G是一個圖，其結點集合為V，邊集合為Ecabedf3．圖G如右圖所示，以下說法對的的是()．A．{(a,d)}是割邊B．{(a,d)}是邊割集C．{(d,e)}是邊割集D．{(a,d),(a,c)}是邊割集對的答案：C上學期許多同學選擇答案A。重要是對割邊、邊割集的概念理解不到位。復習割邊、邊割集的定義：定義3.2.9設無向圖G=<V,E>為連通圖，若有邊集E1E，使圖G刪除了E1的所有邊后，所得的子圖是不連通圖，而刪除了E1的任何真子集后，所得的子圖是連通圖，則稱E1是G的一個邊割集．若某個邊構成一個邊割集，則稱該邊為割邊（或橋假如答案A對的，即刪除邊(a,d)后，得到的圖是不連通圖，但事實上它還是連通的。因此答案A是錯誤的。4．設G是連通平面圖，有v個結點，e條邊，r個面，則r=()．A．e－v＋2B．v＋e－2C．e－v－2D．e＋v＋2對的答案：A該題重要是檢查大家對平面圖的歐拉定理的理解情況。定理4.3.2（歐拉定理）設連通平面圖G的結點數為v，邊數為e，面數為r，則下列歐拉公式成立．v-e+r=25．無向圖G存在歐拉通路，當且僅當()．A．G中所有結點的度數全為偶數B．G中至多有兩個奇數度結點C．G連通且所有結點的度數全為偶數D．G連通且至多有兩個奇數度結點對的答案：D上學期許多同學選擇答案C。重要是將題中的“歐拉通路”誤認為“歐拉回路”了。其實應當運用定理4.1.1進行選擇，才是對的的。定義4.1.1給定無孤立結點圖G，若存在一條路通過圖G的每條邊一次且僅一次，則該路稱為歐拉路；若存在一條回路通過圖G的每條邊一次且僅一次，在該回路稱為歐拉回路；……定理4.1.1無向圖G具有一條歐拉路，當且僅當G是連通的，且有零個或2個奇數度數的結點．推論一個無向圖具有一條歐拉回路，當且僅當該圖是連通的，并且它的結點度數都是偶數．所以，對的答案應當是D．6．設G是有n個結點，m條邊的連通圖，必須刪去G的()條邊，才干擬定G的一棵生成樹．A．B．C．D．對的答案：A上學期許多同學選擇答案D。重要是把定理5.1.1給出的圖T為樹的等價定義之一是圖T連通且e=v-1中的公式用錯了．大家只要把m代入公式e=v-1中的e，把n代入公式e=v-1中的v，可以知道定理5.1.1給定圖T，則以下關于圖T（1）無回路的連通圖．（2）無回路且e=v-1，其中e是邊數，v是頂點數．（3）連通且e=v-1．（4）無回路，但增長任一新邊，得到且僅得到一個回路．（5）連通，但刪去任一邊后圖便不連通．（v≥2）（6）每一對頂點之間有且僅有一條路．（v≥2）定理5.1.1的六個等價定義，大家應當熟記的．最重要的是：無向簡樸圖G是棵樹，當且僅當G連通且邊數比結點數少1．二、填空題1．已知圖G中有1個1度結點，2個2度結點，3個3度結點，4個4度結點，則G的邊數是．應當填寫：15重要檢查大家對握手定理掌握的情況。定理3.1.1（握手定理）設G是一個圖，其結點集合為V，邊集合為Ecabedcabedf問：若無向樹T中有8個結點，4度，3度，2度的分支點各一個，那么T的樹葉數為多少？2．設給定圖G(如右圖所示)，則圖G的點割集是．應當填寫：{f}，{c，e}上學期許多同學填錯答案重要對點割集的概念理解不對的。定義3.2.7設無向圖G=<V,E>為連通圖，若有點集V1V，使圖G刪除了V1的所有結點后，所得的子圖是不連通圖，而刪除了V1的任何真子集后，所得的子圖是連通圖，則稱V1是G的一個上學期許多同學填寫的{f，c}，重要是沒有完全理解定義3.2.7，由于{f}是{f，c}的3．設無向圖G＝<V,E>是漢密爾頓圖，則V的任意非空子集V1，都有V1．應當填寫：W(G-V1)由于具有漢密爾頓回路的圖稱為漢密爾頓圖．而由定理4.2.1若圖G=<V,E>中具有一條漢密爾頓回路，則對于結點集V的每個非空子集S均有W(G-S)|S|成立，其中W(G-S)是（G-S）中連通分支數．因此應當填寫：W(G-V1)．4．設有向圖D為歐拉圖，則圖D中每個結點的入度．應當填寫：等于出度假如大家記住“具有歐拉回路的圖稱為歐拉圖”和定理4.1.2：一個有向圖具有單向歐拉回路，當且僅當它是連通的，且每個結點的入度等于出度．5．設完全圖K有n個結點(n2)，m條邊，當時，K中存在歐拉回路．應當填寫：n為奇數上學期許多同學填錯答案重要對完全圖的概念理解不對的。定義3.1.6簡樸圖G=<V，E>中，若每一對結點間都有邊相連，則稱該圖為完全圖．有n個結點的無向完全圖記為Kn．由定義可知，完全圖Kn中的任一結點v到其它結點都有一條邊，共有n-1條邊，即每個結點的度數是n-1，當n為奇數時，n-1為偶數。由定理4.1.1的推論可知，應當填寫：n6．給定一個序列集合{1，01，10，11，001，000}，若去掉其中的元素，則該序列集合構成前綴碼．應當填寫：1由于在二進制中1是10和11的前綴。而前綴碼的定義是（定義5.2.10）：填寫該題答案時大家一定要對前綴碼的定義理解非常清楚。問：若把序列集合中的1換成0，應當去掉哪個元素？三、判斷說明題1．給定兩個圖G1，G2（如下圖所示）：（1）試判斷它們是否為歐拉圖、漢密爾頓圖？并說明理由．v1（2）若是歐拉圖，v1v6v5v4v6v5v4v3v2分析：先復習歐拉圖的判別定理和漢密爾頓圖的定義：定理4.1.1的推論：一個無向圖具有一條歐拉回路，當且僅當該圖是連通的，并且它的結點度數都是偶數．定義4.2.1：若存在一條回路通過圖G的每個結點一次且僅一次，則該回路稱為漢密爾頓回路；具有漢密爾頓回路的圖稱為漢密爾頓圖．解：（1）圖G1是歐拉圖．由于圖G1中每個結點的度數都是偶數．圖G2是漢密爾頓圖．由于圖G2存在一條漢密爾頓回路（不惟一）：a(a,b)b(b,e)e(e,f)f(f,g)g(g,d)d(d,c)c(c,a)a問題：請大家想一想，為什么圖G1不是漢密爾頓圖，圖G2不是歐拉圖。（2）圖G1的歐拉回路為：（不惟一）：v1(v1,v2)v2(v2,v3)v3(v3,v4)v4(v4,v5)v5(v5,v2)v2(v2,v6)v6(v6,v4)v4(v4,v1)v1v5v1v2v4v6v32．判別圖G(如右圖所示)是不是平面圖，并說明理由．分析：平面圖的定義是定義4.3.1設G=<V，E>是一個無向圖，假如能把G的所有結點與邊畫在平面上，并且使得任何兩條邊除端點外沒有其他的交點，則v5v1v2v4v6v3顯然平面圖的邊與邊只在結點處相交．解：圖G是平面圖．由于只要把結點v2與v6的連線(v2,v6)拽到結點v1的外面，把把結點v3與v6的連線(v3,v6)拽到結點v4,v5的外面，就得到一個平面圖．注意：定理4.3.3設G是一個有v個結點e條邊的連通簡樸平面圖，若v≥3，則e≤3v-6．會用于判斷不是平面圖。四、計算題1．設圖GV，E，其中Va1,a2,a3,a4,a5,Ea1,a2，a2,a4，a3,a1，a4,a5，a5,a2（1）試給出G的圖形表達；（2）求G的鄰接矩陣；（3）判斷圖G是強連通圖、單側連通圖還是弱連通圖？a1a2a1a2a3a4a5（3）圖G是單側連通圖，也是弱連通圖．關于強連通圖、單側連通圖還是弱連通圖的判斷，希望大家掌握圖論綜合作業單項選擇題中的第4題。2．圖G=<V,E>，其中V={a,b,c,d,e,f}，E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(d,e),(d,f),(e,f)}，相應邊的權值依次為5，2，1，2，6，1，9，3及8．（1）畫出G的圖形；cabedf152261938（3）求出G權最小的生成樹及其權值．解：（1）由于V={a,b,c,d,e,f}E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(d,e),(d,f),(e,f)}，權值依次為5，2，1，2，6，1，9，3及8所以，G的圖形如右圖所示：（2）分析：定義3.3.1設G=<V，E>是一個簡樸圖，其中V={v1，v2，…，vn}，則n階方陣A(G)=(aij)稱為G的鄰接矩陣．其中ccabedf152261938（3）用避圈法：第1步：選(a,e)和(c,e)邊；第2步：選(b,d)邊；（為什么不選(a,c)？）第3步：選(d,f)邊；第4步：選(a,b)邊．這樣，得到了最小的生成樹，如右圖中粗線所示．最小的生成樹的權為1+1+5+2+3=12．上學期作業中的最小的生成樹求的不對，重要是沒有把握“取權數最小的邊，且與前面取到的邊不構成圈”，經常是只注意取權數最小的邊了，而忽略“不構成圈”的規定。問：假如結點集是V={a,b,c,d,e}，邊集E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(d,e)}，相應邊的權值依次為5，2，1，2，6，1，9，那么會求嗎？3．設有一組權為2,3,5,7,11,13,17,19,23,29,31,試（1）畫出相應的最優二叉樹；32713551117341602910231942172453319565解：（1）最優二叉樹如右圖所示：方法（Huffman）：從2,3,5,7,11,13,17,19,23,29,31中選2,3為最低層結點，并從權數中刪去，再添上他們的和數，即5,5,7,11,13,17,19,23,29,31；再從5,5,7,11,13,17,19,23,29,31中選5,5為倒數第2層結點，并從上述數列中刪去，再添上他們的和數，即7,10,11,13,17,19,23,29,31；然后，從7,10,11,13,17,19,23,29,31中選7,10和11,13為倒數第3層結點，并從上述數列中刪去，再添上他們的和數，即17,17,24,19,23,29,31；……（2）權值為：26+36+55+74+114+134+173+193+233+293+312=12+18+25+28+44+52+51+57+69+87+62=505講評：作業中最優二叉樹都畫對了，但計算總權值時把有些權的層數計算錯了，導致總權值計算錯誤。問：假如一組權為2,3,6,9,13,