張清華圖論課后題答案

1、第1章 圖論預(yù)備知識(shí)1.1 解：(1) p=,a,b,c,a,b,a,c,b,c,a,b,c(2) p=,a,b,c,a,b,c(3) p=,(4) p=,(5)p=,a,b,a,a,b,a,b,a,b,a,b,a,a,b,a,b,a,b,a,b,a,b,a,a,b,a,b,a,b1.2 解：(1) 真 (2) 假 (3)假 (4)假1.3 解：(1) 不成立，A=1 B=1,2 C=2 (2) 不成立，A=1 B=1,2 C=1,31.4 證明：設(shè)(x,y)(AB)X(CD) 說(shuō)明xAB,yCD 由于 xA,yC 所以 (x,y) A X C 由于xB,yD 所以 (x,y) B X D 所

2、以 (x,y) （A X C）（B X D） 反過(guò)來(lái)，如果（x,y）(A X C) （B X D） 由于 (x,y) （A X C）所以 xA,yC 由于 (x,y) （B X D）所以xB,yD 所以x(AB) y(CD) 所以 (x,y) (AB)X(CD) 所以(AB)X(CD)= (A X C) （B X D）1.5 解：Hasse圖12249431025極大元9,24,10,7極小元3,2,5,7最大元24最小元21.6 解 (1)R=<x,y>|x整除y468(2)關(guān)系圖為：9102571(3)不存在最大元，最小元為21.7 解：(1)R=<1,1>,<

3、;2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>(2) 略(3) IAR 故R是自反的。<1,2>R <2,3>R 但是<1,3>R 故不滿(mǎn)足傳遞性1.8 解：(1) 不成立 A=1 B=2 C=3 D=4 則左式=<1,3>，<1,4>,<2,3>,<2,4> 右式=<1,3>,<2,4>(2) 不成立 A=1,3 B=1 C=2,4 D=2 則左式=<3,4>右

4、式=<1,4>,<3,2>,<3,4>(3) 不成立 A=1 B=2 C=3 D=4 則左式=<1,3>,<1,4>,<2,3>,<2,4> 右式=<1,3>,<2,4>(4) 成立 證明：設(shè)<x,y>(A-B)X C x(A-B) yCxAxB yC<x,y>A X C<x,y>B X C<x,y>(A X C)-(B XC) 故得 （A-B）X C=（A X C）-（B X C）1.9 略1.10略1.11 解：A為n個(gè)元素的優(yōu)先級(jí)和，

5、A上有2n2 個(gè) 不同的二元關(guān)系，理由為：設(shè)A，B為集合，AXB的任何子集所定義的二元關(guān)系稱(chēng)作從A到B的二元關(guān)系，特別當(dāng)A=B時(shí)，稱(chēng)作A上的二元關(guān)系，若|A|=n，則|AXA|=n2，那么A上共有2n2個(gè)不同的二元關(guān)系。1.12略1.13 解：1)真.由于R1和R2和R2都是自反的,因而對(duì)任何,都有(x,x)R1,(x,x)R2.因此,對(duì)任何xA,都有(x,x)R1R2.所以R1R2是自反的。2)假.令A(yù)=a,b,R1=(a,b),R2=b,a.那么R1R2=(a,a),它就不是A上的反自反關(guān)系.3)假.令A(yù)=a,b,c,R1=(a,b),(b,a),R2=(b,c),(c,b).那末R1R2

6、=(a,c),就不是A的對(duì)稱(chēng)關(guān)系.4)假.令A(yù)=a,b,c,d,R1=(a,c),(b,c),R2=(c,b),(d,a)易證R1,R2都是反對(duì)稱(chēng)關(guān)系.但是R1R2=(a,b),(b,a)就不是A上的反對(duì)稱(chēng)關(guān)系.5)假.令A(yù)=a,b,c,R1=(a,c),(b,a),(b,c),R2=(c,b),(a,c),(a,b),易證R1和R2都是傳遞關(guān)系,但R1R2=(a,b),(b,b),(b,c)就不是A上的傳遞關(guān)系.1.14 證明：由任意的a，存在一個(gè)b，使得<a,b>R,由對(duì)稱(chēng)性所以<b,a>R,由傳遞性<a,a>R,所以R是等價(jià)關(guān)系。1.15 證明：xA，

7、<x,x>R,<x,x>S<x,x>RS，所以RS有自反性；x,yA,因?yàn)镽,S是反對(duì)稱(chēng)的，<x,y>RS<y,x>RS(<x,y>R<x,y>S) (<y,x>R<y,x>S)(<x,y>R<y,x>R) (<x,y>S<y,x>S)x=yy=xx=y所以，RS有反對(duì)稱(chēng)性。x,y,zA,因?yàn)镽,S是傳遞的，<x,y>RS<y,z>RS<x,y>R<x,y>S<y,z>R<y

8、,z>S<x,y>R<y,z>R<x,y>S<y,z>S<x,z>R<x,z>S<x,z>RS所以，RS有傳遞性。所以RS也是A上的偏序關(guān)系。1.16 解：r(R)=<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<1,2>,<2,3>,<2,5>,<3,4>,<4,3>,<5,5>s(R)=<1,2>,<2,1>,<2,3>,

9、<3,2>,<2,5>,<5,2>,<3,4>,<4,3>,<5,5>t(R)=<1,2>,<1,3>,<1,4>,<1,5>,<2,3>,<2,4>,<2,5>,<3,3>,<3,4>,<4,3>,<4,4>,<5,5>1.17 (1)證明：對(duì)任意a,b,a+b=a+b,故得(a,b)R(a,b),關(guān)系R具有自反性;如果(a,b)R(c,d),則a+d=b+c,c+b=d+a,故

10、得(c,d)R(a,b),關(guān)系R具有對(duì)稱(chēng)性;如果(a,b)R(c,d),(c,d)R(e,f),則a+d=b+c,c+f=d+e,故得a+f=b+e,(a,b)R(e,f),關(guān)系R具有傳遞性;于是關(guān)系R是等價(jià)關(guān)系.1.18 略1.19略1.20 解： (1) 單射(2) 滿(mǎn)射(3) 既不是單射，也不是滿(mǎn)射(4) 滿(mǎn)射(5) 雙射1.21 解：(1) O(n3)(2) O(n5)(3) O(n3n!)第2章 圖2.1解：(1)a:出度為3、入度為1b:出度為2、入度為2c:出度為2、入度為3d:出度為2、入度為3e:出度為2、入度為2abcde    &#

11、160;(2)a:出度為3、入度為1b:出度為1、入度為2c:出度為3、入度為3d:出度為3、入度為2e:出度為0、入度為3abcde     2.2解：構(gòu)成無(wú)向圖的度序列：(1)、(2)、(3)、(4)、(6)構(gòu)成無(wú)向簡(jiǎn)單圖的度序列：(2)、(3)、(4)2.3解：補(bǔ)圖為：     2.4解：設(shè)圖G中結(jié)點(diǎn)數(shù)為n,則有3x4+3x(n-3)=2x12.求得n=7,即圖G有7個(gè)結(jié)點(diǎn).2.5 證明將習(xí)圖2.2的兩圖頂點(diǎn)標(biāo)號(hào)為如下的(a)與(b)圖作映射f : f(vi)®ui (1

12、3; i £ 10)容易證明，對(duì)"vivjÎE(a),有f(vivj)=uiujÎE(b) (1£ i £ 10, 1£j£ 10 )由圖的同構(gòu)定義知，兩個(gè)圖是同構(gòu)的。2.6解：同構(gòu)對(duì)應(yīng)關(guān)系：a8、b7、c4、d9、e5、f6、g1、h2、i10、j3.2.7證：設(shè)在一有向完全圖G中，邊數(shù)為n.則可知deg+vi=deg-vi=n.即所有結(jié)點(diǎn)的入度和等于所有節(jié)點(diǎn)的出度和，即所有結(jié)點(diǎn)的入度的平方和等于所有節(jié)點(diǎn)的出度的平方和。2.8解：(1)      

13、60;     (2)                    2.9證明：用反證法。設(shè)無(wú)向圖G只有兩個(gè)奇點(diǎn)u,v，若u,v不連通，即它們之間沒(méi)任何通路，則G至少有兩個(gè)連通分支G1,G2，且u,v分別屬于G1和G2，于是G1和G2中各有一個(gè)奇度結(jié)點(diǎn)，與握手定理矛盾，因此u,v必連通。2.10解：點(diǎn)割集為：v1，v3、v4、v6割點(diǎn)為：v4、v62.1

14、1解：強(qiáng)連通圖：(a）單相連通圖：（b）（c）（d）弱連通圖：（a）（b）（c）（d）2.12證明:設(shè)v0v1vk為G中一條最長(zhǎng)路，則v0的鄰接頂點(diǎn)一定在該路上，否則，與假設(shè)矛盾。現(xiàn)取與v0相鄰的腳標(biāo)最大者，記為l，則l³d,于是得圈v0v1v2vlv0,該圈長(zhǎng)為l+1，顯然不小于+1。2.13證明：證其逆否命題：e不是割邊當(dāng)且僅當(dāng)e含在G的某個(gè)圈中。 必要性：設(shè)e=xy不是割邊。假定e位于G的某個(gè)連通分支G1中，則G1-e仍連通。故在G1_e中有(x,y)路P，P+e便構(gòu)成G1中一個(gè)含有e的圈。 充分性：設(shè)e含在G的某個(gè)圈C中，而C含于某連通分支G1中，則G1-

15、e仍連通。故W(G-e)=W(G)，這說(shuō)明e不是割邊,證畢。2.14證明：用數(shù)學(xué)歸納法證明： （1）n=1時(shí)，G為平凡圖，顯然G連通。（2）n=2時(shí)，m12n-1n-2+1=1此時(shí)G為K2，當(dāng)然連通。（3）假設(shè)當(dāng)n=k（k2）時(shí)，m12n-1n-2+1結(jié)論成立。 當(dāng)n=k+1時(shí)，若此時(shí)每個(gè)結(jié)點(diǎn)度數(shù)為k，則結(jié)論顯然成立，否則必存在一個(gè)結(jié)點(diǎn)v度數(shù)至多只有k-1度，即這個(gè)結(jié)點(diǎn)最多只有k-1條邊和它相連。因?yàn)榇藭r(shí)總的邊數(shù)m12kk-1,則其它k個(gè)結(jié)點(diǎn)之間的邊數(shù)m'12kk-1-(k-1)=12k-1k-2。根據(jù)歸納假設(shè)，顯然這k個(gè)結(jié)點(diǎn)之間是連通的，而根據(jù)上面我們知道，至少有

16、一條邊使v和其它結(jié)點(diǎn)相連，所以此時(shí)這個(gè)圖是連通的,結(jié)論成立。2.15證明：（1）因?yàn)镚連通，且G無(wú)割邊，所以任意兩個(gè)結(jié)點(diǎn)u,v，都存在簡(jiǎn)單道路p=uwv.又因?yàn)镚無(wú)割邊，所以，刪除邊wv后，子圖依然連通，即w,v存在簡(jiǎn)單道路p',以此類(lèi)推，可以找到一條和p每條邊都不相同的p=vu,這樣p和p就構(gòu)成了一條回路。  （2）因?yàn)镚中任意兩個(gè)結(jié)點(diǎn)都位于同一回路中，所以任意結(jié)點(diǎn)u,和任意邊e的兩個(gè)端點(diǎn)v1,v2都分別在兩個(gè)回路C1，C2中，如果C1=C2=uv1v2u,那么將回路中v1v2,用v1v2=e替換，就得到新的新的回路，并滿(mǎn)足要求。如果C1C2，C1=uv1u,C2

17、=uv2u,那么構(gòu)成新的道路P=uv1uv2u,在其中將重復(fù)邊剔出掉，得到新的回路C3，其中包含v1,v2結(jié)點(diǎn)，可以將回路中v1v2用v1v2=e替換，就得到新的新的回路，并滿(mǎn)足要求。  （3）對(duì)任意兩條邊e1,e2其端點(diǎn)分別為u1,u2,v1,v2。根據(jù)（2）存在回路C1 = u1v1v2u1,C2=u2v1v2u2。那么可以形成新的閉道路P=u1v1v2u2v1v2u1,在其中將重復(fù)邊剔出到，得到新的回路C3，其中包含e2和u1,u2結(jié)點(diǎn)，可以將回路中u1u2用u1u2=e1替換，就得到新的新的回路，包含e1,e2,滿(mǎn)足要求。  

18、(4)因?yàn)槿我鈨蓷l邊都在同一回路中，所以不存在割邊。假設(shè)邊e是割邊，那么刪除此邊，圖不連通，分支中的任何一對(duì)不在同一分支中的邊，不能構(gòu)成回路，與條件矛盾。所以，G中無(wú)割邊。2.16解：(1)deg(v1)=2、deg(v2)=3(2)否 (3) 4(4)略2.17解：(1)A=0101001101010100(2)A2=0111020101110011A3=0212012202120201A4=0323041303230322V1到V4長(zhǎng)度為1、2、3、4的路各有1、1、2、3條。2.18解：無(wú)向圖G:    v1v2v3v4v5可達(dá)矩陣P = 1111

19、111111111111111111111 有可達(dá)矩陣可知改圖為強(qiáng)連通圖。2.19解：(1) 鄰接矩陣A = 1200000100011010(2) G中長(zhǎng)度為3的通路有23條，其中有7條為回路。(3) 圖G為強(qiáng)連通圖2.20解：鄰接矩陣 A = 1201200000011010關(guān)聯(lián)矩陣 M(G) = 211100110000001000112.21解：(1)當(dāng)r=1時(shí)，沒(méi)有長(zhǎng)度大于等于1的圈。 當(dāng)2rs時(shí)，有長(zhǎng)度為4,6,2r的圈，它們都是偶圈，因而非同構(gòu)的圈共有r-1種。 (2)至多有r個(gè)頂點(diǎn)彼此不相鄰。 (3)至多有r條邊彼此不相鄰。 (4)k= r 2.22證明：反證法。若存在某個(gè)具有

20、奇數(shù)個(gè)面，且每個(gè)面均有奇數(shù)條棱的多面體V，不妨設(shè)V有r(r為奇數(shù))個(gè)面，設(shè)為R1,R2,Rr，S1,S2,Sr分別為它們的棱數(shù)，均為奇數(shù)。作無(wú)向圖G如下：在V的每個(gè)面中放一個(gè)頂點(diǎn)vi，i=1,2,r, 且兩個(gè)面Ri與Rj有公共面就連邊。若存在這樣的無(wú)向圖G，則d(vi)均為奇數(shù)Si，由握手定理得i=1dvi=i=1Si=2m(m為邊數(shù))但因r,Si(i=1,2,n)均為奇數(shù)，上面等式不可能成立。故不存在這樣的無(wú)向圖G，從而也不存在滿(mǎn)足要求的多面體。2.23解：設(shè)G是n階m條邊的自補(bǔ)圖,即G為n階m條邊的簡(jiǎn)單圖,且GG 。于是，G 的邊數(shù)m=m，且m+m'=2m=n(n-1)/2。于是n

21、(n-1)=4m，因而n=4k，或n-1=4k，k為正整數(shù)。2.24證明：為偶數(shù)(n為奇數(shù))。于是，若為奇數(shù)，必有dG(v)也為奇數(shù)。故與G中奇度頂點(diǎn)個(gè)數(shù)相等。2.25解:都可以實(shí)現(xiàn)，如下圖   (1)     (2)2.26解：(1)錯(cuò)誤、(2)正確、(3)正確2.27略2.28解：無(wú)向完全圖Kn當(dāng)n3且n為奇數(shù)時(shí)才是歐拉圖。 當(dāng)n>3且n為偶數(shù)時(shí)存在歐拉路而不存在歐拉回路。2.29 略2.30 略2.31 略第3章 樹(shù)與最短路徑3.1該樹(shù)的結(jié)點(diǎn)個(gè)數(shù)n=5，故邊數(shù)m=n-1=4,因?yàn)椋?個(gè)結(jié)點(diǎn)分配的度數(shù)

22、為8，由于樹(shù)是簡(jiǎn)單連通圖，知，則該樹(shù)的度數(shù)序列必是下列情況之一，(1)1，1，2，2，2(2)1，1，1，2，3(3)1，1，1，1，4這些度數(shù)序列對(duì)應(yīng)的簡(jiǎn)單樹(shù)為3.2該樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為，則邊數(shù)，又因?yàn)?，所以可知一棵?shù)的結(jié)點(diǎn)個(gè)數(shù)之和為。3.3設(shè)有n個(gè)一度結(jié)點(diǎn)，則結(jié)點(diǎn)個(gè)數(shù)為=3+5+8+n，邊數(shù)為=3+5+8+n-1,則.可得n=23.3.4設(shè)有n個(gè)一度結(jié)點(diǎn)，則：3.5反證法。假設(shè)沒(méi)有結(jié)點(diǎn)度數(shù)大于等于3的結(jié)點(diǎn)，則只有度為1的結(jié)點(diǎn)3個(gè)和度為2的結(jié)點(diǎn)n個(gè)。邊數(shù)：3+n-1，度數(shù)：3+2n.所以2（3+n-1）=3+2n。等式左邊為偶數(shù)，右邊為奇數(shù)，相互矛盾，假設(shè)不成立。所以至少有一個(gè)結(jié)點(diǎn)度數(shù)大于等于3

23、.3.6設(shè)度為的結(jié)點(diǎn)個(gè)數(shù)為則則由于，故全為0.當(dāng)時(shí)，只有兩個(gè)度為1的結(jié)點(diǎn)，所以T是一條直線(xiàn)。當(dāng)時(shí)，有兩個(gè)度為1的結(jié)點(diǎn)，其他結(jié)點(diǎn)度數(shù)都為2，T仍為一條直線(xiàn)。綜上T是一條直線(xiàn)。3.7=>若為度數(shù)序列,則該樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為n，邊數(shù)為n-1,所以<=若，則該樹(shù)的結(jié)點(diǎn)為n，且結(jié)點(diǎn)度數(shù)依次為。即是一棵樹(shù)的度數(shù)序列。3.8證明假設(shè)中沒(méi)有樹(shù)葉，則， 是二部圖結(jié)點(diǎn)分類(lèi)，且中頂點(diǎn)的出度最少為2，則，可得與題中給的相矛盾。所以中至少有一片樹(shù)葉。3.9T是一棵樹(shù)，則T中任意兩個(gè)結(jié)點(diǎn)之間有且僅有一條路，所以T中任意兩點(diǎn)僅有唯一的簡(jiǎn)單通路，反之亦成立。3.10Kruskal算法可求得如下最小生成樹(shù):453454

24、33323.11證明:因?yàn)镚為連通圖，所以結(jié)點(diǎn)v的關(guān)聯(lián)便只有一條。又因?yàn)镚的任何一棵生成樹(shù)T必為G的生成子圖且連通，即T包含G的所有結(jié)點(diǎn)且連通，而v的關(guān)聯(lián)邊只有e一條邊，故e一定是任何一棵樹(shù)的枝。3.12證明：如果簡(jiǎn)單連通圖G無(wú)回路，則G本身就是生成樹(shù)。即G的任何一條邊都可以是某一生成樹(shù)的枝。若G中有回路，則去掉任意一條邊，則圖仍連通，若圖中仍有回路，重復(fù)上述過(guò)程知道圖中無(wú)回路為止。去掉的邊不一樣，則得到的生成樹(shù)不一樣，又因?yàn)槿ミ吺窃诨芈分腥我馊サ舻囊粭l邊，所以G中任一條邊都可以是某一生成樹(shù)的枝。3.13正則二叉樹(shù)為為完全二叉樹(shù)且所有葉結(jié)點(diǎn)在同一層。因?yàn)橥耆鏄?shù)的分支節(jié)點(diǎn)的出度都是2，則可知

25、除根節(jié)點(diǎn)外，其他每層上的結(jié)點(diǎn)個(gè)數(shù)都為偶數(shù)，故一棵正則二叉樹(shù)必有奇數(shù)個(gè)結(jié)點(diǎn)。3.14385166219100119813649643025161495143.156727401314179823111235573.160次迭代1次迭代2次迭代3次迭代4次迭代5次迭代6次迭代7次迭代結(jié)束到各結(jié)點(diǎn)的最短路徑為：3.17 3.183.19解：圖中有兩個(gè)奇點(diǎn)E,F。取一條連接EF的路EGF，添加重復(fù)邊（E，G）和（G，F(xiàn)），經(jīng)檢驗(yàn)可得滿(mǎn)足定理的條件，即為最優(yōu)方案,其最優(yōu)回路:DBACBEGEDFGFCD.3.20最鄰近算法：acedba 37 bdecab 37 cedbac 37 dbeacd 36最

26、短哈密頓回路為：dbeacd最鄰近插入法：aaacaaceaacdeaabcdea acbdea acdbea acdeba 其權(quán)值分別為：52，40，36，43最短哈密頓回路為：acdbea第五章 獨(dú)立集、支配集與匹配5.1證明：由G是二部圖可知，其子圖H也是二部圖，顯然二部圖的頂點(diǎn)劃分（X，Y）中的X，Y均是二部圖的獨(dú)立集，則有，其中是子圖H的頂點(diǎn)數(shù)，是圖H的最大獨(dú)立集中具有的點(diǎn)的數(shù)目。 反證法：若G不是二部圖，則G含有奇圈H，H是G的子圖，但這與已知條件矛盾，故G是二部圖。5.2證明：G是二部圖，則其子圖H也是二部圖，因?yàn)?，故?duì)子圖H有，則必有一個(gè)匹配關(guān)聯(lián)G中所有結(jié)點(diǎn)，故G有一個(gè)完美匹配

27、。G有一個(gè)完美匹配，則子圖H也有完美匹配，故該匹配關(guān)聯(lián)H的所有結(jié)點(diǎn)，所以。5.3(1)G中極小支配集為v1, v3, v2, v4, v5，支配數(shù)2。(2)G中極小點(diǎn)覆蓋集為v1, v3, v2, v4, v5，點(diǎn)覆蓋數(shù)2。(3)G中極大點(diǎn)獨(dú)立集為v1, v3, v2, v4, v5，點(diǎn)獨(dú)立數(shù)3。(4)G中極大匹配為a, c, a, f, b, d, b, f, e, c, e, d，匹配數(shù)2。(5)G中極小邊覆蓋集為a, b, f, a, e, c, b, e, d, d, c, e, d, f, b, c, f, a，邊覆蓋數(shù)3。5.4證明：G是二分圖，并且則，又，故。5.5（a）極小點(diǎn)覆

28、蓋a,c,e,g,b,c,d,e,gb,d,e,fb,c,d,f極大獨(dú)立集b,d,fa,fa,c,ga,e,g最小點(diǎn)覆蓋a,c,e,gb,d,e,fb,c,d,f最大獨(dú)立集b,d,fa,c,ga,e,g(b)極小點(diǎn)覆蓋b,c,e,fb,c,d,fb,c,d,ea,c,e,fa,c,d,ea,b,d,e極大獨(dú)立集a,da,ea,fb,db,fc,f最小點(diǎn)覆蓋b,c,e,fb,c,d,fb,c,d,ea,c,e,fa,c,d,ea,b,d,e最大獨(dú)立集a,da,ea,fb,db,fc,f5.65.7(1)(2) 5.8證明：設(shè)M為樹(shù)的一個(gè)完美匹配，則滿(mǎn)足：（1）T的所有點(diǎn)均為M飽和點(diǎn)，且與所有葉子

29、結(jié)點(diǎn)關(guān)聯(lián)的邊均在T的任意一個(gè)匹配里。（2）T的頂點(diǎn)數(shù)n=2|M|為偶數(shù)，而T的邊數(shù)m=2n-1=2|M|-1為奇數(shù)。反證：設(shè)和都是樹(shù)的完美匹配，并且他們是不同的，則，設(shè)導(dǎo)出子圖為H。由于和都是T的完美匹配，則H中定點(diǎn)的度均為2,所以H中存在圈，這與T是樹(shù)相矛盾。故樹(shù)至多有一個(gè)完美匹配。5.9（1）歸納法n=1時(shí)完美匹配數(shù)是1n=2時(shí)完美匹配數(shù)是3，滿(mǎn)足（2n-1）！設(shè)當(dāng)n=k時(shí)，完美匹配數(shù)是（2k-1）！，當(dāng)n=k+1時(shí)，即向中加入兩點(diǎn)u，v，則多出4k+1條邊，（1）取的一個(gè)完美匹配，則只加入邊uv有為的一個(gè)完美匹配，無(wú)妨設(shè)為中的邊（2）則去掉添加有另一個(gè)的完美匹配添加有另一個(gè)的完美匹配。（

30、3）對(duì)同樣的操作則共有2k種設(shè)法，算上共有2k+1種，（4）不同完美匹配有（2k-1）！每一種均可增加為2k+1，所以不同完美匹配有（2k+1）（2k-1）！=（2k+1）！種，得證。（2）對(duì)于有n！種完美匹配。5.10利用匈牙利算法可求得最大匹配5.11略5.125.13由Kuhn-Munkres算法可得。第六章 平面圖與著色6.1略6.2 略6.3由題意可得：n=6，m=（46）/2=12由歐拉公式n-m+r=2可得：r=8.6.4n-m+r=n-30+20=2所以n=12.6.5證明：反證法假設(shè)極大平面圖G是非聯(lián)通的，則它至少有兩個(gè)連通分支，在這兩個(gè)連通分支的外部邊界上各取一頂點(diǎn)，則這兩個(gè)頂點(diǎn)是不相鄰的，在這兩個(gè)頂點(diǎn)之間加一條邊，則所得的圖還是平面圖，這與G是極大平面圖相矛盾，所以極大平面圖一定是連通圖。6.6證明：用反證法，若分情況討論。（1），G中存在頂點(diǎn)，設(shè)與相鄰的頂點(diǎn)v，并設(shè)v除與相鄰?fù)膺€依次的