湘潭大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)劉任任版離散數(shù)學(xué)課后習(xí)題答案---第二學(xué)期--圖論與組合數(shù)學(xué)

1、習(xí) 題 六1設(shè)是一個(gè)無(wú)回路的圖, 求證：若中任意兩個(gè)頂點(diǎn)間有惟一的通路, 則是樹(shù). 證明：由假設(shè)知，是一個(gè)無(wú)回路的連通圖，故是樹(shù)。2證明：非平凡樹(shù)的最長(zhǎng)通路的起點(diǎn)和終點(diǎn)均為懸掛點(diǎn). 分析：利用最長(zhǎng)通路的性質(zhì)可證。 證明：設(shè)是樹(shù)中的極長(zhǎng)通路。若的起點(diǎn)滿足，則不是中極長(zhǎng)的通路。對(duì)終點(diǎn)也可同理討論。故結(jié)論成立。3證明：恰有兩個(gè)懸掛點(diǎn)的樹(shù)是一條通路. 分析：因?yàn)闃?shù)是連通沒(méi)有回路的，所以樹(shù)中至少存在一條通路P。因此只需證明恰有兩個(gè)懸掛點(diǎn)的樹(shù)中的所有的點(diǎn)都在這條通路P中即可。證明：設(shè)是樹(shù)中的兩個(gè)懸掛點(diǎn)，即。因是樹(shù)，所以存在-通路：。顯然，。若，則由恰有兩個(gè)懸掛點(diǎn)的假設(shè)，可知中有回路；若中還有頂點(diǎn)不在中，則

2、存在-通路，顯然與不鄰接，且。于是，可推得中有回路，矛盾。故結(jié)論成立。4設(shè)是樹(shù), , 求證：中至少有個(gè)懸掛點(diǎn). 分析：由于，所以G中至少存在一個(gè)頂點(diǎn)v的度k，于是至少有k個(gè)頂點(diǎn)與鄰接，又G是樹(shù)，所以G中沒(méi)有回路，因此與v鄰接的點(diǎn)往外延伸出去的分支中，每個(gè)分支的最后一個(gè)頂點(diǎn)必定是一個(gè)懸掛點(diǎn)，因此G中至少有k個(gè)懸掛點(diǎn)。證明：設(shè)，且。于是，存在，使。若不是懸掛點(diǎn)，則有使。如此下去，有，滿足且, 。故中至少有個(gè)懸掛點(diǎn)。5設(shè)是一個(gè)圖, 求證：若, 則中必含回路. 分析：利用樹(shù)是沒(méi)有回路且連通的圖，且樹(shù)中的頂點(diǎn)數(shù)和邊數(shù)的關(guān)系可證。證明：設(shè)有個(gè)分支：。顯然，。若無(wú)回路，則每個(gè)均是樹(shù)，。于是。從而 ，即。此為

3、矛盾，故必含回路。6設(shè)是有個(gè)連通分支的圖, 求證：是森林當(dāng)且僅當(dāng).證明：見(jiàn)題5的證明。7畫(huà)出的所有16棵生成樹(shù). 解，K4的所有16棵生成樹(shù)如下圖所示。132413241324324 1324132413241324132413241324132413241324132413248設(shè)是連通圖, 求證：. 分析：樹(shù)應(yīng)該是具有p個(gè)頂點(diǎn)中邊數(shù)最少的連通圖，而樹(shù)中的邊數(shù)q=p-1可證。證明：設(shè)是連通圖。若無(wú)回路，則是樹(shù)，于是。若有回路，則刪去中條邊使之保持連通且無(wú)回路。于是，即。9遞推計(jì)算的生成樹(shù)數(shù)目. =eK2,3e+e=e+e+e=e+e+e+e+=+e+=+=1210通過(guò)考慮樹(shù)中的最長(zhǎng)通路, 直

4、接驗(yàn)證有標(biāo)記的5個(gè)頂點(diǎn)的樹(shù)的總數(shù)為125. 分析：設(shè)樹(shù)中5個(gè)頂點(diǎn)的標(biāo)記分別為1，2，3，4，5。而5個(gè)頂點(diǎn)的樹(shù)的最長(zhǎng)通路只能是4、3、2，如下（1）（2）（3）所示。(1) 最長(zhǎng)通路長(zhǎng)度為4；(2) 最長(zhǎng)通路長(zhǎng)度為3； （3） 最長(zhǎng)通路長(zhǎng)度為2。 對(duì)于（1），把每個(gè)頂點(diǎn)看作是一個(gè)空，不同的頂點(diǎn)序列對(duì)應(yīng)不同的樹(shù)，但由于對(duì)稱性12345和54321所形成的樹(shù)應(yīng)該是同一棵樹(shù)，因此這種情況下所有有標(biāo)記的樹(shù)的數(shù)目為：5！/2=60個(gè)；對(duì)于（2），把上面四個(gè)頂點(diǎn)分別看作一個(gè)空，在構(gòu)造樹(shù)的時(shí)候可以先構(gòu)造這四個(gè)頂點(diǎn)，剩下的一個(gè)頂點(diǎn)只能放在下面，選擇上面四個(gè)頂點(diǎn)的數(shù)目應(yīng)為可以從所有有標(biāo)記的樹(shù)的數(shù)目為*4！，但同

5、樣由對(duì)稱性，如1234這樣的排列和頂點(diǎn)5構(gòu)成的樹(shù)與1235這樣的排列和4構(gòu)成的數(shù)是一樣的。因此這種情況下所有有標(biāo)記的樹(shù)的數(shù)目為：*4！/2=60個(gè)；對(duì)于（3），只要確定了中間度為4的頂點(diǎn)，這棵樹(shù)就構(gòu)造完了，所有這種情況下有標(biāo)記的樹(shù)的數(shù)目為：個(gè)； 解：有標(biāo)記的5個(gè)頂點(diǎn)的樹(shù)的總數(shù)為：60+60+5=125個(gè)。11用表示個(gè)頂點(diǎn)的有標(biāo)記樹(shù)的個(gè)數(shù), 求證：由此得恒等式分析：每個(gè)n階樹(shù)可由下面的方法構(gòu)造出來(lái)：先從這n個(gè)頂點(diǎn)中任取k個(gè)頂點(diǎn)構(gòu)造出一個(gè)k階樹(shù)，對(duì)剩下的n-k個(gè)頂點(diǎn)構(gòu)造出一個(gè)n-k階樹(shù)，再將這兩個(gè)樹(shù)合并成一個(gè)樹(shù)，顯然這樣得到的樹(shù)是一個(gè)n階的樹(shù)。又由定理6.2.4有i個(gè)頂點(diǎn)的無(wú)標(biāo)記的生成樹(shù)共有ii-

6、2個(gè)，可得下面的證明。證明：任取k個(gè)頂點(diǎn)的一棵k階樹(shù)與 (nk)個(gè)頂點(diǎn)構(gòu)成的nk階樹(shù)之間連接兩點(diǎn)就是一棵n階樹(shù)，這里有k (nk) 種連接。并注意到一來(lái)一往每條邊用了兩次，因此， k (nk) T(k) T (nk)Cnk =2T(n)。上式兩邊對(duì)k從1到n1求和，得。再將T(n) = nn2, T(k) = kk2, T (nk)= (nk)nk2, 代入上式便可得恒等式：12. 如何用Kruskal算法求賦權(quán)連通圖的權(quán)最大的生成樹(shù)（稱為最大樹(shù)）？證明：將Kruskal算法中的“小”改成“大”即可得到“最大樹(shù)”。13設(shè)是一個(gè)賦權(quán)連通圖, . 求證：按下列步驟（Prim算法）可以得出的一個(gè)最優(yōu)

7、樹(shù). （）置；（）選取滿足條件且最小的；（）；（）若則轉(zhuǎn)（）, 否則停止, 中的邊就是最優(yōu)樹(shù)的邊. 解： (1) 設(shè)是按Prim算法得出的圖。由Prim算法的初值及終止條件，可知連通，且為的生成子圖。又由（）知無(wú)回路。故是生成樹(shù)。 （2）設(shè)是的生成樹(shù)，仿定理6.3.1的證明，可證結(jié)論成立。14按題13的Prim算法, 求出圖6. 9的最優(yōu)樹(shù). 解：最優(yōu)樹(shù)如下。（權(quán)為20）6621321234567習(xí)題七1對(duì)圖7.7中的兩個(gè)圖，各作出兩個(gè)頂點(diǎn)割。（a）（b）圖7.7解： 對(duì)圖7.7增加加節(jié)點(diǎn)標(biāo)記如下圖所示， 則(a)的兩個(gè)頂點(diǎn)割為： V11=a,b ； V12=c,d (b)的兩個(gè)頂點(diǎn)割為： V

8、21=u,v ； V12=y 2求圖7.7中兩個(gè)圖的和. 解：如上兩個(gè)圖，有 k(G1)=(G1)=2, k(G2)=1, (G2)=2 3試作出一個(gè)連通圖, 使之滿足：解：做連通圖G如下，于是有 ： 4求證, 若是邊連通的, 則.證明：設(shè)G是k邊連通的，由定義有(G)k. 又由定理7.1.2知(G) ，因此有 k(G) 即 k ，從而 5求證, 若是階簡(jiǎn)單圖, 且, 則.分析：由G是簡(jiǎn)單圖，且，可知G中的(G)只能等于 p-1或p-2；如(G)= p-1,則G是一個(gè)完全圖，根據(jù)書(shū)中規(guī)定，有k(G)=p-1=(G)；如(G)= p-2,則從G中任取V（G）的子集V1，其中|V1|=3，則V(G

9、)-V1的點(diǎn)導(dǎo)出子圖是連通的，否則在V1中存在一個(gè)頂點(diǎn)v，與其他兩個(gè)頂點(diǎn)都不連通。則在G中，頂點(diǎn)v最多與G中其他p-3個(gè)頂點(diǎn)鄰接，所以d(v)p-3，與(G)= p-2矛盾。這說(shuō)明了在G中，去掉任意p-3個(gè)頂點(diǎn)后G還是連通的，按照點(diǎn)連通度的定義有k(G)>k-3，又根據(jù)定義7.1.1，有k(G)=k-2。證明：因?yàn)镚是簡(jiǎn)單圖 ,所以d(v)p-1,vV(G),已知(G)p-2（）若(G)= p-1,則G=Kp（完全圖），故k(G)=p-1=(G)。（）若(G)= p-2, 則 GKp,設(shè)u,v不鄰接，但對(duì)任意的wV(G),有 uw,vw E(G).于是，對(duì)任意的V1V(G), | V1|

10、=p-3 ,G-V1必連通. 因此必有k(G) p-2=(G),但k(G) (G)。 故k(G) =(G)。 6找出一個(gè)階簡(jiǎn)單圖, 使, 但. 解：7設(shè)為正則簡(jiǎn)單圖, 求證.分析：G是一個(gè)正則簡(jiǎn)單圖，所以(G)=3，根據(jù)定理7.1.1有，所以只能等于0，1，2，3這四種情況。下面的證明中分別討論了這四種情況下的關(guān)系。證明：(1)若=0，則G不連通,所以(G)=K(G).(2) 設(shè) K(G)=1,且u 是G中的一個(gè)割點(diǎn)，G-u不連通,由于d(u)=3,從而至少存在一個(gè)分支僅一邊與u相連,顯然這邊是G的割邊,故(G)，所以(G)=K(G) () 設(shè)K(G)=2,且v1,v2為G的一個(gè)頂點(diǎn)割。G1=

11、G-v1連通,則v2是G1的割點(diǎn)且v2在G1中的度小于等于，類似于(2)知在G1中存在一割邊e2(關(guān)聯(lián)v2)使得G1-e2不連通另一方面由于(G)>=K(G)=2故G-e2連通由于G1-e2= (G-e2)-v1，故v1是G-e2的割點(diǎn)，且v1在G-e2中的度小于等于，于是類似于(2)知，在G-e2中存在一割邊e1，即(G-e2)-e1=G-e1,e2不連通，故(G)=2.所以(G)=K(G). () 設(shè)k(G) =3,于是， 有3 =k（G） (G)=3 ,知8證明：一個(gè)圖是邊連通的當(dāng)且僅當(dāng)?shù)娜我鈨蓚€(gè)頂點(diǎn)由至少兩條邊不重的通路所連通.分析：這個(gè)題的證明關(guān)鍵是理解邊連通的定義。證明：（必

12、要性）因?yàn)镚是邊連通的，所以G沒(méi)有割邊。設(shè)u，v是G中任意兩個(gè)頂點(diǎn)，由G的連通性知u，v之間存在一條路徑P1，若還存在從u到v的與P1邊不重的路徑P2，設(shè)C=P1P2，則C中含u,v的回路，若從u到v的任意另外路徑和P1都有一條（或幾條）公共邊，也就是存在邊e在從u到v的任何路徑中，則從G中刪除e，G就不連通了，于是e成了G中一割邊，矛盾。（充分性）假設(shè)G不是一個(gè)2-邊連通的，則G中有割邊，設(shè)e=(u,v)為G中一割邊，由已知條件可知，u與v處于同一簡(jiǎn)單回路C中，于是e處在C中，因而從G中刪除e后G仍然連通，這與G中無(wú)割邊矛盾。vV1V2uG9舉例說(shuō)明：若在連通圖中, 是一條通路, 則不一定包

13、含一條與內(nèi)部不相交的通路。 解 如右圖G，易知G是2連通的， 若取P為uv1v2v， 則G中不存在Q了。10證明：若中無(wú)長(zhǎng)度為偶數(shù)的回路, 則的每個(gè)塊或者是, 或者是長(zhǎng)度為奇數(shù)的回路.分析：塊是G的一個(gè)連通的極大不可分子圖，按照不可分圖的定義，有G的每個(gè)塊應(yīng)該是沒(méi)有割點(diǎn)的。因此，如果能證明G的某個(gè)塊如果既不是，也不是長(zhǎng)度為奇數(shù)的回路，再由已知條件G中無(wú)長(zhǎng)度為偶數(shù)的回路，則可得出G的這個(gè)塊肯定存在割點(diǎn)，則可導(dǎo)出矛盾。本題使用反證法。證明： 設(shè)K是G的一個(gè)塊，若k既不是 K2也不是奇回路，則k至少有三個(gè)頂點(diǎn)，且存在割邊e=uv,于是u,v中必有一個(gè)是割點(diǎn)，此與k是塊相矛盾。 11證明：不是塊的連通

14、圖至少有兩個(gè)塊, 其中每個(gè)塊恰含一個(gè)割點(diǎn).分析：一個(gè)圖不是塊，按照塊的定義，這個(gè)圖肯定含有割點(diǎn)v，對(duì)圖分塊的時(shí)候也應(yīng)該以割點(diǎn)為標(biāo)準(zhǔn)進(jìn)行，而且分得的塊中必定含這個(gè)割點(diǎn)，否則所得到的子圖一定不是極大不可分子圖，從而不會(huì)是一個(gè)塊。證明：由塊的定義知，若圖G不是塊且連通，則G有割點(diǎn)，依次在有割點(diǎn)的地方將G分解成塊，一個(gè)割點(diǎn)可分成兩塊，每個(gè)塊中含G中的一個(gè)割點(diǎn)。如下圖G。易知 u,v是割點(diǎn)，G可分成四個(gè)塊K1 K4 。其中每個(gè)塊恰含一個(gè)割點(diǎn)。 12證明：圖中塊的數(shù)目等于 其中, 表示包含的塊的數(shù)目.分析：一個(gè)圖G的非割點(diǎn)只能分布在G的一個(gè)塊中，即=1（當(dāng)v是G的非割點(diǎn)時(shí)），且每個(gè)塊至少包含一個(gè)割點(diǎn)。因此

15、下面就從G的割點(diǎn)入手進(jìn)行證明。證明中使用了歸納法。證明：先考慮G是連通的情況（），對(duì)G中的割點(diǎn)數(shù)n用歸納法。由于對(duì)G的非割點(diǎn)v，b(v)=1，即b(v)-1 =0，故對(duì)n=0時(shí)，G的塊數(shù)為1結(jié)論成立。假設(shè)G中的割點(diǎn)數(shù)nk（k0）時(shí)，結(jié)論成立。對(duì)n=k+1的情況，任取G的一個(gè)割點(diǎn)a，可將G分解為連通子圖Gi，使得a在Gi中不是割點(diǎn)，a又是Gi的公共點(diǎn)。這樣，每一個(gè)Gi，有且僅有一個(gè)塊含有a，若這些Gi共有r個(gè)，則b(a)=r，又顯然Gi的塊也是G的塊，且Gi的割點(diǎn)數(shù)k。故由歸納法假設(shè)Gi的塊的塊數(shù)為1，這里是Gi中含v的塊的塊數(shù)，注意到Gi中異于a的v，b(v)= ，而a在每一個(gè)Gi中均為非割點(diǎn)

16、，故。于是Gi的塊數(shù)為1將所有Gi的塊全部加起來(lái)，則得到G的塊數(shù)為：r=r=1+(r-1) =1由歸納法可知，當(dāng)G連通時(shí)，結(jié)論成立。當(dāng)G不連通時(shí)，對(duì)每個(gè)連通分支上述結(jié)論顯然成立。因此有圖中塊的數(shù)目等于13 給出一個(gè)求圖的塊的好算法。分析：設(shè)G是一個(gè)具有p個(gè)頂點(diǎn)，q條邊，w個(gè)連通分支的圖。求圖G的塊可先求圖G的任一生成森林F，且對(duì)每一邊eF，求F+e中的唯一回路，設(shè)這些回路C1，C2，Cq-p+w都已求得，（這些都有好算法）。在此基礎(chǔ)上，我們注意到，兩個(gè)回路（或一個(gè)回路與一個(gè)塊）若有多于1個(gè)公共點(diǎn)，則它們屬于同一塊。此外，由割邊的定義知，G的任一割邊不含于任何回路中，且它們都是G的塊?；谶@些道

17、理，可得如下求圖G的塊的好算法。解：求圖的塊的算法：（1）令s=1，t=1，n=q-p+w（2）若n>0，輸入C1，C2，Cn；否則，轉(zhuǎn)第4步。（3）若且對(duì)i=s+t，n-1，令，轉(zhuǎn)第4步；否則，t=t+1，轉(zhuǎn)第5步。（4）若s<n，令t=1，轉(zhuǎn)第3步；否則，算法停止（這時(shí)C1，C2，Cn與E（G）- C1，C2，Cn中的每一邊都是G的塊）（5）若s+tn轉(zhuǎn)第3步；否則，s=s+1，轉(zhuǎn)第4步。本算法除了求回路有已知的好算法外，計(jì)算量主要在第3步，比較的頂點(diǎn)尋找它們的公共點(diǎn)的運(yùn)算中，這些運(yùn)算不超出p2*(q-p+w)次，故是好算法。14證明：是連通的。分析：只要證明不存在少于個(gè)頂點(diǎn)的

18、頂點(diǎn)割集。設(shè)是一個(gè)的任一頂點(diǎn)子集，可分和兩種情形證明。證明：(1) 當(dāng)時(shí)，根據(jù)定理7.3.1的證明，不是的頂點(diǎn)割集，當(dāng)然更不是在上加些邊的的頂點(diǎn)割集。(2) 當(dāng)時(shí)，設(shè)是的頂點(diǎn)割集，屬于的不同分支?？疾祉旤c(diǎn)集合和 這里加法取模若或中有一個(gè)含的頂點(diǎn)少于個(gè)，則在中存在從到的路。與為頂點(diǎn)割集矛盾。若和中都有的個(gè)頂點(diǎn)，則：j 若或中，有一個(gè)(不妨說(shuō))中的個(gè)頂點(diǎn)不是相繼連成段，則中存在從到的路。與為頂點(diǎn)割集矛盾。k 若與中，的個(gè)頂點(diǎn)都是相繼連成一段的。若與中至少有一個(gè)沒(méi)有被分成兩段，則立即與為頂點(diǎn)割集矛盾；若被分成兩段：含的記，含的記，且也被分為兩段：含的記，含的記。這樣，被分為兩段：含的 和含的。這兩段

19、都是連通的，且含段的中間點(diǎn)(或最靠近中間的一點(diǎn))與含段的類似點(diǎn)滿足：故與有邊相連，在中有路()，與為頂點(diǎn)割集矛盾。綜上所述，是連通的。15證明：.分析：根據(jù)定理7.3.1，圖是m-連通圖，因此有 又根據(jù)的構(gòu)造，可知 ，再由定理7.1.1可證。 證明：由定理7.3.1知： 已知：k 16試畫(huà)出、和分析：根據(jù)書(shū)上第54頁(yè)構(gòu)造的方法可構(gòu)造出、和。(i) : r = 2 ,p=8,對(duì)任意 i,j V(), i- jr 或者則如下圖：(ii) 圖：r =2,p=8,則在中添加連接頂點(diǎn)i 與 i+p/2(mod p)的邊，其中1ip/2,15; 2 6; 3 7; 4 0. 則圖如下：(iii) 圖: r

20、=2,在圖上添加連接頂點(diǎn)0與（p-1）/2和(p+1）/2的邊，以及頂點(diǎn) i 與 i +（p+1）/2(mod p) 的邊，其中1 i< （p-1）/2.04; 0 5; 1 6; 2 7; 38.則圖如下： 習(xí)題81、圖中8.10中哪些是E圖？哪些是半E圖？分析：根據(jù)歐拉定理及其推論，E圖是不含任何奇點(diǎn)的圖，半E圖是最多含兩個(gè)奇點(diǎn)的圖。解： (a) 半E 圖 。（b）E 圖。 （c）非半E 圖 和 E 圖 2、試作出一個(gè)E圖G(p,q),使得p與q均為奇數(shù)。能否作出一個(gè)E圖G(p,q)，使得p為偶數(shù)，而q為奇數(shù)？如果是p為奇數(shù)，q為偶數(shù)呢？解：以下 E 圖中， p與 q 的奇偶如下表

21、pqG1奇數(shù)奇數(shù)G2偶數(shù)奇數(shù)G3奇數(shù)偶數(shù)3、求證：若G 是 E 圖，則 G 的每個(gè)塊也是 E 圖。 分析：一個(gè)圖如果含有E回路，則該圖是E圖；另一方面一個(gè)塊是G中不含割點(diǎn)的極大連通不可分子圖，且非割點(diǎn)不可能屬于兩個(gè)或兩個(gè)以上的塊。這樣沿G中的一條E回路遍歷G的所有邊時(shí)，從一個(gè)塊到達(dá)另一個(gè)塊時(shí)，只能經(jīng)過(guò)割點(diǎn)才能實(shí)現(xiàn)。證明：設(shè)B是G的塊，任取G中一條E回路C，由B中的某一點(diǎn)v出發(fā)，沿C前進(jìn)，C只有經(jīng)過(guò)G的割點(diǎn)才能離開(kāi)B，也就是說(shuō)只有經(jīng)過(guò)同一個(gè)割點(diǎn)才能回到B中，注意到這個(gè)事實(shí)后，我們將C中屬于B外的一個(gè)個(gè)閉筆回路除去，最后回到v時(shí)，我們得到的就是B上的一個(gè)E回路，所以B也是E圖。4、求證：若G無(wú)奇點(diǎn)

22、，則G中存在邊互不重的回路 ，使得分析：G中無(wú)奇點(diǎn)，則除了孤立點(diǎn)后其他所有點(diǎn)的度至少為2，而孤立點(diǎn)不與任何邊關(guān)聯(lián)，因此在分析由邊構(gòu)成的回路時(shí)可以不加考慮；而如果一個(gè)圖所有的頂點(diǎn)的度至少為2，則由第五章習(xí)題18知該圖必含回路。證明：將G中孤立點(diǎn)去掉以后得到圖G1，顯然G1也是一個(gè)無(wú)奇點(diǎn)的E圖，且。由第五章習(xí)題18知，G1必含有回路C1；在圖G1-C1中去掉孤立點(diǎn)，得圖G2，顯然G2仍然是一個(gè)無(wú)奇點(diǎn)的圖，且，于是G2中也必含回路C2，如此直到Gm中有回路Cm，且Gm-Cm全為孤立點(diǎn)為止，于是有：5、求證：若G有2k>0個(gè)奇點(diǎn)，則G中存在k個(gè)邊互不重的鏈 ,使得：分析：一個(gè)圖的E回路去掉一條邊

23、以后，將得到一條E鏈。證明：設(shè) 為 G 中的奇數(shù)度頂點(diǎn)，k1在Vi和Vi+k 之間用新邊ei連接，=1，2.k,所得之圖記為G*，易知G*的每個(gè)頂點(diǎn)均為偶數(shù)，從而G*存在 E 閉鏈C* ?，F(xiàn)從C*中刪去ei （=1，2.k），則C*被分解成 k 條不相交的鏈Q(jìng)i(=1，2.k),顯然有: 6、 證明：如果 （1）G不是2連通圖，或者（2）G是二分圖<X,Y>,且XY,則 G 不是 H 圖。分析：G不是2連通圖，說(shuō)明，于是或，如果，則說(shuō)明G不連通，如G不連通，顯然G不是H圖，如則G中存在孤立點(diǎn)，因此有(G-v)2，由定理8.2.1G不是H圖。若G是二分圖<X，Y>，則X或

24、Y中的任意兩個(gè)頂點(diǎn)不鄰接，因此G-X剩下的是Y中的點(diǎn)，這些點(diǎn)都是孤立點(diǎn)；同樣G-Y剩下的是X中的點(diǎn)，這些點(diǎn)也是孤立點(diǎn)；即有，如果XY，則有成立。無(wú)論哪個(gè)結(jié)論成立，根據(jù)定理8.2.1都有G不是H圖。證明：若（1）成立則G不連通或者是G有割點(diǎn)u，若G不連通,則G不是H圖，若G有割點(diǎn)u，取S=u,于是(G-u)> S因此 G不是H圖.因此 G不是H圖.7、證明：若 G 是半 H 圖,則對(duì)于V(G)的每一個(gè)真子集S，有: 分析：圖G的權(quán)與它的生成子圖 的連通分支數(shù)滿足： ，因?yàn)橐粋€(gè)圖的生成子圖是在該圖的基礎(chǔ)上去掉若干邊得到的，顯然去掉邊以后只能使該圖的連通分支增加。對(duì)于圖G的一條H通路C，滿足任

25、取, 證明:設(shè)C是G的一條H通路，任取, 易知而 C-S是 G-S 的生成子圖. 8、試述 H 圖與 E 圖之間的關(guān)系。 分析：H圖是指存在一條從某個(gè)點(diǎn)出發(fā)經(jīng)過(guò)其他頂點(diǎn)有且僅有一次的回路；而E圖是指從某點(diǎn)出發(fā)通過(guò)圖中所有的邊一次且僅有一次的回路。從定義可看出，這兩者之間沒(méi)有充分或必要的關(guān)系。解 ： 考慮如下四個(gè)圖:易知G1是E圖，但非H圖; G2是H圖，但非E圖; G3既非E圖，又非H圖；G4既是E圖，也是H圖。 9、作一個(gè)圖，它的閉包不是完全圖分析：一個(gè)p階圖的閉包是指對(duì)G中滿足d(u)+d(v)p的頂點(diǎn)u,v，若uvE(G)，則將邊uv加到G中，得到G+uv，如此反復(fù)加邊，直到滿足d(u)

26、+d(v)p的所有頂點(diǎn)均鄰接。由閉包的定義，如果一個(gè)圖本身不存在任何一對(duì)頂點(diǎn)u,v，滿足d(u)+d(v)p，則它的閉包就是其自身。顯然可找到滿足這種條件的非完全圖。10、若 G 的任何兩個(gè)頂點(diǎn)均由一條 H 通路連接著，則稱G 是H連通的。 （2）對(duì)于p4，構(gòu)造一個(gè)具有 的H連通圖G。分析：根據(jù)定理5.3.1有，因此而，所以qp*(G)/2，因此如果能判斷(G)3，則有 下面的證明關(guān)鍵是判斷(G)3。證明：（1）任取wV(G),由于G是連通的，所以d(w)1。若d(w)=1,則與w鄰接的頂點(diǎn)u與w之間不可能有一條H 通路連接它們，否則因?yàn)閜4，所以G中除了u與w外還有其他頂點(diǎn)，因此，如果u與w

27、之間有一條H通路的話，這條H通路與u與w的連線就構(gòu)成了一個(gè)回路，這樣與d(w)=1矛盾，所以d(w)1；同樣的道理，若d(w)=2，則與w鄰接的頂點(diǎn)u與v之間不存在H通路。因此(G) 3。從而 2q=d(u)3p, 即：2q3p,也即q 3p/2() 若p為奇數(shù)，于是() 若p為偶數(shù)，則3p為偶數(shù)，于是綜合以上各種情況 ，有： （2）()當(dāng)p=偶數(shù)時(shí)，q=3p/2，滿足條件的圖如下圖(a); () 當(dāng)p=奇數(shù)時(shí)， 滿足條件的圖如下圖(b); 圖(a) 圖(b) 11、證明：若G是一個(gè)具有 p2的連通簡(jiǎn)單圖，則 G 有一條長(zhǎng)度至少是2的通路。 分析：使用反證法，假設(shè)G 中沒(méi)有一條長(zhǎng)度大于或等于2

28、的通路。先找到圖G的一條最長(zhǎng)通路P，設(shè)其長(zhǎng)度為m，由假設(shè)m<2。再在P的基礎(chǔ)上構(gòu)造一條長(zhǎng)度為m+1的回路C，顯然C中包含的頂點(diǎn)數(shù)小<2，由于p2，所以圖G至少還有一個(gè)頂點(diǎn)v不在該圈中，又由于G是連通的，所以v到C上有一條通路P。于是P+C的長(zhǎng)度等于通路P的長(zhǎng)度的通路構(gòu)成了一條比P更長(zhǎng)的通路，這與P是G的一條最長(zhǎng)通路矛盾。從而本題可得到證明。證明：(用反證法)設(shè) 是G的最長(zhǎng)通路,其長(zhǎng)度為m，假設(shè)m<2。由P是G的最長(zhǎng)通路，則V1,Vm+1只能與 P中的頂點(diǎn)相鄰，注意到 G 是簡(jiǎn)單圖分析：由定理8.2.4，如果p（3）階簡(jiǎn)單圖G的各頂點(diǎn)度數(shù)序列下面的證明就是利用這個(gè)定理來(lái)判斷當(dāng)m

29、<p/2時(shí)，dm滿足dm>m。從而G是H圖。13、在圖8-8中，如果分別去掉v3，v4和v5，則相應(yīng)得到的旅行推銷員問(wèn)題的解分別取什么下界估計(jì)值？ 分析：利用Kruskal算法可給出一個(gè)關(guān)于旅行推銷員問(wèn)題的的下界估計(jì)式： 任選賦權(quán)完全圖Kn的一個(gè)頂點(diǎn)v，用Kruskal算法求出Kn-v的最優(yōu)樹(shù)T，設(shè)C是最優(yōu)的H回路，于是有C-v也是Kn-v的一個(gè)生成樹(shù)，因此有：w(T)w(C-v)設(shè)e1和e2是Kn中與v關(guān)聯(lián)的邊中權(quán)最小的兩條邊，于是：w(T)+w(e1)+w(e2)w(C) 上式左邊的表達(dá)式即是w(C)的下界估計(jì)式。解：（1）去掉v3后的最優(yōu)數(shù)T3的權(quán)為w(T3)=5+5+1+7

30、=18,而與v3關(guān)聯(lián)的5條邊中權(quán)最小的兩條之權(quán)為w(e1)=8,w(e2)=9,因此下界估計(jì)值為w(C3)=18+8+9=35, ( 2 )去掉v4后，仿上有w(T4)=20, w(C4)=20+7+8=35; （3）去掉v5后, 有w(T5)=26, w(C5)=26+1+5=32.14、設(shè)G是一種賦權(quán)完全圖，其中對(duì)任意x,y,zV(G),都滿足 ： 證明：G中最優(yōu)H回路最多具有權(quán) 其中T是G中的一棵最優(yōu)樹(shù)。分析：H回路是指從圖中某點(diǎn)出發(fā)，經(jīng)過(guò)圖中每個(gè)頂點(diǎn)有且僅有一次，最后回到出發(fā)點(diǎn)的一條回路。由于G是一種賦權(quán)完全圖，所以從任意頂點(diǎn)出發(fā)包括了G的其他所有頂點(diǎn)有且僅有一次再回到原點(diǎn)的回路都構(gòu)成

31、了G的一條H回路，且最優(yōu)H回路C的權(quán)滿足 。因此只需證明G中存在一條H回路，其權(quán) 即可，因此證明本題的關(guān)鍵是找到滿足這個(gè)結(jié)論的H回路。 證明：設(shè)T是G中的一棵最優(yōu)樹(shù)，將T的每邊加倍得到圖，則的每個(gè)頂點(diǎn)的度數(shù)均為偶數(shù)。所以有一歐拉回路Q，設(shè)，(n|v(G)|)，Q中某些頂點(diǎn)可能有重復(fù)，且 。 在Q中，從v3開(kāi)始，凡前面出現(xiàn)過(guò)的頂點(diǎn)全部刪去，得到G的|v(G)|個(gè)頂點(diǎn)的一個(gè)排列。由于G是完全的，所以可以看作G中的一個(gè)H回路。在中任意邊(u,v)，在T中對(duì)應(yīng)存在唯一的(u,v)-通路P，由權(quán)的三角不等式有 。由于將中的邊(u,v)用T中的P來(lái)代替時(shí)，就得到Q，因而 。故G中的最優(yōu)H回路C的權(quán) 習(xí) 題

32、 九1證明：任何樹(shù)最多只有一個(gè)完美匹配分析：樹(shù)是連通沒(méi)有回路的圖；樹(shù)的完美匹配是樹(shù)存在一個(gè)匹配M，滿足樹(shù)的所有頂點(diǎn)v都是M-飽和點(diǎn)。而兩個(gè)完美匹配中不同的邊所關(guān)聯(lián)的頂點(diǎn)的度至少為2，否則如果等于1的話，則該頂點(diǎn)關(guān)聯(lián)的邊只有一條，在構(gòu)造完美匹配的時(shí)候?yàn)榱耸沟眠@個(gè)點(diǎn)成飽和點(diǎn)，只有一種選擇。證明：設(shè)樹(shù)有兩個(gè)或兩個(gè)以上的完美匹配，任取完美匹配和，。于是。易知邊導(dǎo)出子圖中的每個(gè)頂點(diǎn)滿足。于是中存在回路，從而中有回路。此與是樹(shù)矛盾，故結(jié)論成立。2證明：樹(shù)有完美匹配當(dāng)且僅當(dāng)對(duì)任意，均有分析：一方面，由定理9.1.3 圖G存在完美匹配當(dāng)且僅當(dāng)對(duì)任意SV(G)，有，所以如果樹(shù)G有完美匹配，則；而G有完美匹配，說(shuō)

33、明偶數(shù)，所以；從而有。 另一方面，如果對(duì)任意，均有，則對(duì)v而言，可利用這個(gè)這個(gè)奇分支找到v關(guān)聯(lián)的唯一邊，從而構(gòu)造出G的一個(gè)完美匹配。證明：必要性 設(shè)有完美匹配。由定理9.1.3，取，則 又 有完美匹配，偶數(shù)。于是=奇數(shù)。故 . 從而 .充分性 設(shè)對(duì)任意，有.即恰有一個(gè)奇分支，因是樹(shù)，故只能與中的一個(gè)頂點(diǎn)鄰接。設(shè)v與的關(guān)聯(lián)邊為。顯然v確定以后，uv是唯一確定的，且易知。因?yàn)镚-v只有一個(gè)奇分支，則G-u以后，v應(yīng)該與G-v的其他偶分支在一個(gè)連通分支中，而這個(gè)分支的頂點(diǎn)數(shù)顯然是奇數(shù)，從而構(gòu)成G-u的唯一一個(gè)奇分支，而u與這個(gè)奇分支中的頂點(diǎn)顯然也只有與v鄰接，所以。于是對(duì)任意，按這樣的方法構(gòu)造其關(guān)聯(lián)

34、邊，所的的匹配 就是G的一個(gè)完美匹配3設(shè)是奇數(shù)。舉出沒(méi)有完美匹配的-正則簡(jiǎn)單圖的例子。 分析：作G如下：取2k-1個(gè)頂點(diǎn)，在奇足標(biāo)頂點(diǎn)和偶足標(biāo)頂點(diǎn)間兩兩連以邊外，再連以邊，所得圖記為G0，顯然G0除外其余頂點(diǎn)的度均為k，而的度為k-1，取k個(gè)兩兩不相交的G0的拷貝和一個(gè)新頂點(diǎn)v0，并把每個(gè)G0拷貝中對(duì)應(yīng)于的頂點(diǎn)與v0相連以邊。最后所得的圖記為G，顯然G是k-正則的簡(jiǎn)單圖。又由于G0含2k-1個(gè)頂點(diǎn)，則G的頂點(diǎn)數(shù)為：k*(2k-1)+1。所以如果G有一個(gè)完美匹配M的話，則|M|=。假設(shè)M是G的一個(gè)完美匹配，則其邊應(yīng)來(lái)自k個(gè)獨(dú)立的G0，和跟v0相關(guān)聯(lián)的一條邊。而每個(gè)G0，其包含的頂點(diǎn)數(shù)為2k-1，

35、所以G0能提供給M的邊最多為k-1條，k個(gè)這樣的G0能提供給M的邊最多為k*(k-1)，因此M最多包含的邊為k*(k-1)+1=k2-(k-1)< ，因此G不可能有完美匹配。解：令k=3，得到的圖G0及G如下：V0V1V2V3V5V4V1V2V3V5V4V1V2V3V5V44設(shè)為偶數(shù)，舉出沒(méi)有完美匹配的-正則簡(jiǎn)單圖的例子. 分析：當(dāng)k為偶數(shù)時(shí)，取G=Kk+1，則G的頂點(diǎn)數(shù)為k+1，顯然G的頂點(diǎn)數(shù)為奇數(shù)，所以G無(wú)完美匹配。解：令k=2時(shí)，可構(gòu)造出無(wú)完美匹配的2-正則圖。5兩人在圖上進(jìn)行對(duì)奕雙方分別執(zhí)黑子和白子，輪流向G的不同頂點(diǎn)下子，要求當(dāng)i >0時(shí)，鄰接，并規(guī)定最后可下子的一方獲勝

36、。若規(guī)定執(zhí)黑子者先下子，試證明執(zhí)黑子的一方有取勝的策略當(dāng)且僅當(dāng)G無(wú)完美匹配。分析：假設(shè)G有完美匹配，則G的每個(gè)頂點(diǎn)都是M-飽和點(diǎn)，這樣先下者無(wú)論取哪個(gè)頂點(diǎn)，后下者都可取其相鄰的M-飽和點(diǎn)，這樣先下的人必輸；因此先下的人如要贏的話，G中肯定無(wú)完美匹配。 反過(guò)來(lái)，如果G中無(wú)完美匹配，由于任何圖都有最大匹配，則可找到G的一個(gè)最大匹配M，由于M不是完美匹配，因此G中存在M-非飽和點(diǎn)v，先下的黑方就可找到這個(gè)點(diǎn)下，則與v相鄰的下一個(gè)點(diǎn)必是M-飽和點(diǎn)，不然，Muv就是一個(gè)更大的匹配，與M是最大匹配矛盾。同理中不存在可增廣路，故黑方所選必是飽和點(diǎn)，如此下去，最后必是白方無(wú)子可下，故黑方必勝。 證明：必要性（

37、反證法） 若中存在一個(gè)完美匹配，則中任何點(diǎn)都是飽和點(diǎn)。故不論執(zhí)黑子（先下者）一方如何取，白方總可以取中和關(guān)聯(lián)邊的另一端點(diǎn)作為，于是，黑方必輸。 充分性. 設(shè)中不存在完美匹配，令是的最大匹配，而是非飽和點(diǎn)。于是，黑方可先取點(diǎn)，白方所選必是飽和點(diǎn)（因是最大的匹配）由的最大性可知中不存在可增廣路，故黑方所選必是飽和點(diǎn)，如此下去，最后必是白方無(wú)子可下，故黑方必勝。6證明：二分圖有完美匹配當(dāng)且僅當(dāng)對(duì)任何，有 成立 舉例說(shuō)明若不是二分圖，則上述條件未必充分。分析：由定理9.1.2Hall定理，對(duì)于具有二劃分（X,Y）的二分圖，G有飽和X中每個(gè)頂點(diǎn)的匹配當(dāng)且僅當(dāng)對(duì)任意的,有，顯然如果G有完美匹配M的話，則M

38、既飽和X，也飽和Y。但當(dāng)G不是二分圖時(shí)，這個(gè)結(jié)論不一定成立，如K2n+1對(duì)任意的滿足，但它無(wú)完美匹配。 證明：必要性. 設(shè)有完美匹配，則飽和及，由定理和對(duì)任何或，有今任取，有于是有 充分性：設(shè)對(duì)任何，有.即任取，有，于是由定理，存在飽和的匹配，同理，存在飽和的匹配，從而，易知和都是完美匹配。當(dāng)不是二分圖時(shí)，條件不充分，如。7個(gè)學(xué)生做化學(xué)實(shí)驗(yàn)，每?jī)蓚€(gè)人一組，如果每對(duì)學(xué)生只在一起互作一次實(shí)驗(yàn)，試作出一個(gè)安排，使任意兩個(gè)學(xué)生都在一起做過(guò)實(shí)驗(yàn)。分析：該題可轉(zhuǎn)化為對(duì)具有2n個(gè)頂點(diǎn)（可分別記為0，1，2，2n-1）的完全圖構(gòu)造其不同的2n-1個(gè)完美匹配，使得（0，1）（0，2）（0，2n-1），（1，2）

39、（1，3），（1，2n-1），（2n-2,2n-1）在這2n-1個(gè)匹配中出現(xiàn)且僅出現(xiàn)一次。 解： 共安排2n-1次實(shí)驗(yàn)，可使任意兩個(gè)學(xué)生都在一起做過(guò)實(shí)驗(yàn)。安排如下： 第1次：(0, 1), (2, 2n-1), (3, 2n-2), , (x, y)。 其中， x+y=2n+1; 第2次：(0, 2), (3, 1), (4, 2n-1), , (x, y) 。 其中， x+y=2n+3; 第2n-1次：(0, 2n-1), (1, 2n-2), (2, 2n-3), , (x, y) 。 其中， x+y=2n-1;8試證明：任何一個(gè)（0,1）矩陣中，包含元素1的行或列的最小數(shù)目，等于位于不同

40、行不同列的1的最大數(shù)目。分析：由定理9.2.2，對(duì)二分圖G，均成立（其中為G的最大匹配數(shù)，為G的點(diǎn)覆蓋數(shù)）。將給定的（0，1）矩陣表示成一個(gè)二分圖，.其中當(dāng)且僅當(dāng)該題轉(zhuǎn)化為了判斷G的和的關(guān)系。 證明： 設(shè)是一個(gè)（0,1）矩陣.將表示成一個(gè)二分圖，.其中當(dāng)且僅當(dāng)于是，的（最?。c(diǎn)覆蓋數(shù)等于含中元素1的行（第行元素1的數(shù)目表示頂點(diǎn)覆蓋的邊之?dāng)?shù)目）或列（第列元素1的數(shù)目表示頂點(diǎn)覆蓋的邊數(shù)目）的數(shù)目。而的最大匹配數(shù)等于中位于不同行不同列的1的最大數(shù)目.由定理9.2.2知，若為二分圖，則。故結(jié)論成立.9能否用5個(gè)的長(zhǎng)方表將圖9-13中的10個(gè)正方形完全遮蓋??？圖9-13分析：按如下方法作出圖：在圖9-1

41、3的每個(gè)正方形格子中放一個(gè)頂點(diǎn)，與鄰接當(dāng)且僅當(dāng)與所在的方格有公共邊。則該問(wèn)題等價(jià)于判斷相應(yīng)圖是否有完美匹配，解：按照分析，構(gòu)造圖如下：則有，由定理9.1.3可判斷它沒(méi)有完美匹配。因此不能用5個(gè)的長(zhǎng)方表將圖9-13中的10個(gè)正方形完全遮蓋住。u10試證明：是二分圖當(dāng)且僅當(dāng)對(duì)的每個(gè)子圖均有。分析：若G=（X，Y）是二分圖，顯然X和Y都構(gòu)成G的點(diǎn)獨(dú)立集，所以G的最大獨(dú)立數(shù)，且；而二分圖的每個(gè)子圖顯然也是二分圖。證明：必要性.設(shè)是二分圖，于是的任何子圖也是二分圖，設(shè)，。不妨設(shè)。顯然 ， 因此，。于是，。充分性. 若不是二分圖，則中含奇回路。令。顯然，。 矛盾。故是二分圖。11試證明：是二分圖當(dāng)且僅當(dāng)對(duì)

42、的每個(gè)適合的子圖，均有.分析：是指G的最大獨(dú)立集，是指G的邊覆蓋數(shù)。 如果G是不含孤立點(diǎn)的二分圖（X，Y），顯然=max(|X|,|Y|)，因此如果能證明=max(|X|,|Y|)，則對(duì)不含孤立點(diǎn)的二分圖G，有證明： 必要性. 設(shè)是二分圖。 ，即無(wú)孤立點(diǎn)。顯然也是二分圖，設(shè)，且。于是，。而一條邊最多覆蓋一個(gè)頂點(diǎn)，故。但由于無(wú)孤立點(diǎn)，因此，故。充分性. 若不是二分圖，則含奇回路。設(shè)。于是 ，而。矛盾。故必為二分圖。12設(shè)是具有劃分（X，Y）的二分圖。證明：若對(duì)于任何.均有，則有飽和中每一頂點(diǎn)的匹配。分析：根據(jù)定理9.1.2，二分圖G有飽和X中每個(gè)點(diǎn)的匹配當(dāng)且僅當(dāng)對(duì)任何，有根據(jù)這個(gè)結(jié)論，如果能說(shuō)明

43、滿足條件的二分圖G中不存在任何，有，則題目得證。證明： 由題意知，對(duì)。若中不存在飽和的匹配，則由Hall定理，存在，使。設(shè)，其中。由對(duì)任何，得，但由于S中的點(diǎn)關(guān)聯(lián)的邊都是的點(diǎn)關(guān)聯(lián)的邊，因此，因此有，但，因此在中總存在一點(diǎn)，有。矛盾。故中存在飽和的匹配。13證明（Hall定理的推廣）：在以為二劃分的二分圖G中，最大匹配數(shù)為 分析：由定理9.2.2有：如果一個(gè)圖G是二分圖，則，是G的最大匹配數(shù)，是G的最小覆蓋。因此如果能說(shuō)明等于的話，則本題得以證明。證明：由于，所以=顯然是G的一個(gè)覆蓋，而G的任意一個(gè)覆蓋都可以寫(xiě)成的形式，所以=因此有=14證明：在無(wú)孤立點(diǎn)的二分圖G中，最大獨(dú)立集的頂點(diǎn)集(G)等于

44、最小邊覆蓋數(shù)。證明：參見(jiàn)題1115在9個(gè)人的人群中，假設(shè)有一個(gè)人認(rèn)識(shí)另外兩個(gè)人，有兩個(gè)人每人認(rèn)識(shí)另外4個(gè)人，有4個(gè)人認(rèn)識(shí)另外5個(gè)人，余下的兩個(gè)人每人認(rèn)識(shí)另外的6個(gè)人。證明：有3個(gè)人，他們?nèi)炕ハ嗾J(rèn)識(shí)。分析：將該題中的人用圖中的節(jié)點(diǎn)表示，兩個(gè)節(jié)點(diǎn)有連線當(dāng)且僅當(dāng)兩個(gè)人認(rèn)識(shí)，則該題轉(zhuǎn)化為求證滿足上述條件的圖G含有一個(gè)K3。 要判斷一個(gè)圖是否含有K3，我們先要了解以下概念和定理：T2，p：具有p個(gè)頂點(diǎn)的完全2分圖，如果p是偶數(shù)，則該圖的每一部分頂點(diǎn)數(shù)為p/2；如果p為奇數(shù)，則該圖的其中一部分頂點(diǎn)數(shù)為(p-1)/2，另一部分頂點(diǎn)數(shù)為(p+1)/2。Turan定理（托蘭定理）的推論：若簡(jiǎn)單圖G不含K3，則

45、E(G)E(T2,p)，且當(dāng)E(G)=E(T2,p)時(shí)，有該定理的嚴(yán)格內(nèi)容為：若簡(jiǎn)單圖G不含Km+1，則E(G)E(Tm，p)，且當(dāng)E(G)=E(Tm，p)時(shí)，有其中Tm，p為具有p個(gè)頂點(diǎn)的完全m部圖。這里我們令m=2，只說(shuō)明我們所要的結(jié)論。 這個(gè)定理的證明請(qǐng)參看Bondy和Murty著的Graph Theory with Applications中的定理7.9及其證明。按照這個(gè)定理，我們只需判斷E（G）>E(T2，9)=20即可。證明： 方法一：由題意，可作一個(gè)9個(gè)點(diǎn)的圖，各頂點(diǎn)度序列為。于是有> E(T2，9)=4*5=20由托蘭定理推論有G含有一個(gè)K3，所以9人中的至少有三個(gè)

46、相互認(rèn)識(shí)。方法二（反證法）假設(shè)9人中的任意三個(gè)都互不認(rèn)識(shí)。由題意，設(shè)，如圖，于是，中的任何兩頂點(diǎn)互不鄰接，從而。因此，只有或以及。但由題設(shè)，至少有8人認(rèn)識(shí)3個(gè)以上的人，此與題意不符。16設(shè)（）是簡(jiǎn)單圖，且，則中包含三角形，請(qǐng)證明此結(jié)論。分析：該題也可利用托蘭定理的推論，如果能證明q>E（T2，p），則可判斷G中包含三角形。證明：當(dāng)p為偶數(shù)時(shí)，E（T2，p）=由已知條件E（G）= E（T2，p） 當(dāng)p為奇數(shù)時(shí)，E（T2，p）=由已知條件E（G）=>=E（T2，p）由以上分析可知，當(dāng)時(shí)，有E（G）> E（T2，p），所以G中包含三角形。17試找出一個(gè)簡(jiǎn)單圖，使得，但不包含三角形。

47、分析：由于T2，p不包含三角形，且當(dāng)p為偶數(shù)時(shí)，當(dāng)p為奇數(shù)時(shí)，所以任意的T2，p都是滿足題目條件的不包含三角形的圖。解：取p=4，則T2，4右圖所示。18將的邊著紅色或蘭色，使其中既無(wú)三邊紅色的，也無(wú)10條邊全著蘭色的。分析：如教材圖9-11，將圖中不鄰接的兩頂點(diǎn)之間用蘭色的邊聯(lián)結(jié)，將鄰接的兩頂點(diǎn)之間的邊著成紅色，即滿足題要求。解：著色結(jié)果如下圖。19設(shè)，求證分析：是指包含k團(tuán)或l獨(dú)立集的頂點(diǎn)數(shù)最少的圖的頂點(diǎn)數(shù)。顯然，如果定，的由定理9.3.3當(dāng)m2時(shí)，。證明 , 20證明：當(dāng)時(shí)，分析：此結(jié)論的證明可仿照定理9.3.3的方法令，如果能證明Yp中只有不到半數(shù)的圖含有k團(tuán)，同時(shí)Yp中也只有不到半數(shù)

48、的圖含有k獨(dú)立集。于是Yp中必存在某個(gè)圖它既不含有k團(tuán)，也不含k獨(dú)立集，由于這個(gè)結(jié)論對(duì)任意的圖都成立，因此有: 證明：在定理9.3.3的證明中，取.于是，有令，則 又，故對(duì)于一切，于是，仿定理9.3.3之證明，即得21在匈牙利算法的第3步中，假如y是非M飽和的，如何得到一條從u到y(tǒng)的M可增廣路？分析： 由二分圖的定義及增廣路徑的定義，可知二分圖中的增廣路徑具有如下性質(zhì)：(1) 起點(diǎn)和終點(diǎn)都是非M-飽和點(diǎn)，而其它所有點(diǎn)都是M-飽和點(diǎn)。(2) 整條路徑上沒(méi)有重復(fù)的點(diǎn)。(3)路徑上總共有奇數(shù)條邊，且所有第奇數(shù)條邊都不在M中，所有第偶數(shù)條邊都在M中。(4)把增廣路徑上的所有第奇數(shù)條邊加入到原匹配中去，

49、并把增廣路徑中的所有第偶數(shù)條邊從原匹配中刪除（這個(gè)操作稱為增廣路徑的取反），則新的匹配數(shù)就比原匹配數(shù)增加了1個(gè)。解：根據(jù)以上分析，可得到求從u到非M飽和點(diǎn)y的M可增廣路徑的算法如下：1For i=0 to n 2. pre(vi)=null3 Succ(vi)=null 4 d(u)=0,d(vi)=/初始置每個(gè)頂點(diǎn)的前導(dǎo)和后繼頂點(diǎn)為null，u與u的距離為0，其他點(diǎn)與u的距離為5 S=u /以u(píng)為初始頂點(diǎn)構(gòu)造所有的M-交錯(cuò)路，直到頂點(diǎn)y在某條交錯(cuò)路上為止4While (y不屬于S) 5 任取S中的頂點(diǎn)v，6. if succ(v)=null7 For 每個(gè)與v鄰接的頂點(diǎn)w 8 If （w是M

50、-飽和點(diǎn)并且 pre(w)null）d(w)=d(v)+1 9. if （(d(w)是奇數(shù)并且vw不屬于M)或者(d(w)是偶數(shù)并且vw屬于M)9 succ(v)null，pre(w)=v，S=SW 10 11 /結(jié)束while循環(huán)找到了一條從u到y(tǒng)的M-可增廣路算法結(jié)束以后得到一條路徑P=ypre(y) pre(pre(y) u則P-即為一條從u到y(tǒng)的M-可增廣路徑。22說(shuō)明在匈牙利算法的第3步中，執(zhí)行 后，所得到的M 仍是G 的一個(gè)匹配. 說(shuō)明：因?yàn)镻是一條M可增廣路，所以可以看作在P上，保留第奇數(shù)條邊，去掉第偶數(shù)條得到的一個(gè)邊集，顯然P的所有偶數(shù)條邊是沒(méi)有公共頂點(diǎn)的，所以仍是G的一個(gè)匹配。23在圖9-12中