1、習 題 六1設是一個無回路的圖, 求證：若中任意兩個頂點間有惟一的通路, 則是樹. 證明：由假設知，是一個無回路的連通圖，故是樹。2證明：非平凡樹的最長通路的起點和終點均為懸掛點. 分析：利用最長通路的性質可證。 證明：設是樹中的極長通路。若的起點滿足，則不是中極長的通路。對終點也可同理討論。故結論成立。3證明：恰有兩個懸掛點的樹是一條通路. 分析：因為樹是連通沒有回路的，所以樹中至少存在一條通路P。因此只需證明恰有兩個懸掛點的樹中的所有的點都在這條通路P中即可。證明：設是樹中的兩個懸掛點，即。因是樹，所以存在-通路：。顯然，。若，則由恰有兩個懸掛點的假設，可知中有回路；若中還有頂點不在中，則

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

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

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

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

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

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

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

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

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

11、G-v1連通,則v2是G1的割點且v2在G1中的度小于等于，類似于(2)知在G1中存在一割邊e2(關聯v2)使得G1-e2不連通另一方面由于(G)>=K(G)=2故G-e2連通由于G1-e2= (G-e2)-v1，故v1是G-e2的割點，且v1在G-e2中的度小于等于，于是類似于(2)知，在G-e2中存在一割邊e1，即(G-e2)-e1=G-e1,e2不連通，故(G)=2.所以(G)=K(G). () 設k(G) =3,于是， 有3 =k（G） (G)=3 ,知8證明：一個圖是邊連通的當且僅當的任意兩個頂點由至少兩條邊不重的通路所連通.分析：這個題的證明關鍵是理解邊連通的定義。證明：（必

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

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

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

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

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

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

18、頂點割集。設是一個的任一頂點子集，可分和兩種情形證明。證明：(1) 當時，根據定理7.3.1的證明，不是的頂點割集，當然更不是在上加些邊的的頂點割集。(2) 當時，設是的頂點割集，屬于的不同分支。考察頂點集合和 這里加法取模若或中有一個含的頂點少于個，則在中存在從到的路。與為頂點割集矛盾。若和中都有的個頂點，則：j 若或中，有一個(不妨說)中的個頂點不是相繼連成段，則中存在從到的路。與為頂點割集矛盾。k 若與中，的個頂點都是相繼連成一段的。若與中至少有一個沒有被分成兩段，則立即與為頂點割集矛盾；若被分成兩段：含的記，含的記，且也被分為兩段：含的記，含的記。這樣，被分為兩段：含的 和含的。這兩段

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

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

21、pqG1奇數奇數G2偶數奇數G3奇數偶數3、求證：若G 是 E 圖，則 G 的每個塊也是 E 圖。 分析：一個圖如果含有E回路，則該圖是E圖；另一方面一個塊是G中不含割點的極大連通不可分子圖，且非割點不可能屬于兩個或兩個以上的塊。這樣沿G中的一條E回路遍歷G的所有邊時，從一個塊到達另一個塊時，只能經過割點才能實現。證明：設B是G的塊，任取G中一條E回路C，由B中的某一點v出發，沿C前進，C只有經過G的割點才能離開B，也就是說只有經過同一個割點才能回到B中，注意到這個事實后，我們將C中屬于B外的一個個閉筆回路除去，最后回到v時，我們得到的就是B上的一個E回路，所以B也是E圖。4、求證：若G無奇點

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

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

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

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

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

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

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

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

30、=18,而與v3關聯的5條邊中權最小的兩條之權為w(e1)=8,w(e2)=9,因此下界估計值為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、設G是一種賦權完全圖，其中對任意x,y,zV(G),都滿足 ： 證明：G中最優H回路最多具有權 其中T是G中的一棵最優樹。分析：H回路是指從圖中某點出發，經過圖中每個頂點有且僅有一次，最后回到出發點的一條回路。由于G是一種賦權完全圖，所以從任意頂點出發包括了G的其他所有頂點有且僅有一次再回到原點的回路都構成

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

32、 九1證明：任何樹最多只有一個完美匹配分析：樹是連通沒有回路的圖；樹的完美匹配是樹存在一個匹配M，滿足樹的所有頂點v都是M-飽和點。而兩個完美匹配中不同的邊所關聯的頂點的度至少為2，否則如果等于1的話，則該頂點關聯的邊只有一條，在構造完美匹配的時候為了使得這個點成飽和點，只有一種選擇。證明：設樹有兩個或兩個以上的完美匹配，任取完美匹配和，。于是。易知邊導出子圖中的每個頂點滿足。于是中存在回路，從而中有回路。此與是樹矛盾，故結論成立。2證明：樹有完美匹配當且僅當對任意，均有分析：一方面，由定理9.1.3 圖G存在完美匹配當且僅當對任意SV(G)，有，所以如果樹G有完美匹配，則；而G有完美匹配，說

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

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

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

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

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

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

39、（1，3），（1，2n-1），（2n-2,2n-1）在這2n-1個匹配中出現且僅出現一次。 解： 共安排2n-1次實驗，可使任意兩個學生都在一起做過實驗。安排如下： 第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試證明：任何一個（0,1）矩陣中，包含元素1的行或列的最小數目，等于位于不同

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

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

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

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

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

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

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

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

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

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

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