離散數(shù)學(xué)第7章-圖論-習(xí)題

1、第7章 習(xí)題課,,練習(xí)7-1（6）簡(jiǎn)單圖的最大度小于結(jié)點(diǎn)數(shù)。,證明：設(shè)簡(jiǎn)單圖G中有n個(gè)結(jié)點(diǎn)。 任取一個(gè)結(jié)點(diǎn)v， 由已知G是簡(jiǎn)單圖沒(méi)有環(huán)和重邊，v至多和n-1個(gè)結(jié)點(diǎn)相鄰， 也即deg(v) ≤n-1, 而 △(G)＝max deg(v) ≤ n-1, 因此 最大度小于結(jié)點(diǎn)數(shù)。,練習(xí)7-2（2）：若無(wú)向圖G中恰有兩個(gè)奇數(shù)度的結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)之間必有一條路。,證明：設(shè)無(wú)向圖G中兩個(gè)奇數(shù)度的結(jié)點(diǎn)為

2、u和v。從u開(kāi)始構(gòu)造一條跡，即從u出發(fā)經(jīng)關(guān)聯(lián)于結(jié)點(diǎn)u的邊e1到達(dá)結(jié)點(diǎn)u1，若deg(u1)為偶數(shù),則必可由u1再經(jīng)關(guān)聯(lián)于結(jié)點(diǎn)u1的邊e2到達(dá)結(jié)點(diǎn)u2,如此繼續(xù)下去,每邊只取一次,直到另一個(gè)奇數(shù)度結(jié)點(diǎn)停止,由于圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn),故該結(jié)點(diǎn)或是u或是v。如果是v,那么從u到v的一條路就構(gòu)造好了。如果仍是結(jié)點(diǎn)u,此路是閉跡。,閉跡上每個(gè)結(jié)點(diǎn)都是關(guān)聯(lián)偶數(shù)條邊,而deg(u)為奇數(shù),所以至少還有一條關(guān)聯(lián)于結(jié)點(diǎn)u的邊不在此閉跡上。繼續(xù)從u出

3、發(fā),沿著該邊到達(dá)另一個(gè)結(jié)點(diǎn)u1’,依次下去直到另一個(gè)奇數(shù)度結(jié)點(diǎn)停下。這樣經(jīng)過(guò)有限次后必可到達(dá)結(jié)點(diǎn)v,這就是一條從u到v的路。,練習(xí)7-2（3）：若圖G是不連通的，則G的補(bǔ)圖G是連通的。,證明：若G=是不連通的，可設(shè)圖G的連通分支為G[V1],G[V2],……,G[Vm](m≥2)。由于任意兩個(gè)連通分支G[Vi],G[Vj]不連通，因此Vi與Vj之間的連線在補(bǔ)圖中，在G中任取兩個(gè)結(jié)點(diǎn)u和v，則u和v的位置有兩種情況：1)若u和v

4、均在同一個(gè)連通分支G[Vi]中,根據(jù)上面的分析，可在另一個(gè)連通分支G[Vj]（i≠j)中取一個(gè)結(jié)點(diǎn)w，使得u與w，v 與w在G中連通，故有u－w－v，即u與v在G中連通2)若u與v分別屬于兩個(gè)不同的連通分支G[Vi]與G[Vj]，由上面的分析可知，u與v在G中連通。故當(dāng)圖G不連通時(shí)，則補(bǔ)圖G是連通的,,,,,,7-2（4）:當(dāng)且僅當(dāng)G的一條邊e不包含在G的回路中時(shí)，e才是G的割邊。,證明：必要性。（ e是G的割邊）設(shè)e是連通圖G的

5、割邊，e關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)是u和v。如果e包含在G的一個(gè)回路中，那么除邊e=(u,v)外還有另一條分別以u(píng)和v為端點(diǎn)的路，所以刪去邊e后，G仍為連通圖，這與e是割邊相矛盾。,充分性。如果邊e不包含在G的任一條回路中，那么連接結(jié)點(diǎn)u和v的邊只有e，而不會(huì)有其它連接u和v的任何路。因?yàn)槿绻B接u和v還有不同于邊e的路，此路與邊e就組成一條包含邊e的回路，從而導(dǎo)致矛盾。所以刪去邊e后，u和v就不連通，故邊e是割邊。,300頁(yè)（2）,如果u可達(dá)v

6、，它們之間可能不止一條路，在所有這些路中，最短路的長(zhǎng)度稱為u和v之間的距離（或短程線），記作d，如果從u到v是不可達(dá)的，則通常寫成 d =∞,300頁(yè)（3）,用Warshall算法求可達(dá)性矩陣。,i=1時(shí)，因?yàn)锳的第一行全為0，所以A不變。,i=2時(shí)，因?yàn)锳的第2列全為0，所以A不變。,i=3時(shí)，因?yàn)锳[2，3]=A[4，3]=1，將第3行加到第2行和第4行。,i=4時(shí)，因?yàn)锳[4,2]=1，將第四行加到第2行，A不變。i=5時(shí)，因?yàn)?/p>

7、A的第5列全為0，所以A不變。,故A的可達(dá)性矩陣為：,300頁(yè)（4）：寫出如圖7-3.11所示的圖G的完全關(guān)聯(lián)矩陣，并驗(yàn)證其秩如定理7-3.2所述。,完全關(guān)聯(lián)矩陣為:,此圖為連通圖，由定理7-3.2，其秩為5。,311頁(yè)（2）構(gòu)造一個(gè)歐拉圖，其結(jié)點(diǎn)數(shù)v和邊數(shù)e滿足下述條件,a)v，e的奇偶性一樣。b) v，e的奇偶性相反。 如果不可能，說(shuō)明原因。,v=3,e=3,v=5,e=5,v=4,e=4,v=4,e=6,v=7,e=8,v=6

8、,e=7,無(wú)向圖G具有一條歐拉回路，當(dāng)且僅當(dāng)G是連通的，并且所有結(jié)點(diǎn)度數(shù)全為偶數(shù)。下面的圖中所有結(jié)點(diǎn)度數(shù)全為偶數(shù)，所以都是歐拉圖。,311頁(yè)（6）,a)畫一個(gè)有一條歐拉回路和一條漢密爾頓回路的圖。,在無(wú)孤立結(jié)點(diǎn)圖G中，經(jīng)過(guò)圖中每條邊一次且僅有一次的一條回路，稱為歐拉回路。,給定圖G，經(jīng)過(guò)圖中每個(gè)結(jié)點(diǎn)恰好一次的回路稱作漢密爾頓回路。,b)畫一個(gè)有一條歐拉回路，但沒(méi)有一條漢密爾頓回路的圖。,c)畫一個(gè)沒(méi)有一條歐拉回路，但有一條漢密爾頓回路的

9、圖。,設(shè)G是一個(gè)具有k個(gè)奇數(shù)度結(jié)點(diǎn)（k>0）的連通圖，證明在G中的邊能剖分為k/2條路（邊不相重）。,證明：因?yàn)橐粋€(gè)圖中度數(shù)為奇數(shù)的結(jié)點(diǎn)個(gè)數(shù)必為偶數(shù)，故k必為偶數(shù)。將G中k個(gè)奇數(shù)度結(jié)點(diǎn)分為數(shù)目相等的兩組{u1,u2,…,uk/2}和{v1,v2,…,vk/2} 。對(duì)圖G添加邊(u1,v1), (u2,v2),…, (uk/2,vk/2)共k/2條邊，得到圖G’。由于圖G’中每個(gè)結(jié)點(diǎn)的度數(shù)均為偶數(shù)，故G’中存在一條歐拉回路。在

10、圖G’中刪去邊(u1,v1),得到一條歐拉路, 此路的兩個(gè)端點(diǎn)是u1和v1。結(jié)點(diǎn)u2和v2必在路的中間, 再刪去邊(u2,v2)，得到兩條邊互不相重的跡，這兩個(gè)跡的端點(diǎn)分別為u2和v2。結(jié)點(diǎn)u3和v3必在某一條跡的中間。再刪去邊(u3,v3) ，則將一條跡（包含u3和v3的跡）又分為兩條邊互不相重的跡，共得到3條互不相重的跡。以此繼續(xù)下去,直到所有的添加邊(u1,v1), (u2,v2),…, (uk/2,vk/2)全部刪去,得到

11、k/2條邊互不相重的路(跡)。,練習(xí) 317頁(yè)（1）,317頁(yè)（2）證明：少于30條邊的平面連通簡(jiǎn)單圖至少有一個(gè)頂點(diǎn)的度不大于4 。,證明： 用反證法。假設(shè)任一頂點(diǎn)的度均大于或等于5，則5v≤2e＜60，即v＜12。 又因?yàn)閑≤3v–6，所以5v≤2e≤6v–12 于是5v≤6v–12，即v≥12。矛盾。 因此至少有一個(gè)頂點(diǎn)的度不大于4,練習(xí)321頁(yè)（1）,(a) v*=5,e*=8,r*=5,(b) v*=7,e

12、*=13,r*=12,(c) v*=5,e*=6,r*=3,(d) v*=7,e*=12,r*=7,證明：若圖G是自對(duì)偶的，則v=v*，e=e*，即r*=v=v*=r，e=e*則由歐拉定理v-e+r=2得v-e+v=2，即e=2v-2。若圖G是自對(duì)偶的，則e=2v-2。,321頁(yè)(4)證明：若圖G是自對(duì)偶的，則e=2v-2。,P327 (6)(a)的最小生成樹(shù)：,P327 (6)(b)的最小生成樹(shù)有5棵，最小生成樹(shù)的樹(shù)權(quán)為11。