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

離散數(shù)學(xué)11春圖論部分綜合練習(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ù)與生成樹(shù)、根樹(shù)及其應(yīng)用等． 本次綜合練習(xí)主要是復(fù)習(xí)這一單元的主要概念與計(jì)算方法，與集合論一樣，也安排了五種類(lèi)型，有單項(xiàng)選擇題、填空題，判斷說(shuō)明題、計(jì)算題、證明題．這樣的安排也是為了讓同學(xué)們熟悉期末考試的題型，能夠較好地完成這一部分主要內(nèi)容的學(xué)習(xí)． 下面是本學(xué)期第4，5次形考作業(yè)中的部分題目． 一、單項(xiàng)選擇題 單項(xiàng)選擇題主要是第4次形考作業(yè)的部分題目． 第4次作業(yè)同樣也是由10個(gè)單項(xiàng)選擇題組成，每小題10分，滿(mǎn)分100分．在每次作業(yè)在關(guān)閉之前，允許大家反復(fù)多次練習(xí)，系統(tǒng)將保留您的最好成績(jī)，希望大家要多練幾次，爭(zhēng)取好成績(jī)．需要提醒大家的是每次練習(xí)的作業(yè)題目可能不一樣，請(qǐng)大家一定要認(rèn)真閱讀題目． 1．設(shè)圖G＝<V, E>，vV，則下列結(jié)論成立的是 ( ) ． A．deg(v)=2E B． deg(v)=E C． D． 該題主要是檢查大家對(duì)握手定理掌握的情況．復(fù)習(xí)握手定理： 定理3.1.1 設(shè)G是一個(gè)圖，其結(jié)點(diǎn)集合為V，邊集合為E，則 也就是說(shuō)，無(wú)向圖G的結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的兩倍． 正確答案：C 2．設(shè)無(wú)向圖G的鄰接矩陣為 ， 則G的邊數(shù)為( )． A．6 B．5 C．4 D．3 主要是檢查對(duì)鄰接矩陣的概念理解是否到位．大家要復(fù)習(xí)鄰接矩陣的定義，要記住當(dāng)給定的簡(jiǎn)單圖是無(wú)向圖時(shí)，鄰接矩陣為對(duì)稱(chēng)的．即當(dāng)結(jié)點(diǎn)vi與vj相鄰時(shí)，結(jié)點(diǎn)vj與vi也相鄰，所以連接結(jié)點(diǎn)vi與vj的一條邊在鄰接矩陣的第i行第j列處和第j行第i列處各有一個(gè)1，題中給出的鄰接矩陣中共有10個(gè)1，故有102=5條邊． o o o o a b c d o e 正確答案：B 3．如右圖所示，以下說(shuō)法正確的是 ( ) ． A．{(a, e)}是割邊 B．{(a, e)}是邊割集 C．{(a, e) ,(b, c)}是邊割集 D．{(d, e)}是邊割集 先復(fù)習(xí)割邊、邊割集的定義： 定義3.2.9 設(shè)無(wú)向圖G=<V,E>為連通圖，若有邊集E1E，使圖G刪除了E1的所有邊后，所得的子圖是不連通圖，而刪除了E1的任何真子集后，所得的子圖是連通圖，則稱(chēng)E1是G的一個(gè)邊割集．若某個(gè)邊構(gòu)成一個(gè)邊割集，則稱(chēng)該邊為割邊（或橋） 因?yàn)閯h除答案A或B或C中的邊后，得到的圖是還是連通圖，因此答案A、B、C是錯(cuò)誤的． 正確答案：D o o o a b c d o 4．圖G如由圖所示，以下說(shuō)法正確的是 ( )． A．a(chǎn)是割點(diǎn) B．{b, c}是點(diǎn)割集 C．{b, d}是點(diǎn)割集 D．{c}是點(diǎn)割集 主要是檢查對(duì)點(diǎn)割集、割點(diǎn)的概念理解的情況． 定義3.2.7 設(shè)無(wú)向圖G=<V, E>為連通圖，若有點(diǎn)集V1V，使圖G刪除了V1的所有結(jié)點(diǎn)后，所得的子圖是不連通圖，而刪除了V1的任何真子集后，所得的子圖是連通圖，則稱(chēng)V1是G的一個(gè)點(diǎn)割集．若某個(gè)結(jié)點(diǎn)構(gòu)成一個(gè)點(diǎn)割集，則稱(chēng)該結(jié)點(diǎn)為割點(diǎn)． 從圖二中刪除結(jié)點(diǎn)b, c，得到的子圖是由不連通圖，而只刪除結(jié)點(diǎn)b或結(jié)點(diǎn)c，得到的子圖仍然是連通的，由定義可以知道，{b, c}是點(diǎn)割集．所以 正確答案：B 5．設(shè)有向圖（a）、（b）、（c）與（d）如下圖所示，則下列結(jié)論成立的是( )． A．（a）是強(qiáng)連通的 B．（b）是強(qiáng)連通的 C．（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á)的，則稱(chēng)圖G是單向（側(cè)）連通的； 若在任何結(jié)點(diǎn)偶對(duì)中，兩結(jié)點(diǎn)對(duì)互相可達(dá)，則稱(chēng)圖G是強(qiáng)連通的． 正確答案：A 問(wèn)：上面的圖中，哪個(gè)僅為弱連通的？ 請(qǐng)大家要復(fù)習(xí)“弱連通”的概念． 6．設(shè)完全圖K有n個(gè)結(jié)點(diǎn)(n2)，m條邊，當(dāng)（ ）時(shí)，K中存在歐拉回路． A．m為奇數(shù) B．n為偶數(shù) C．n為奇數(shù) D．m為偶數(shù) 我們先復(fù)習(xí)完全圖的概念： 定義3.1.6 簡(jiǎn)單圖G=<V，E>中，若每一對(duì)結(jié)點(diǎn)間都有邊相連，則稱(chēng)該圖為完全圖．有n個(gè)結(jié)點(diǎn)的無(wú)向完全圖記為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è)無(wú)向圖具有一條歐拉回路，當(dāng)且僅當(dāng)該圖是連通的，并且它的結(jié)點(diǎn)度數(shù)都是偶數(shù)． 所以，正確答案應(yīng)該是C． 7．若G是一個(gè)漢密爾頓圖，則G一定是( )． A．平面圖 B．對(duì)偶圖 C．歐拉圖 D．連通圖 我們先復(fù)習(xí)漢密爾頓圖的概念： 定義4.2.1 給定圖G，若存在一條路經(jīng)過(guò)圖G的每個(gè)結(jié)點(diǎn)一次且僅一次，則該路稱(chēng)為漢密爾頓路；若存在一條回路經(jīng)過(guò)圖G的每個(gè)結(jié)點(diǎn)一次且僅一次，則該回路稱(chēng)為漢密爾頓回路； 具有漢密爾頓回路的圖稱(chēng)為漢密爾頓圖． 由定義可知，漢密爾頓圖是連通圖． 所以，正確答案應(yīng)該是D． 問(wèn)：漢密爾頓圖為什么不一定是歐拉圖嗎？ 8．設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r= ( )． A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2 本題主要檢查大家是否掌握了歐拉定理． 定理4.3.2（歐拉定理） 設(shè)連通平面圖G的結(jié)點(diǎn)數(shù)為v，邊數(shù)為e，面數(shù)為r，則歐拉公式v-e+r =2成立． 由歐拉公式v-e+r =2，得到r = e- v+2． 所以，答案A是正確的． 9．無(wú)向簡(jiǎn)單圖G是棵樹(shù)，當(dāng)且僅當(dāng)( )． A．G連通且邊數(shù)比結(jié)點(diǎn)數(shù)少1 B．G連通且結(jié)點(diǎn)數(shù)比邊數(shù)少1 C．G的邊數(shù)比結(jié)點(diǎn)數(shù)少1 D．G中沒(méi)有回路． 可以運(yùn)用教材中的定理5.1.1，可以作出正確選擇．因?yàn)槎ɡ?.1.1中給出的圖T為樹(shù)的等價(jià)定義之一是圖T連通且e=v-1，其中e是邊數(shù)，v是結(jié)點(diǎn)數(shù)．也就是說(shuō)：無(wú)向簡(jiǎn)單圖G是棵樹(shù)，當(dāng)且僅當(dāng)G連通且邊數(shù)比結(jié)點(diǎn)數(shù)少1． 正確答案：A 注：由上面的樹(shù)的等價(jià)定義可知，結(jié)點(diǎn)數(shù)v與邊數(shù)e滿(mǎn)足e=v-1關(guān)系的無(wú)向連通圖就是樹(shù)． 10．已知一棵無(wú)向樹(shù)T中有8個(gè)結(jié)點(diǎn)，4度，3度，2度的分支點(diǎn)各一個(gè)，T的樹(shù)葉數(shù)為（ ）． A．8 B．5 C．4 D．3 正確答案：B 設(shè)無(wú)向樹(shù)T的樹(shù)葉數(shù)為x，因?yàn)闃?shù)葉是度數(shù)為1的結(jié)點(diǎn)． 那么，由定理3.1.1（握手定理） 設(shè)G是一個(gè)圖，其結(jié)點(diǎn)集合為V，邊集合為E，則 得 4+3+2+x=2（8-1），即x=5．應(yīng)選擇B． 下面的內(nèi)容主要是第5次形考作業(yè)的部分題目． 二、填空題 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ù)是 ． 也是檢查大家對(duì)握手定理掌握的情況． 因?yàn)閳DG中有1個(gè)1度結(jié)點(diǎn)，2個(gè)2度結(jié)點(diǎn)，3個(gè)3度結(jié)點(diǎn)，4個(gè)4度結(jié)點(diǎn)，即，根據(jù)握手定理，邊數(shù)有 o o o o a b c d o e o f ． 應(yīng)該填寫(xiě)：15 2．設(shè)給定圖G (如右圖所示)，則圖G的點(diǎn)割集是 ． 本題還是檢查大家對(duì)點(diǎn)割集、割點(diǎn)的概念理解的情 況． 點(diǎn)割集、割點(diǎn)的定義前面已經(jīng)復(fù)習(xí)了，從圖G中刪除結(jié)點(diǎn)f，得到的子圖是不連通圖，即結(jié)點(diǎn)集{f}是點(diǎn)割集；同樣，從圖G中刪除結(jié)點(diǎn)c，e，得到的子圖也是不連通圖，那么結(jié)點(diǎn)集{c, e}也是點(diǎn)割集．而刪除其他結(jié)點(diǎn)集都沒(méi)有滿(mǎn)足點(diǎn)割集、定義的集合，所以 應(yīng)該填寫(xiě)：{f}、{c, e} 3．無(wú)向圖G存在歐拉回路，當(dāng)且僅當(dāng)G連通且 ． 由定理4.1.1的推論 一個(gè)無(wú)向圖具有一條歐拉回路，當(dāng)且僅當(dāng)該圖是連通的，并且它的結(jié)點(diǎn)度數(shù)都是偶數(shù)． 應(yīng)該填寫(xiě)：結(jié)點(diǎn)度數(shù)都是偶數(shù) 4．設(shè)G=<V，E>是具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，若在G中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于 ，則在G中存在一條漢密爾頓路． 定理4.2.2 設(shè)G=<V，E>是具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，若在G中每一對(duì)結(jié)點(diǎn)度數(shù)之和大于等于n-1，則在G中存在一條漢密爾頓路． 應(yīng)該填寫(xiě)：n-1 5．設(shè)圖G是有6個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的總度數(shù)為18，則可從G中刪去 條邊后使之變成樹(shù)．（……邊后，可以確定圖G的一棵生成樹(shù)） 由握手定理（定理3.1.1）知道圖G有182=9 條邊，又由定理5.1.1中給出的圖T為樹(shù)的等價(jià)定義之一是“圖T連通且e=v-1”，可以知道： 應(yīng)該填寫(xiě)：4． 6．設(shè)正則5叉樹(shù)的樹(shù)葉數(shù)為17，則分支數(shù)為i = ． 定理5.2.1 設(shè)有正則m叉樹(shù)，其樹(shù)葉數(shù)為t，分枝數(shù)為i，則(m-1)i=t-1． 其中m=5， t=17，由(5-1)i=17-1，得i =4． 應(yīng)該填寫(xiě)：4 三、判斷說(shuō)明題 1．如果圖G是無(wú)向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖G存在一條歐拉回路． 分析：先復(fù)習(xí)歐拉圖的判別定理： 定理4.1.1的推論：一個(gè)無(wú)向圖具有一條歐拉回路，當(dāng)且僅當(dāng)該圖是連通的，并且它的結(jié)點(diǎn)度數(shù)都是偶數(shù)． 解：不正確． 因?yàn)轭}中的圖G沒(méi)有“連通”的條件． 2．如下圖所示的圖G存在一條歐拉回路． 解：不正確． 因?yàn)閳DG中結(jié)點(diǎn)b和c的度數(shù)是奇數(shù)． 注：這是一個(gè)漢密爾頓圖，但不是歐拉圖，它可以作為單向選擇題7解答之后提出的問(wèn)題的一個(gè)解答． 3．設(shè)G是一個(gè)有7個(gè)結(jié)點(diǎn)16條邊的連通圖，則G為平面圖． 分析：定理4.3.3 設(shè)G是一個(gè)有v個(gè)結(jié)點(diǎn)e條邊的連通簡(jiǎn)單平面圖，若v≥3，則e≤3v-6． 利用該定理判斷本題． 解：不正確． 因?yàn)轭}中的連通簡(jiǎn)單平面圖有v=7個(gè)結(jié)點(diǎn)，e=16條邊，那么1637-6=15，由定理4.3.3知道，圖G不是平面圖． 4．設(shè)G是一個(gè)連通平面圖，且有6個(gè)結(jié)點(diǎn)11條邊，則G有7個(gè)面． 分析：可以用平面圖中的歐拉公式：v-e+r =2來(lái)判斷，其中v為結(jié)點(diǎn)數(shù)，e為邊數(shù)，r為面數(shù)． 解：正確． 因?yàn)檫B通平面圖G有v=6個(gè)結(jié)點(diǎn)，e=11條邊，那么由歐拉公式計(jì)算得：r =2+ 11- 6 = 7個(gè)面． 四、計(jì)算題 1．設(shè)G=<V，E>，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，試 (1) 給出G的圖形表示； (2) 寫(xiě)出其鄰接矩陣； (3) 求出每個(gè)結(jié)點(diǎn)的度數(shù)； o o o o v1 o v5 v2 v3 v4 (4) 畫(huà)出其補(bǔ)圖的圖形． 解：(1) 因?yàn)閂={ v1，v2，v3，v4，v5}， E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)， (v4,v5) }，所以G的圖形表示為： (2) 分析：本題給定的簡(jiǎn)單圖是無(wú)向圖， 因此鄰接矩陣為對(duì)稱(chēng)的．即當(dāng)結(jié)點(diǎn)vi與vj相 鄰時(shí)，結(jié)點(diǎn)vj與vi也相鄰，所以連接結(jié)點(diǎn)vi 與vj的一條邊在鄰接矩陣的第i行第j列處和 第j行第i列處各寫(xiě)一個(gè)1；當(dāng)結(jié)點(diǎn)vi與vj沒(méi) 有邊連接時(shí)，鄰接矩陣的第i行第j列處和第j行第i列處各寫(xiě)一個(gè)0． 鄰接矩陣： (3) 由G的圖形可知，v1，v2，v3，v4，v5結(jié)點(diǎn)的度數(shù)依次為1，2，4，3，2 o o o o v1 o v5 v2 v3 v4 o o o o v1 o v5 v2 v3 v4 (4) 由關(guān)于補(bǔ)圖的定義3.1.9可知，先畫(huà)出完全圖（見(jiàn)圖1），然后去掉原圖，可得補(bǔ)圖（見(jiàn)圖2）如下： 圖1 圖2 注意：補(bǔ)圖中，如果沒(méi)有標(biāo)出結(jié)點(diǎn)v3，則是錯(cuò)的． 2．圖G=<V, E>，其中V={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，對(duì)應(yīng)邊的權(quán)值依次為2、1、2、3、6、1、4及5，試 （1）畫(huà)出G的圖形； （2）寫(xiě)出G的鄰接矩陣； （3）求出G權(quán)最小的生成樹(shù)及其權(quán)值． 解 （1）因?yàn)閂={ a, b, c, d, e}，E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，所以G的圖形表示為： （2）由圖得圖G的鄰接矩陣為： （3）圖G有5個(gè)結(jié)點(diǎn)，其生成樹(shù)有4條邊，用Kruskal算法（避圈法）求其權(quán)最小的生成樹(shù)T： 第1步，取具最小權(quán)1的邊(a, c)； 第2步，取剩余邊中具最小權(quán)1的邊(c, e)； 第3步，取剩余邊中不與前2條邊構(gòu)成回路的具最小權(quán)2的邊(a, b)； 第4步，取剩余邊中不與前3條邊構(gòu)成回路的具最小權(quán)3的邊(b, d)． 所求最小生成樹(shù)T如右下圖，其權(quán)為． 注意：在用避圈法求最小的生成樹(shù)的關(guān)鍵是：“取圖中權(quán)數(shù)最小的邊，且與前面取到的邊不構(gòu)成圈”，很多學(xué)生只注意到取權(quán)數(shù)最小的邊了，而忽略了“不構(gòu)成圈”的要求． 如果結(jié)點(diǎn)數(shù)少一個(gè)，邊數(shù)也少些，大家應(yīng)該會(huì)做了吧． 3．設(shè)有一組權(quán)為2, 3, 5, 7, 17, 31，試畫(huà)出相應(yīng)的最優(yōu)二叉樹(shù)，計(jì)算該最優(yōu)二叉樹(shù)的權(quán)． 解：方法（Huffman）：從2, 3, 5, 7, 17, 31中選2, 3為最低層結(jié)點(diǎn)，并從權(quán)數(shù)中刪去，再添上他們的和數(shù)，即5, 5, 7, 17, 31； o o o o o 3 2 7 5 5 17 34 10 o o o o 17 31 o o 65 再?gòu)?, 5, 7, 17, 31中選5, 5為倒數(shù)第2層結(jié)點(diǎn)，并從 上述數(shù)列中刪去，再添上他們的和數(shù)，即7, 10, 17, 31； 然后，從7, 10, 17, 31中選7, 10為倒數(shù)第3層結(jié)點(diǎn)， 并從上述數(shù)列中刪去，再添上他們的和數(shù)，即17, 17, 31； …… 最優(yōu)二叉樹(shù)如右圖所示． 最優(yōu)二叉樹(shù)權(quán)值為：25+35+54+73+172+311 =10+15+20+21+34+31=131 講評(píng)：作業(yè)中最優(yōu)二叉樹(shù)往往都能畫(huà)對(duì)了，但計(jì)算總權(quán)值時(shí) 可能會(huì)把有些權(quán)的層數(shù)計(jì)算錯(cuò)了，導(dǎo)致總權(quán)值計(jì)算錯(cuò)誤，大家一定要細(xì)心． 注意：這3個(gè)計(jì)算題大家一定要掌握． 五、證明題 證明題同學(xué)一般都做不好，原因是對(duì)證明題方法沒(méi)有掌握，也是對(duì)一些概念不清楚所造成的．因此，希望大家認(rèn)真學(xué)習(xí)教材和老師講課中的證明方法，并通過(guò)作業(yè)逐步掌握做證明題的方法． 1．設(shè)G是一個(gè)n階無(wú)向簡(jiǎn)單圖，n是大于等于3的奇數(shù)．證明圖G與它的補(bǔ)圖中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等． 證明：設(shè)，．則是由n階無(wú)向完全圖的邊刪去E所得到的．所以對(duì)于任意結(jié)點(diǎn)，u在G和中的度數(shù)之和等于u在中的度數(shù)．由于n是大于等于3的奇數(shù)，從而的每個(gè)結(jié)點(diǎn)都是偶數(shù)度的（度），于是若在G中是奇數(shù)度結(jié)點(diǎn)，則它在中也是奇數(shù)度結(jié)點(diǎn)．故圖G與它的補(bǔ)圖中的奇數(shù)度結(jié)點(diǎn)個(gè)數(shù)相等． 2．設(shè)連通圖G有k個(gè)奇數(shù)度的結(jié)點(diǎn)，證明在圖G中至少要添加條邊才能使其成為歐拉圖． 證明：由定理3.1.2，任何圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)必是偶數(shù)，可知k是偶數(shù)． 又根據(jù)定理4.1.1的推論，圖G是歐拉圖的充分必要條件是圖G不含奇數(shù)度結(jié)點(diǎn)．因此只要在每對(duì)奇數(shù)度結(jié)點(diǎn)之間各加一條邊，使圖G的所有結(jié)點(diǎn)的度數(shù)變?yōu)榕紨?shù)，成為歐拉圖． 故最少要加條邊到圖G才能使其成為歐拉圖． 9