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

1、、應(yīng)用題題0:(1996年全國(guó)數(shù)學(xué)聯(lián)賽)有n(n6)個(gè)人聚會(huì)，已知每個(gè)人至少認(rèn)識(shí)其中的n/2個(gè)人，而對(duì)任意的n/2個(gè)人，或者其中有兩個(gè)人相互認(rèn)識(shí)，或者余下的n-n/2個(gè)人中有兩個(gè)人相互認(rèn)識(shí)。證明這n個(gè)人中必有3個(gè)人互相認(rèn)識(shí)。注：n/2表示不超過(guò)n/2的最大整數(shù)。證明將n個(gè)人用n個(gè)頂點(diǎn)表示，如其中的兩個(gè)人互相認(rèn)識(shí)，就在相應(yīng)的兩個(gè)頂點(diǎn)之間連一條邊，得圖Go由條件可知，G是具有n個(gè)頂點(diǎn)的簡(jiǎn)單圖，并且有(1)對(duì)每個(gè)頂點(diǎn)x,NG(x)n/2;(2)對(duì)V的任一個(gè)子集S,只要S=n/2,S中有兩個(gè)頂點(diǎn)相鄰或V-S中有兩個(gè)頂點(diǎn)相鄰。需要證明G中有三個(gè)頂點(diǎn)兩兩相鄰。反證，若G中不存在三個(gè)兩兩相鄰的頂點(diǎn)。在G中取

2、兩個(gè)相鄰的頂點(diǎn)x1和y1，記NG(x1)=yi,y2,yt和NG(yi)=xi,X2,xk,貝UNg(xi)和NG(yi)不相交，并且Ng(xi)(NG(yi)中沒(méi)有相鄰的頂點(diǎn)對(duì)。情況一；n=2r：此時(shí)n/2=r,由(i)和上述假設(shè)，t=k=r且NG(yi)=V-NG(xi),但Ng(xi)中沒(méi)有相鄰的頂點(diǎn)對(duì)，由(2),NG(yi)中有相鄰的頂點(diǎn)對(duì)，矛盾。情況二；n=2r+i:此時(shí)n/2=r,由于Ng(xi)和NG(yi)不相交，tr,kr,所以r+it,r+ik。若1=+1，則k=r,即NG(yi)=r,Ng(xi)=V-NG(yi),由(2),Ng(xi)或NG(yi)中有相鄰的頂點(diǎn)對(duì)，矛

3、盾。故kwr+1,同理twr+1。所以t=r,k=r。記wV-Ng(xi)UNG(yi),由(2),w分別與Ng(xi)和NG(yi)中一個(gè)頂點(diǎn)相鄰,設(shè)wxi0E,wyj0E。若xi°yj0E,則w,xi0,yj0兩兩相鄰，矛盾。若xi0yj0E,則與xi0相鄰的頂點(diǎn)只能是(NG(xi)-yj0)Uw,與yj0相鄰的頂點(diǎn)只能是(NG(yi)-xj0)Uw。但與w相鄰的點(diǎn)至少是3,故Ng(xi)UNG(yi)中存在一個(gè)不同于xi0和yj0頂點(diǎn)z與w相鄰，不妨設(shè)zNg(xi),則z,w,xi0兩兩相鄰，矛盾。題1:已知圖的結(jié)點(diǎn)集V=a,b,c,d以及圖G和圖D的邊集合分別為:E(G)=(

4、a,a),(a,b),(b,c),(a,c)E(D)=<a,b>,<a,c>,<c,d>,<c,a>,<c,b>試作圖G和圖D,寫(xiě)出各結(jié)點(diǎn)的度數(shù)，回答圖G、圖D是簡(jiǎn)單圖還是多重圖?例2圖圖G圖D2個(gè)2度結(jié)點(diǎn)，3個(gè)4度結(jié)點(diǎn),2個(gè)1度結(jié)點(diǎn)，其余結(jié)點(diǎn)度數(shù)圖G中：deg(a)=4,deg(b)=2,deg=2,deg(d)=0圖D中：deg(a)=3,deg(b)=2,deg=4,deg(d)=1圖D是簡(jiǎn)單圖.其中deg+(a)=2,deg-(a)=1,deg+(b)=0,deg-(b)=2,deg+(c)=3,deg-(c)=1,deg-(

5、d)=1.題2:設(shè)簡(jiǎn)單連通無(wú)向圖G有12條邊，G中有2個(gè)1度結(jié)點(diǎn),其余結(jié)點(diǎn)度數(shù)為3.求G中有多少個(gè)結(jié)點(diǎn).試作一個(gè)滿(mǎn)足該條件的簡(jiǎn)單無(wú)向圖.解：設(shè)圖G有x個(gè)結(jié)點(diǎn)，有握手定理21+22+34+3(x223)=1223x24211827x=9圖G有9個(gè)結(jié)點(diǎn).圖見(jiàn)例3圖.(圖不唯一)題3:設(shè)簡(jiǎn)單連通無(wú)向圖G有9條邊，G中有4個(gè)3度結(jié)點(diǎn),為2.求G中有多少個(gè)結(jié)點(diǎn).題4無(wú)向完全圖K3,K4,及3個(gè)結(jié)點(diǎn)的有向完全圖.題5:兩個(gè)圖同構(gòu)有下列必要條件:(1) 結(jié)點(diǎn)數(shù)相同；(2) 邊數(shù)相同；(3) 度數(shù)相同的結(jié)點(diǎn)數(shù)相同.(a)和(b)滿(mǎn)足上述三個(gè)條件，但這兩個(gè)圖并但它們不是兩個(gè)圖同構(gòu)的充分條件，下圖中不同構(gòu).到目前

6、為止，判斷兩個(gè)圖同構(gòu)，只能根據(jù)定義，還沒(méi)有其它簡(jiǎn)單而有效的方法題6:三名商人各帶一隨從乘船過(guò)河，一只小船只能容納2人，由他們自己劃行。隨從們密約,在河的任一案，一旦隨從的人數(shù)比商人多，就殺人越貨。但是如何乘船渡河的大權(quán)掌握在商人手中，商人們?cè)鯓影才琶看纬舜桨覆拍馨踩珊樱拷猓河脠D論模型求解如下：每個(gè)狀態(tài)有三個(gè)因素：此岸構(gòu)成，彼岸構(gòu)成，船所在。此岸albl,al為商人個(gè)數(shù)，bl為隨從個(gè)數(shù)，al>bl,a1,b1=0,1,2,3,或a1=0,b1=0,1,2,3。彼岸a2b2,a2為商人個(gè)數(shù)，b2為隨從個(gè)數(shù)，a2>b2,a2,b2=0,1,2,3,或a2=0,b2=0,1,2,3。注

7、：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|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|

8、1-03|30|0-01|32|1-11|22|0-00|33|1。或：33|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-11|22|0-00|33|1。題7在平面上有n個(gè)點(diǎn)S=xi,X2,xn,其中任兩個(gè)點(diǎn)之間的距離至少是1,證明在這n個(gè)點(diǎn)中距離為1的點(diǎn)對(duì)數(shù)不超過(guò)3n。證明首先建立一個(gè)圖G=(V,E),其中V就取S中的n個(gè)頂點(diǎn)，V中兩個(gè)點(diǎn)有邊相連當(dāng)且僅當(dāng)兩點(diǎn)之間的距離恰好是1。則所得圖G是一個(gè)簡(jiǎn)單圖，S中距離為1的點(diǎn)對(duì)數(shù)就是G的邊數(shù)。因此我們只需證明m(G)3n。我們考慮G中每個(gè)頂點(diǎn)

9、的度，可以證明：deg(Xi)6,i=1,2,，n。讓Xi是G中的任一個(gè)頂點(diǎn)，且與Xi相鄰的頂點(diǎn)為y1,y2,yk,則y1,y2,yk分布在以Xi為圓心的單位圓周上。所以k=deg(Xi)6,i=1,2,，n。由握手定理得n2m(G尸d(vi)6ni1故m(G)3n。題8n個(gè)點(diǎn)由若干線段連接著。已知每一點(diǎn)與另外任何一點(diǎn)都有道路相連通。而任何兩點(diǎn)都沒(méi)有兩種不同的道路。證明：線段總數(shù)為n-1。證明構(gòu)造圖G:將問(wèn)題中給定的n個(gè)點(diǎn)作為頂點(diǎn)，線段作為邊。根據(jù)給定的條件，所得圖G是含有n個(gè)頂點(diǎn)的簡(jiǎn)單圖，每一對(duì)頂點(diǎn)之間有且只有一條路連接，因此G是連通圖，并且沒(méi)有回路(否則，該回路上兩個(gè)不同的頂點(diǎn)之間有兩條不

10、同的路)，所以圖G是一棵樹(shù)。題9:設(shè)無(wú)向圖G有12條邊，已知G中度數(shù)為3的節(jié)點(diǎn)個(gè)數(shù)為6個(gè)，其余結(jié)點(diǎn)的度數(shù)均小于3,問(wèn)G中至少有多少頂點(diǎn)？解：由定理可知，圖中所有節(jié)點(diǎn)的度數(shù)之和應(yīng)為邊數(shù)的2倍，即12x2=24,卻掉度數(shù)為3的6個(gè)結(jié)點(diǎn)的總度數(shù)18,還剩6度，又由于其余結(jié)點(diǎn)的度數(shù)小于3,故度數(shù)只能是0,1,2,若其余結(jié)點(diǎn)的度數(shù)均為2,則至少需3個(gè)結(jié)點(diǎn)，故圖G中至少有9個(gè)結(jié)點(diǎn)。題10:若圖G是不連通的，則G的補(bǔ)圖G是連通的。證明：設(shè)6=(V,E)不連通，則設(shè)其連通分支為Gi,G2,Gs,其相應(yīng)的節(jié)點(diǎn)集為Vi,V2,Vs,任取G中的兩個(gè)節(jié)點(diǎn)u,vCV,_1)、若u,v分屬于G中不同的連通分支，則(u,v

11、)G,因此u,v在G中連通。2)、若u,v分屬于G中同一個(gè)連通分支，則從另一連通分支中任取一結(jié)點(diǎn)w,則(u,w)G,(v,w)CG,于是在G中存在一條道路uwv,使得u,v連通。綜上所述可知，對(duì)于G中任意2個(gè)結(jié)點(diǎn)，u,v總有路相連，故G是連通的。題11:當(dāng)且僅當(dāng)G的一條邊e不包含在G的回路中，e才是G的割邊(橋)。證明：必要性：設(shè)e是連通圖G的割邊，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)槿?/p>

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

13、個(gè)子集Vi和V2,滿(mǎn)足Vi和V2分屬于不同的連通分支。設(shè)由Vi生成的G的子圖Gi中有ni個(gè)結(jié)點(diǎn)ki條邊，設(shè)由V2生成的G的子圖G2中有n2個(gè)結(jié)點(diǎn)k2條邊，則ni+n2=n,ki+k2=k,ni,n2i由于G是簡(jiǎn)單無(wú)向圖，故Gi和G2也是簡(jiǎn)單無(wú)向圖，從而有：1 ikini(ni-i),k2n2(n2-i)2 21 ik=ki+k2ni(ni-i)+n2(n2-i)(i)2 2另一方面，由已知k>(n-i)(n-2)=(ni+n2-i)(ni+n2-2)(2)22由于n>2,因此ni和n2至少有一個(gè)大于等于2,不妨設(shè)ni2,由(2)得k>(ni+n2-i)(ni+n2-2)=ni

14、(ni+n2-2)+(n2-i)(ni+n2-2)222iini(ni-i)+n2(n2-i)22與式(i)矛盾，故G是連通圖。題i3:判斷下圖是否能一筆畫(huà)出，并說(shuō)明理由。V V0* Vn圖(a)解：圖(a)中所有結(jié)點(diǎn)(除Vo, vn外)的度數(shù)為圖(b)2或4, deg vo =deg vn = i ,故有歐拉定理可知，圖(a)包含歐拉通路，由vo出發(fā)到達(dá)vn必有一條包含所有邊且只包含一次的通路。圖(b)中所有結(jié)點(diǎn)(除v0,vn外)的度數(shù)為2或4,degvo=degvn=5,故有歐拉定理可知，圖(b)包含歐拉通路，由vo出發(fā)到達(dá)vn必有一條包含所有邊且只包含一次的通路。題14：構(gòu)造一個(gè)歐拉圖，

15、其結(jié)點(diǎn)數(shù)n與邊數(shù)m滿(mǎn)足下列條件(1)、n,m的奇偶性一樣的簡(jiǎn)單圖。(2)、n,m的奇偶性相反的簡(jiǎn)單圖。如果不可能，請(qǐng)說(shuō)明原因。2,是歐拉圖，見(jiàn)2,是歐拉圖，見(jiàn)4,是歐拉圖，見(jiàn)下解：(1)、4個(gè)結(jié)點(diǎn)4條邊，結(jié)點(diǎn)數(shù)和邊數(shù)都是偶數(shù)，每個(gè)結(jié)點(diǎn)的度數(shù)均為下圖(a)。3個(gè)結(jié)點(diǎn)3條邊，結(jié)點(diǎn)數(shù)和邊數(shù)都是奇數(shù)，每個(gè)結(jié)點(diǎn)的度數(shù)為下圖(b)。(2)、6個(gè)結(jié)點(diǎn)9條邊，3個(gè)結(jié)點(diǎn)的度數(shù)為2,3個(gè)結(jié)點(diǎn)的度數(shù)均為圖(c)。5個(gè)結(jié)點(diǎn)10條邊，每個(gè)結(jié)點(diǎn)的度數(shù)為4,是歐拉圖，見(jiàn)下圖(題15:設(shè)G是一個(gè)具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單無(wú)向圖，n3,設(shè)G的結(jié)點(diǎn)表示n個(gè)人，G的邊表示他們間的友好關(guān)系，若兩個(gè)結(jié)點(diǎn)杯一條邊連接，當(dāng)且僅當(dāng)對(duì)應(yīng)的人是朋友。(

16、1)、結(jié)點(diǎn)的度數(shù)能做怎樣的解釋?zhuān)?2)、G是連通圖能做怎樣的解釋?zhuān)?3)、假定任意兩個(gè)人合起來(lái)認(rèn)識(shí)所留下的n-2個(gè)人，證明n個(gè)人能站成一排，使得中間每個(gè)人兩旁站著自己的朋友，而兩端的兩個(gè)人，他們每個(gè)人旁邊只站著他的一個(gè)朋友。(4)、證明對(duì)于n4,(3)中保證n個(gè)人能站成一圈，使每個(gè)人的兩旁站著自己的朋友。解：(1)、結(jié)點(diǎn)u的度數(shù)deg(u)表明u與deg(u)個(gè)人是朋友。(2)、G是連通圖表明任意兩個(gè)人可通過(guò)其朋友及朋友的朋友結(jié)識(shí)，建立友好關(guān)系。(3)、由已知任意兩個(gè)人合起來(lái)認(rèn)識(shí)其余的n-2個(gè)人，即對(duì)G中任意兩個(gè)結(jié)點(diǎn)u,v,deg(u)+deg(v)n-2,且其余n-2個(gè)結(jié)點(diǎn)與u或v鄰接。若u

17、與v鄰接，貝Udeg(u)+deg(v)n-2+1=n-1。若u與v不鄰接，若deg(u)+deg(v)=n-2,則對(duì)于任意的wCV-u,v,w與u鄰接(w與v鄰接)，但不能同時(shí)與u,v鄰接，設(shè)w與u鄰接，則w必不與v鄰接，則結(jié)點(diǎn)w和u都不與v鄰接，也就是w和u都不認(rèn)識(shí)v,從而結(jié)點(diǎn)w和結(jié)點(diǎn)u的度數(shù)之和<n-2(即w和u兩個(gè)人合起來(lái)不能夠認(rèn)識(shí)所留下的n-2個(gè)人)，與假設(shè)矛盾。因此，deg(u)+deg(v)n-1,即圖G中存在哈密頓通路，按照此通路的結(jié)點(diǎn)排列可得n個(gè)人排列成一排，使中間的每個(gè)人兩邊都是朋友，而兩端的兩個(gè)人，一邊站著的也是朋友。(4)、由(3)可知，當(dāng)n3時(shí)，對(duì)G中任意兩個(gè)結(jié)

18、點(diǎn)u,v有，deg(u)+deg(v)n-1。下面證明，當(dāng)n4時(shí)，deg(u)+deg(v)n。若u和v鄰接，顯然成立。若u和v不鄰接,貝Udeg(u)+deg(v)>n-1,否貝U,若deg(u)+deg(v)=n-1,則V-u,v至少有2個(gè)結(jié)點(diǎn)(因n4),設(shè)為小t,且w與u,v均鄰接，t只與u,v之一鄰接。設(shè)t與u鄰接，則t和u與結(jié)點(diǎn)v都不鄰接，與假設(shè)矛盾，故對(duì)任意結(jié)點(diǎn)u,v,deg(u)+deg(v)>n-1,即deg(u)+deg(v)n。故圖G中存在哈密頓回路，按照此回路的結(jié)點(diǎn)排列，即為所求的圈，滿(mǎn)足n個(gè)人能站成一圈，使每個(gè)人的兩旁站著自己的朋友。題16:設(shè)G是有11個(gè)或

19、更多結(jié)點(diǎn)的圖，證明G或G(補(bǔ)圖)是非平面圖。證明：反證法：設(shè)G和G都是平面圖，設(shè)G和G的結(jié)點(diǎn)數(shù)分別為n和n,邊數(shù)分別為m和m,貝Un=n,m+m=n(n-1)2由歐拉定理可知，m3n-6,m3n-61n(n-1)=m+m3n-6+3n-6=6n-122即n2-13n+240從而得出n<11,與n11相矛盾，故G和G不可能同時(shí)為平面圖，即n11時(shí)，G或G(補(bǔ)圖)是非平面圖。題17:一棵樹(shù)有上個(gè)結(jié)點(diǎn)度數(shù)為2,n3個(gè)結(jié)點(diǎn)度數(shù)為3,，nk個(gè)結(jié)點(diǎn)度數(shù)為k,問(wèn)它有幾個(gè)度數(shù)為1的結(jié)點(diǎn)。解：設(shè)樹(shù)T中有n1個(gè)度數(shù)為1的結(jié)點(diǎn)，則樹(shù)中邊數(shù)m為：m=n1+n2+n3+nk-1又由于任意圖中結(jié)點(diǎn)度數(shù)之和等于邊數(shù)的

20、2倍，故：n1+2n2+3n3+knk=2(n1+n2+n3+nk-1)故：n1=(3-2)n3+(4-2)n4+(k-2)nk+2題18:證明在完全二叉樹(shù)中，邊的總數(shù)m等于2(nt-1),nt是樹(shù)葉總數(shù)。證明：對(duì)分枝結(jié)點(diǎn)數(shù)i用數(shù)學(xué)歸納法：當(dāng)i=1時(shí)，邊數(shù)m=2,樹(shù)葉數(shù)nt=2,故m=2(nt-1)成立。假設(shè)i=k時(shí)(k1)成立，下面證明i=k+1時(shí)結(jié)論成立。由于樹(shù)T是完全二叉樹(shù)，因此T中必存在一分枝結(jié)點(diǎn)v,v的兩個(gè)兒子v1,v2均是樹(shù)葉。在T中刪去v1,v2得T',則T'是分枝結(jié)點(diǎn)數(shù)為k的完全二叉樹(shù)，此時(shí)v為樹(shù)葉，分枝結(jié)點(diǎn)數(shù)i'=i-1=k+1-1=k樹(shù)葉數(shù)nt

21、9;=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個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖，使得結(jié)點(diǎn)vi的度數(shù)為di,則稱(chēng)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)、

22、(3, 3, 3, 3)(6)、 (2, 3, 3, 3)(9)、 (2, 2, 4)(10)、(1,2,2,3,4,5)題20:給無(wú)向完全圖Kn(n>7)的各邊隨意涂上紅色或綠色，若已知從某個(gè)結(jié)點(diǎn)v0引出的n-1條邊中至少有六條邊涂紅色，則存在紅色的K4或綠色的K3。證明：設(shè)x1,x2,x3,x4,x5,x6是與v0相鄰的六條邊涂紅色。根據(jù)Ramsey(3,3)=6的證明可知，在x1,x2,x3,x4,x5,x6中，或有3個(gè)相互鄰接的頂點(diǎn)(涂紅色)，這3個(gè)頂點(diǎn)與v0一起構(gòu)成紅色的K4;或者有3個(gè)互不相鄰的頂點(diǎn)(綠色)，這3個(gè)頂點(diǎn)構(gòu)成綠色的K3。題21:證明：在任何兩個(gè)或兩個(gè)以上人的組內(nèi)

23、，存在兩個(gè)人在組內(nèi)有相同個(gè)數(shù)的朋友。證明：此題可轉(zhuǎn)化為圖論的問(wèn)題來(lái)處理：把每個(gè)人對(duì)應(yīng)成相應(yīng)的結(jié)點(diǎn)，兩個(gè)人具有朋友關(guān)系當(dāng)且僅當(dāng)相應(yīng)的結(jié)點(diǎn)相鄰，顯然該圖是簡(jiǎn)單圖，所以原命題等價(jià)于證明在該無(wú)向簡(jiǎn)單圖中一定存在兩個(gè)結(jié)點(diǎn)的度數(shù)相等。反設(shè)，該無(wú)向簡(jiǎn)單圖G中任何一對(duì)結(jié)點(diǎn)的度數(shù)都不相等，并設(shè)結(jié)點(diǎn)數(shù)為no又因?yàn)閳DG是簡(jiǎn)單圖，所以結(jié)點(diǎn)的度數(shù)只能為：0,1,2,，n-1。那么在圖G中，存在度數(shù)為n-1的結(jié)點(diǎn)，與所有結(jié)點(diǎn)相鄰，同時(shí)又存在度數(shù)為0的結(jié)點(diǎn),與所有結(jié)點(diǎn)都不相鄰，因此產(chǎn)生矛盾。所以該無(wú)向簡(jiǎn)單圖中一定存在兩個(gè)結(jié)點(diǎn)的度數(shù)相等。所以在任何兩個(gè)或兩個(gè)以上人的組內(nèi)，存在兩個(gè)人在組內(nèi)有相同個(gè)數(shù)的朋友。題22、設(shè)G為n個(gè)結(jié)

24、點(diǎn)的簡(jiǎn)單無(wú)向圖。(1)、若G的邊數(shù)m=(1/2)(n-1)(n-2)+2,證明G是哈密爾頓圖。(2)、若G的邊數(shù)m=(1/2)(n-1)(n-2)+1，那么圖G是否一定為哈密爾頓圖？請(qǐng)闡述你的理由。分析:因?yàn)橛卸ɡ恚涸O(shè)G=(V,E)是n階(n>3)無(wú)向簡(jiǎn)單圖，若對(duì)于任意的不相鄰的結(jié)點(diǎn)Vi,vjCV,有dev(vi)+dev(vj)>n,則G是哈密爾頓圖。那么只要證明對(duì)任意的不相鄰結(jié)點(diǎn)Vi,VjCV,有dev(vi)+dev(vj)>n即可。解：(1)反證法：假設(shè)存在不相鄰的結(jié)點(diǎn)Vi,vjV,有dev(vi)+dev(vj)wn-1。另V尸vi,vj,Gi=G-Vi,則Gi是(

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