圖論習(xí)題參考答案

1、精品文檔、應(yīng)用題題0: （1996年全國數(shù)學(xué)聯(lián)賽）有n （n>6）個人聚會，已知每個人至少認識其中的 n/2個人，而對任意的n/2個人，或 者其中有兩個人相互認識， 或者余下的n-n/2個人中有兩個人相互認識。 證明這n個人中必 有3個人互相認識。注：n/2表示不超過n/2的最大整數(shù)。證明 將n個人用n個頂點表示，如其中的兩個人互相認識，就在相應(yīng)的兩個頂點之間連一條邊，得圖Go由條件可知，G是具有n個頂點的簡單圖，并且有（1）對每個頂點x, Ng（x）上n/2；（2）對V的任一個子集 S,只要S =n/2, S中有兩個頂點相鄰或 V-S中有兩個頂點相鄰。需要證明G中有三個頂點兩兩相鄰。反

2、證，若G中不存在三個兩兩相鄰的頂點。在 G中取兩個相鄰的頂點x1和y1，記Ng（x1）= yi,y2,yt和 NG（yi）=x i,x2,xk,貝 U Ng（xi）和 NG（yi）不相交，并且 Ng（xi） （NG（yi）中沒有相鄰的頂點對。情況一；n=2r：此時n/2=r,由（1）和上述假設(shè)，t=k=r 且 NG（yi） = V-NG（xi）,但 Ng（xi） 中沒有相鄰的頂點對，由（2）, NG（yi）中有相鄰的頂點對，矛盾。情況二；n=2r+1:此時n/2 = r,由于 Ng（xi）和 NG（yi）不相交，t-r,k之r,所以 r+1 之t,r+1 之 k。 若1=+1,則 k=r,即

3、NG（yi）=r, Ng（xi） = V-NG（yi）,由（2）, Ng（xi）或 NG（yi）中有相鄰的頂點 對，矛盾。故 kwr+l,同理 twr+l。所以 t=r,k=r。記 w V- Ng（xi） UNg'i）,由（2）, w 分 別與 Ng（xi）和 NG（yi）中一個頂點相鄰，設(shè)wxi0e E, wyj°W E。若 xi0yj°WE,則 w, xi0, yj0 兩兩相鄰，矛盾。若xi0yj0*E,則與xi0相鄰的頂點只能是（NG（xi）-y j0） U w,與yj0相鄰的頂點 只能是（NG（yi）-x j0） U w。但與w相鄰的點至少是3,故Ng（xi

4、）U NG（yi）中存在一個不同于 xi0和yj0頂點z與w相鄰,不妨設(shè)zNg（xi）,貝U z, w , xi0兩兩相鄰，矛盾。題1:已知圖的結(jié)點集 V=a,b,c,d以及圖G和圖D的邊集合分別為:E(G)=(a,a), (a,b), (b,c), (a,c)E(D)=< a,b>, <a,c>, <c,d>, <c,a>, <c,b>試作圖G和圖D,寫出各結(jié)點的度數(shù)，回答圖G、圖D是簡單圖還是多重圖?解:圖 G 中：deg(a)=4 , deg(b)=2 , deg=2, deg(d)=0圖 D 中：deg(a)=3 , deg(

5、b)=2 , deg=4, deg(d)=1圖 D 是簡單圖.其中 deg+(a)=2, deg-(a)=1, deg+(b)=0, deg-(b)=2, deg+(c)=3, deg-(c)=1, deg-(d)=1.題2:設(shè)簡單連通無向圖 G有12條辿，G中有2個1度結(jié)點，其余結(jié)點度數(shù)為3.求G中有多少個結(jié)點.試作一個滿足該條件的簡單無向圖.解：設(shè)圖G有x個結(jié)點，有握手定理2M1+2父2+3父4+3父(x22 =12x23x=24+21 -18 = 27x= 9圖G有9個結(jié)點.圖見例3圖.(圖/、唯一)題3:設(shè)簡單連通無向圖 G有9條邊，G中有4個3度結(jié)點，2個2度結(jié)點，3個4度結(jié)點,XX

6、例3圖2個1度結(jié)點，其余結(jié)點度數(shù)為2 .求G中后多少個結(jié)點.題4無向完全圖K3, K4,及3個結(jié)點的有向完全圖K3K4題5:兩個圖同構(gòu)后卜列必要條件：(1) 結(jié)點數(shù)相同；.3個結(jié)點的有向完全圖(3)度數(shù)相同的結(jié)點數(shù)相同但它們不是兩個圖同構(gòu)的充分條件，下圖中(a)和(b)滿足上述三個條件，但這兩個圖并不同構(gòu).到目前為止，判斷兩個圖同構(gòu)，只能根據(jù)定義，還沒有其它簡單而有效的方法題6:三名商人各帶一隨從乘船過河，一只小船只能容納2人，由他們自己劃行。隨從們密約,在河的任一案，一旦隨從的人數(shù)比商人多， 就殺人越貨。但是如何乘船渡河的大權(quán)掌握在商 人手中，商人們怎樣安排每次乘船方案才能安全渡河？ 解：用

7、圖論模型求解如下：每個狀態(tài)有三個因素：此岸構(gòu)成，彼岸構(gòu)成，船所在。此岸 al bl, al為商人個數(shù)，bl 為隨從個數(shù)，al > bl, a1,b1=0,1,2,3,或 a1=0,b1=0,1,2,3。彼岸 a2 b2, a2為商人個數(shù)，b2為隨從個數(shù)，a2> b2, a2,b2=0,1,2,3,或 a2=0,b2=0,1,2,3。注：a1+a2=b1+b2=3; 0表示船在此岸，1表示在彼岸。可行狀態(tài)有:33|00|0, 32|01|0, 31|02|0, 22|11|0, 11|22|0, 03|30|0, 02|31|0, 01|32|0,00|33|1。根據(jù)上圖，求從33|

8、00|0到00|33|1的路徑，可得解如下：33|00|0-31|02|1-32|01|0-30|03|1-31|02|0-11|22|1-22|11|0-02|31|1-03|30|0-01|32|1-02|31|0- 00|33|1?；颍?3|00|0-31|02|1-32|01|0-30|03|1-31|02|0-11|22|1-22|11|0-02|31|1-03|30|0-01|32|1-11|22|0- 00|33|1?；颍?3|00|0-22|11|1-32|01|0-30|03|1-31|02|0-11|22|1-22|11|0-02|31|1-03|30|0-01|32|1-

9、11|22|0- 00|33|1。題7在平面上有n個點S=xi,X2,x n,其中任兩個點之間的距離至少是1,證明在這n個點中距離為1的點對數(shù)不超過 3n。證明 首先建立一個圖 G= (V, E),其中V就取S中的n個頂點，V中兩個點有邊相連 當且僅當兩點之間的距離恰好是 1。則所得圖G是一個簡單圖，S中距離為1的點對數(shù)就是 G的邊數(shù)。因此我們只需證明 m(G)E3n。我們考慮G中每個頂點的度，可以證明：deg(Xi)<6,i=1,2,，n。讓Xi是G中的任一個頂點，且與Xi相鄰的頂點為y1,y2,yk,則y1,y2,yk分布在以Xi為圓心的單位圓周上。所以k= deg(Xi)<6

10、 ,i=1,2, ,n。由握手定理得n2m(G)= '、' d(vi)三 6ni =4故 m(G) <3no 題8 n個點由若干線段連接著。已知每一點與另外任何一點都有道路相連通。而任何兩點都沒有兩種不同的道路。證明：線段總數(shù)為n-1。證明 構(gòu)造圖G:將問題中給定的n個點作為頂點，線段作為邊。根據(jù)給定的條件，所得圖G是含有n個頂點的簡單圖，每一對頂點之間有且只有一條路連接，因此G是連通圖，并且沒有回路(否則，該回路上兩個不同的頂點之間有兩條不同的路)，所以圖G是一棵樹。題9:設(shè)無向圖G有12條邊，已知G中度數(shù)為3的節(jié)點個數(shù)為6個，其余結(jié)點的度數(shù)均小于3,問G中至少有多少頂

11、點？解：由定理可知，圖中所有節(jié)點的度數(shù)之和應(yīng)為邊數(shù)的2倍，即12 X 2 =24,卻掉度數(shù)為3的6個結(jié)點的總度數(shù)18,還剩6度，又由于其余結(jié)點的度數(shù)小于 3,故度數(shù)只能是0, 1, 2, 若其余結(jié)點的度數(shù)均為 2,則至少需3個結(jié)點，故圖G中至少有9個結(jié)點。題10:若圖G是不連通的，則 G的補圖G是連通的。證明：設(shè)6= (V, E)不連通，則設(shè)其連通分支為G，G2, Gs,其相應(yīng)的節(jié)點集為 V，V2, Vs,任取G中的兩個節(jié)點u, vCV,1)、若u, v分屬于G中不同的連通分支，則(u,v) G ,因此u, v在G中連通。2)、若u, v分屬于G中同一個連通分支，則從另一連通分支中任取一結(jié)點w

12、,則(u,w) G ,(v,w) C G ,于是在G中存在一條道路 uwv,使得u, v連通。綜上所述可知，對于 G中任意2個結(jié)點，u, v總有路相連，故 G是連通的。題11:當且僅當G的一條邊e不包含在G的回路中，e才是G的割邊(橋)。證明：必要性：設(shè)e是連通圖G的割邊，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的

13、回路，從而導(dǎo)致矛盾，所以，刪去邊 e后，u和v就不連通，故邊 e為割邊。題12： n個城市由k條公路網(wǎng)絡(luò)連接（一條公路定義為兩個城市間的一條道路，它們之間不能通過任何中間城市），證明：如果有k> 1 （n-1）（n-2）則人們總能通過連接城市的公路在任何城市間旅行。證明：將城市作為結(jié)點，將連接兩個城市的公路作為邊，則問題等價于證明具有n個結(jié)點k 條邊的簡單無向圖 G,若滿足k> 1（n-1）（n-2）,則是連通圖。當n=2時，結(jié)論顯然成立，下2面證明n>2時，結(jié)論也成立。假設(shè)G不連通，不妨設(shè)G有2個連通分支, 滿足Vi和V2分屬于不同的連通分支。設(shè)由設(shè)由V2生成的G的子圖G2

14、中有n2個結(jié)點則可將G中的結(jié)點集V分為兩個子集 Vi和V2, Vi生成的G的子圖Gi中有ni個結(jié)點ki條邊，k2條邊,則ni+n2=n, ki+k2=k, ni, n2之i由于G是簡單無向圖，故 Gi和G2也是簡單無向圖，從而有：ki < ni(ni-i), k2< n2(n2-i)22ii(2)k=ki +k2 _ ni(ni-i)+n2(n2-i)22另一方面，由已知k> (n-i)(n-2)= (ni+n2-i)(n i+n2-2)22由于n>2 ,因此ni和n2至少有一個大于等于2,不妨設(shè)ni >2,由(2)得k> (ni+n2-i)(ni+n2-2

15、)= - ni(ni+n2-2)+ (n2-i)(ni+n2-2)222iini(ni-i)+n2 (n2-i)22與式(i)矛盾，故G是連通圖。題13:判斷下圖是否能一筆畫出，并說明理由。V Vo* Vn圖（a）解：圖（a）中所有結(jié)點（除Vo, Vn外）的度數(shù)為圖（b）2或4, deg v° =deg Vn = i ,故有歐拉定理可知，圖（a）包含歐拉通路，由 Vo出發(fā)到達Vn必有一條包含所有邊且只包含一次的通路。2,是歐拉圖，見2,是歐拉圖，見4,是歐拉圖，見下 d)。圖(b)中所有結(jié)點(除 V0, Vn外)的度數(shù)為2或4, deg vo =deg vn = 5,故有歐拉定理 可

16、知，圖(b)包含歐拉通路，由 V0出發(fā)到達Vn必有一條包含所有邊且只包含一次的通路。題14:構(gòu)造一個歐拉圖，其結(jié)點數(shù)n與邊數(shù)m滿足下列條件(1)、n, m的奇偶性一樣的簡單圖。(2)、n, m的奇偶性相反的簡單圖。如果不可能，請說明原因。解：(1)、4個結(jié)點4條邊，結(jié)點數(shù)和邊數(shù)都是偶數(shù)，每個結(jié)點的度數(shù)均為 下圖(a)。3個結(jié)點3條邊，結(jié)點數(shù)和邊數(shù)都是奇數(shù)，每個結(jié)點的度數(shù)為 下圖(b)。(2)、6個結(jié)點9條邊，3個結(jié)點的度數(shù)為2, 3個結(jié)點的度數(shù)均為 圖(c)。5個結(jié)點10條邊，每個結(jié)點的度數(shù)為 4,是歐拉圖，見下圖(題15:設(shè)G是一個具有n個結(jié)點的簡單無向圖，n之3,設(shè)G的結(jié)點表示n個人，G的

17、邊表 示他們間的友好關(guān)系，若兩個結(jié)點杯一條邊連接，當且僅當對應(yīng)的人是朋友。(1)、結(jié)點的度數(shù)能做怎樣的解釋？(2)、G是連通圖能做怎樣的解釋？(3)、假定任意兩個人合起來認識所留下的n-2個人，證明n個人能站成一排，使得中間每個人兩旁站著自己的朋友，而兩端的兩個人，他們每個人旁邊只站著他的一個朋友。(4)、證明對于n>4, (3)中保證n個人能站成一圈，使每個人的兩旁站著自己的朋友。解：(1)、結(jié)點u的度數(shù)deg (u)表明u與deg (u)個人是朋友。(2)、G是連通圖表明任意兩個人可通過其朋友及朋友的朋友結(jié)識，建立友好關(guān)系。(3)、由已知任意兩個人合起來認識其余的n-2個人，即對 G

18、中任意兩個結(jié)點 u, v,deg(u)+deg(v)之n-2,且其余n-2個結(jié)點與u或v鄰接。若 u 與 v 鄰接，貝U deg(u)+deg(v)占n-2+1=n-1。若u與v不鄰接，若 deg(u)+deg(v) =n-2 ,則對于任意的 w C V-u,v , w與u鄰接(w與v 鄰接)，但不能同時與u, v鄰接，設(shè)w與u鄰接，則w必不與v鄰接，則結(jié)點w和u都不與 v鄰接，也就是 w和u都不認識v,從而結(jié)點w和結(jié)點u的度數(shù)之和<n-2 (即w和u兩個人 合起來不能夠認識所留下的n-2個人)，與假設(shè)矛盾。因此，deg(u)+deg(v)之n-1,即圖G中存在哈密頓通路，按照此通路的結(jié)

19、點排列可得n個人排列成一排，使中間的每個人兩邊都是朋友，而兩端的兩個人，一邊站著的也是朋友。(4)、由(3)可知，當n至3時，對G中任意兩個結(jié)點 u, v有，deg(u)+deg(v)至n-1。 下面證明，當n之4時，deg(u)+deg(v)2n。若u和v鄰接，顯然成立。若 u 和 v 不鄰接,貝U deg(u)+deg(v) >n-1 ,否貝U,若 deg(u)+deg(v) =n-1 ,則 V-u,v至少有 2 個結(jié)點(因n之4),設(shè)為小t ,且w與u, v均鄰接，t只與u, v之一鄰接。設(shè)t與u鄰接， 則t和u與結(jié)點v都不鄰接，與假設(shè)矛盾，故對任意結(jié)點u, v, deg(u)+d

20、eg(v) >n-1 ,即deg(u)+deg(v)之n。故圖G中存在哈密頓回路，按照此回路的結(jié)點排列，即為所求的圈，滿足n個人能站成一圈，使每個人的兩旁站著臼己的朋友。題16:設(shè)G是有11個或更多結(jié)點的圖，證明G或G (補圖)是非平面圖。證明：反證法：設(shè) G和G都是平面圖，設(shè) G和G的結(jié)點數(shù)分別為n和3 ,邊數(shù)分別為 m 和m ,貝Un= n , m+ m = n(n-1)2由歐拉定理可知，mW3n-6, m <3n-6 1n(n-1)= m+ m _ 3n-6+3n-6=6n-12 2即n2-13n+24 -0從而得出n<11 ,與n A11相矛盾，故G和G不可能同時為平

21、面圖，即n211時，G或G (補圖)是非平面圖。題17: 一棵樹有n2個結(jié)點度數(shù)為2, n3個結(jié)點度數(shù)為3,，nk個結(jié)點度數(shù)為k,問它有幾 個度數(shù)為1的結(jié)點。解：設(shè)樹T中有n1個度數(shù)為1的結(jié)點，則樹中邊數(shù) m為：m=n+n2+n3+nk-1又由于任意圖中結(jié)點度數(shù)之和等于邊數(shù)的2倍，故：n1+2n2+3n3+knk=2(n1+n2+n3+ +nk-1)故：n1= (3-2)n3+(4-2)n4+ - +(k-2)n k+2題18:證明在完全二叉樹中，邊的總數(shù) m等于2(nt-1), nt是樹葉總數(shù)。證明：對分枝結(jié)點數(shù)i用數(shù)學(xué)歸納法：當i=1時，邊數(shù)m=2 ,樹葉數(shù)nt=2,故m=2(nt-1)成

22、立。假設(shè)i=k時(k21)成立，下面證明i=k+1時結(jié)論成立。由于樹T是完全二叉樹，因此 T中必存在一分枝結(jié)點v, v的兩個兒子v1 , v2均是樹葉。在T中刪去v1 , v2得T',則T'是分枝結(jié)點數(shù)為k的完全二叉樹，此時 v為樹葉，分枝結(jié)點數(shù)i'=i-1=k+1-1=k樹葉數(shù)nt'=nt-2+1=nt-1邊數(shù)m'=m-2由歸納假設(shè)，m'=2(nt'-1)所以：m-2=2(nt-1-1),即 m=2(nt-1)。題19:給設(shè)d= (d1,d2,dn),其中di為正數(shù)，i=1,2,n。若存在n個結(jié)點的簡單圖，使得 結(jié)點vi的度數(shù)為di,則

23、稱d是可圖解的。下面給出的各序列中哪些是可圖解的，哪些不是，為什么？(1)、 (1,1,1, 2,(4)、 (2, 3, 3, 4,、(2, 3, 3, 4,3, (2)、(0, 1,4, 5)(5)、(2, 3,5, 6)(8)、(1, 3,1, 2, 3, 3)4, 4, 5)3, 4, 5, 6, 6)(3)、 (3, 3, 3, 3)(6)、 (2, 3, 3, 3)(9)、 (2, 2, 4)(10)、 (1, 2, 2, 3, 4, 5)題20:給無向完全圖Kn (n>7)的各邊隨意涂上紅色或綠色，若已知從某個結(jié)點 v0引出 的n-1條邊中至少有六條邊涂紅色，則存在紅色的K4

24、或綠色的K3。證明：設(shè)x1,x2,x3,x4,x5,x6是與v0相鄰的六條邊涂紅色。根據(jù) Ramsey (3, 3) =6的證 明可知，在x1,x2,x3,x4,x5,x6中，或有3個相互鄰接的頂點(涂紅色)，這3個頂點與v0 一 起構(gòu)成紅色的K4；或者有3個互不相鄰的頂點(綠色)，這3個頂點構(gòu)成綠色的 K3。題21:證明：在任何兩個或兩個以上人的組內(nèi)，存在兩個人在組內(nèi)有相同個數(shù)的朋友。證明：此題可轉(zhuǎn)化為圖論的問題來處理：把每個人對應(yīng)成相應(yīng)的結(jié)點，兩個人具有朋友關(guān)系當且僅當相應(yīng)的結(jié)點相鄰，顯然該圖是簡單圖，所以原命題等價于證明在該無向簡單圖中一 定存在兩個結(jié)點的度數(shù)相等。反設(shè)，該無向簡單圖 G

25、中任何一對結(jié)點的度數(shù)都不相等，并設(shè)結(jié)點數(shù)為no又因為圖G是簡單圖，所以結(jié)點的度數(shù)只能為：0, 1, 2,，n-1。那么在圖G中，存在度數(shù)為 n-1的結(jié)點，與所有結(jié)點相鄰，同時又存在度數(shù)為0的結(jié)點,與所有結(jié)點都不相鄰，因此產(chǎn)生矛盾。所以該無向簡單圖中一定存在兩個結(jié)點的度數(shù)相等。所以在任何兩個或兩個以上人的組內(nèi)，存在兩個人在組內(nèi)有相同個數(shù)的朋友。題22、設(shè)G為n個結(jié)點的簡單無向圖。(1)、若G的邊數(shù)m=(1/2)(n-1)(n-2)+2 ,證明G是哈密爾頓圖。(2)、若G的邊數(shù)m=(1/2)(n-1)(n-2)+1，那么圖G是否一定為哈密爾頓圖？請闡述你的理由。分析:因為有定理：設(shè) G= (V,

26、E)是n階(n> 3)無向簡單圖，若對于任意的不相鄰的 結(jié)點Vi, VjCV,有dev(vi)+dev(vj)>n,則G是哈密爾頓圖。那么只要證明對任意的不相鄰 結(jié)點 Vi, VjCV,有 dev(Vi)+dev(vj)>n 即可。解：(1)反證法：假設(shè)存在不相鄰的結(jié)點Vi, VjCV,有dev(Vi)+dev(vj)w n-1。另V仔vi,環(huán), Gi =G-V i ,則Gi是(n-2)階簡單圖，它的邊數(shù) m1滿足m1=(1/2)(n-1)(n-2)+2-(dev(v i)+dev(vj) > (1/2)(n-1)(n-2)+2-(n-1)= (1/2)(n-2)(n-

27、3)+1這與Gi是(n-2)階的簡單圖矛盾(注：(n-2)階的簡單圖的最大邊數(shù)為(1/2)(n-2)(n-3)所以G中任何兩個相鄰的結(jié)點度數(shù)之和均大于等于no再根據(jù)定理：設(shè) G= (V, E)是n階(n>3)無向簡單圖，若對于任意的不相鄰的結(jié)點vvjCV,有 dev(vi)+dev(vj) >n,則 G 是哈密爾頓圖。所以G是哈密爾頓圖。(2)若G的邊數(shù)m=(1/2)(n-1)(n-2)+1 ,那么圖G是不一定為哈密爾頓圖，請看下圖不是哈 密爾頓圖。題23、把平面分成x個區(qū)域，每兩個區(qū)域都相鄰，問 x最大為幾？(可作為選擇題)分析:如果把每個區(qū)域放一個結(jié)點，當兩區(qū)域相鄰就在相應(yīng)的兩個結(jié)點間連一條邊，這樣 就構(gòu)造了一個簡單和完全的平