2023年離散數(shù)學(xué)形成性考核作業(yè)三

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