離散數(shù)學第7章 圖論 習題[教學內(nèi)容]

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

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

3、果仍是結(jié)點u,此路是閉跡。此路是閉跡。 閉跡上每個結(jié)點都是關(guān)聯(lián)偶數(shù)條邊閉跡上每個結(jié)點都是關(guān)聯(lián)偶數(shù)條邊,而而deg(u)為奇數(shù)為奇數(shù),所以至少還所以至少還 有一條關(guān)聯(lián)于結(jié)點有一條關(guān)聯(lián)于結(jié)點u的邊不在此閉跡上。繼續(xù)從的邊不在此閉跡上。繼續(xù)從u出發(fā)出發(fā),沿著該邊沿著該邊 到達另一個結(jié)點到達另一個結(jié)點u1,依次下去直到另一個奇數(shù)度結(jié)點停下。這樣依次下去直到另一個奇數(shù)度結(jié)點停下。這樣 經(jīng)過有限次后必可到達結(jié)點經(jīng)過有限次后必可到達結(jié)點v,這就是一條從這就是一條從u到到v的路。的路。 3優(yōu)學課堂 練習7-2（3）： 若圖G是不連通的，則G的補圖G是連通的。 證明：若G=是不連通的，可設圖G的連通分支為 GV

4、1,GV2,GVm(m2)。 由于任意兩個連通分支GVi,GVj不連通，因此Vi與Vj之 間的連線在補圖中，在G中任取兩個結(jié)點u和v，則u和v 的位置有兩種情況： 1)若u和v均在同一個連通分支GVi中,根據(jù)上面的分析， 可在另一個連通分支GVj（ij)中取一個結(jié)點w，使得 u與w，v 與w在G中連通，故有uwv，即u與v在G 中連通 2)若u與v分別屬于兩個不同的連通分支GVi與GVj，由 上面的分析可知，u與v在G中連通。 故當圖G不連通時，則補圖G是連通的 4優(yōu)學課堂 7-2（4）:當且僅當當且僅當G的一條邊的一條邊e不包含在不包含在G的回路中時，的回路中時， e才是才是G的割邊。的割邊

5、。 證明：必要性。（證明：必要性。（ e是是G的割邊）的割邊） 設設e是連通圖是連通圖G的割邊，的割邊，e關(guān)聯(lián)的兩個結(jié)點是關(guān)聯(lián)的兩個結(jié)點是u和和v。如果。如果e包含在包含在 G的一個回路中，那么除邊的一個回路中，那么除邊e=(u,v)外還有另一條分別以外還有另一條分別以u和和v為為 端點的路，所以刪去邊端點的路，所以刪去邊e后，后，G仍為連通圖，這與仍為連通圖，這與e是割邊相矛盾。是割邊相矛盾。 充分性。充分性。 如果邊如果邊e不包含在不包含在G的任一條回路中，那么連接結(jié)點的任一條回路中，那么連接結(jié)點u和和v的邊只的邊只 有有e，而不會有其它連接，而不會有其它連接u和和v的任何路。因為如果連接

6、的任何路。因為如果連接u和和v還有還有 不同于邊不同于邊e的路，此路與邊的路，此路與邊e就組成一條包含邊就組成一條包含邊e的回路，從而導的回路，從而導 致矛盾。所以刪去邊致矛盾。所以刪去邊e后，后，u和和v就不連通，故邊就不連通，故邊e是割邊。是割邊。 5優(yōu)學課堂 300頁（2） 如果u可達v，它們之間可能不止一條 路，在所有這些路中，最短路的長度 稱為u和v之間的距離（或短程線）， 記作d，如果從u到v是不可達的， 則通常寫成 d = 距離矩陣為 0 1 2 1 0 1 1 1 0 1 1 2 0 dij=1表示存在邊。 6優(yōu)學課堂 300頁（3） 用Warshall算法求可 達性矩陣。 鄰

7、接矩陣為 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 A= i=1時，因為A的第一行 全為0，所以A不變。 i=2時，因為A的第2列 全為0，所以A不變。 i=3時，因為A2，3=A4，3=1，將第3行 加到第2行和第4行。 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 A= i=4時，因為A4,2=1，將第四行 加到第2行，A不變。 i=5時，因為A的第5列全為0，所 以A不變。 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 P=

8、 故故A A的可達的可達 性矩陣為：性矩陣為： 7優(yōu)學課堂 距離矩陣為 0 1 0 1 1 1 0 2 1 0 0 8優(yōu)學課堂 300頁（4）：寫出如圖7-3.11所示的圖G的完 全關(guān)聯(lián)矩陣，并驗證其秩如定理7-3.2所述。 e1e2e3e4e5e6e7e8e9 A100001010 B011000100 C000110010 D110000001 E000011100 F001100001 完全關(guān)聯(lián)矩陣為: 此圖為連通圖，由定理 7-3.2，其秩為5。 9優(yōu)學課堂 311頁（2）構(gòu)造一個歐拉圖，其結(jié)點數(shù)v和邊數(shù)e滿足下述條件 a)v，e的奇偶性一樣。 b) v，e的奇偶性相反。 如果不可能，

9、說明原因。 v=3,e=3 v=5,e=5 v=4,e=4v=4,e=6 v=7,e=8 v=6,e=7 無向圖G具有一條歐拉回 路，當且僅當G是連通的，并且 所有結(jié)點度數(shù)全為偶數(shù)。下面的 圖中所有結(jié)點度數(shù)全為偶數(shù)，所 以都是歐拉圖。 10優(yōu)學課堂 311頁（6） a)畫一個有一條歐拉回路和一條漢密爾頓回路的圖。 在無孤立結(jié)點圖G中，經(jīng)過圖 中每條邊一次且僅有一次的一 條回路，稱為歐拉回路。 給定圖G，經(jīng)過圖中每 個結(jié)點恰好一次的回路稱作 漢密爾頓回路。 11優(yōu)學課堂 b)畫一個有一條歐拉回路，但沒有一條漢密爾頓回路的圖。 12優(yōu)學課堂 c)畫一個沒有一條歐拉回路，但有一條漢密爾頓回路的圖。

10、13優(yōu)學課堂 設設G是一個具有是一個具有k個奇數(shù)度結(jié)點（個奇數(shù)度結(jié)點（k0）的連通圖，）的連通圖， 證明在證明在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中存在一條歐拉回路。 在圖G中刪去邊(u1,v1),得到一條歐拉路, 此路的兩個端 點是u1和v1。結(jié)點u2和v2必在路的中間,

11、 再刪去邊 (u2,v2)，得到兩條邊互不相重的跡，這兩個跡的端點 分別為u2和v2。結(jié)點u3和v3必在某一條跡的中間。 再刪去邊(u3,v3) ，則將一條跡（包含u3和v3的跡）又分 為兩條邊互不相重的跡，共得到3條互不相重的跡。 以此繼續(xù)下去,直到所有的添加邊(u1,v1), (u2,v2), (uk/2,vk/2)全部刪去,得到k/2條邊互不相重的路(跡)。 14優(yōu)學課堂 練習 317頁（1） 15優(yōu)學課堂 317317頁（頁（2 2）證明：少于）證明：少于3030條邊的平面連通簡單圖條邊的平面連通簡單圖 至少有一個頂點的度不大于至少有一個頂點的度不大于4 4 。 證明：證明： 用反證法

12、。假設任一頂點的度均大于或等于用反證法。假設任一頂點的度均大于或等于5 5， 則則5v2e5v2e6060，即，即v v1212。 又因為又因為e3ve3v6 6，所以，所以5v2e6v5v2e6v1212 于是于是5v6v5v6v1212，即，即v12v12。矛盾。矛盾。 因此至少有一個頂點的度不大于因此至少有一個頂點的度不大于4 4 16優(yōu)學課堂 練習 321頁（1） (a) v*=5,e*=8,r*=5 17優(yōu)學課堂 (b) v*=7,e*=13,r*=12 18優(yōu)學課堂 (c) v*=5,e*=6,r*=3 19優(yōu)學課堂 (d) v*=7,e*=12,r*=7 20優(yōu)學課堂 證明：證明： 若圖若圖G是自對偶的，則是自對偶的，則v=v*，e=e*，即，即 r*=v=v*=r，e=e* 則由歐拉定理則由歐拉定理v-e+r=2 得得v-e+v=2，即，即e=2v-2。 若圖若圖G是自對偶的，則