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

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

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

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

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

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

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

7、A的第5列全為0，所以A不變。,故A的可達(dá)性矩陣為：,300頁（4）：寫出如圖7-3.11所示的圖G的完全關(guān)聯(lián)矩陣，并驗證其秩如定理7-3.2所述。,完全關(guān)聯(lián)矩陣為:,此圖為連通圖，由定理7-3.2，其秩為5。,311頁（2）構(gòu)造一個歐拉圖，其結(jié)點數(shù)v和邊數(shù)e滿足下述條件,a)v，e的奇偶性一樣。b) v，e的奇偶性相反。 如果不可能，說明原因。,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,無向圖G具有一條歐拉回路，當(dāng)且僅當(dāng)G是連通的，并且所有結(jié)點度數(shù)全為偶數(shù)。下面的圖中所有結(jié)點度數(shù)全為偶數(shù)，所以都是歐拉圖。,311頁（6）,a)畫一個有一條歐拉回路和一條漢密爾頓回路的圖。,在無孤立結(jié)點圖G中，經(jīng)過圖中每條邊一次且僅有一次的一條回路，稱為歐拉回路。,給定圖G，經(jīng)過圖中每個結(jié)點恰好一次的回路稱作漢密爾頓回路。,b)畫一個有一條歐拉回路，但沒有一條漢密爾頓回路的圖。,c)畫一個沒有一條歐拉回路，但有一條漢密爾頓回路的

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

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

11、k/2條邊互不相重的路(跡)。,練習(xí) 317頁（1）,317頁（2）證明：少于30條邊的平面連通簡單圖至少有一個頂點的度不大于4 。,證明： 用反證法。假設(shè)任一頂點的度均大于或等于5，則5v≤2e＜60，即v＜12。 又因為e≤3v–6，所以5v≤2e≤6v–12 于是5v≤6v–12，即v≥12。矛盾。 因此至少有一個頂點的度不大于4,練習(xí)321頁（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是自對偶的，則v=v*，e=e*，即r*=v=v*=r，e=e*則由歐拉定理v-e+r=2得v-e+v=2，即e=2v-2。若圖G是自對偶的，則e=2v-2。,321頁(4)證明：若圖G是自對偶的，則e=2v-2。,P327 (6)(a)的最小生成樹：,P327 (6)(b)的最小生成樹有5棵，最小生成樹的樹權(quán)為11。