2016年 圖論及其應(yīng)用1-3章習(xí)題答案(電子科大)

1、習(xí)題1：4,5,11,12,17,184 證明 將圖1-28的兩圖頂點(diǎn)標(biāo)號為如下的(a)與(b)圖作映射f : f(vi)®ui (1£ i £ 10)容易證明，對"vivjÎE(a),有f(vivj)=uiujÎE(b) (1£ i £ 10, 1£j£ 10 )由圖的同構(gòu)定義知，圖1-28的兩個(gè)圖是同構(gòu)的。5.分析：四個(gè)頂點(diǎn)的簡單圖最少邊數(shù)為 0，最多邊數(shù)為 6，所以可按邊數(shù)進(jìn)行枚舉。11.證明 由于7個(gè)頂點(diǎn)的簡單圖的最大度不會超過6，因此序列(7,6,5,4,3,3,2)不是圖序列；(6,

2、6,5,4,3,3,1)是圖序列Û（5，4，3，2，2，0）是圖序列，然（5，4，2，2，0）不是圖序列，所以(6,6,5,4,3,3,1) 不是圖序列。12. 證明 只就連通圖證明即可。設(shè)V(G)=v1,v2,vn,對于G中的路v1v2vk,若vk與v1鄰接，則構(gòu)成一個(gè)圈。若vi1vi2vin是一條路，由于d³ 2，因此，對vin，存在點(diǎn)vik與之鄰接，則vik¼vinvik構(gòu)成一個(gè)圈 。 17. 證明 對,若u與v屬于G的不同連通分支，顯然u與v在中連通；若u與v屬于g的同一連通分支，設(shè)w為G的另一個(gè)連通分支中的一個(gè)頂點(diǎn)，則u與w，v與w分別在中連通

3、，因此，u與v在中連通。18.證明: 因?yàn)閑只能屬于G的某一個(gè)連通分支,所以只需考慮G是連通圖的情況. 若G e仍然連通,則(G) = 1 = (G e) < 2 = (G) + 1. 若G e不連通,則(G) = 1 < 2 = (G e) = (G) + 1.習(xí)題2: 1,9,161.證明 設(shè)P=v1v2vk是非平凡樹T中一條最長路，若d(v1)2則v1與vk在T中的鄰接點(diǎn)只能有一個(gè)，否則，若v1與除了P中頂點(diǎn)之外的其他頂點(diǎn)相連，則P可以繼續(xù)延長，這與P是最長路是相矛盾的。若v1與P上的某頂點(diǎn)相連，則就構(gòu)成了圈，這與數(shù)相矛盾，推出P不是最長路。即說明v1與vk是樹葉，則v1與v

4、k均是一度的。所以非平凡樹的最長路的起點(diǎn)和終點(diǎn)均是1度的。9.證明 由于G是連通非平凡的且每個(gè)頂點(diǎn)度數(shù)為偶數(shù)，所以G中至少存在圈C1,從G中去掉C1中的邊，得到G的生成子圖G1,若G1沒有邊，則G的邊集合能劃分為圈。否則，G1的每個(gè)度數(shù)均為偶數(shù)的連通圖，反復(fù)這樣抽取，E(G)最終劃分為若干圈。設(shè)C1是G的邊劃分中的一個(gè)圈。若G僅由此圈組成，則G顯然是閉跡。否則，由于G連通，所以，必然存有公共頂點(diǎn)。于是，C1C2是一條含有C1與C2的邊的跡，如此拼接下去，得到包含G的所有邊的一條閉跡.16.解：（1）不能，Kruskal算法得到的任何生成樹一定是最小生成樹。 （2）可以，步驟如下：步驟一：選擇邊

5、e1，是的盡可能??；步驟二：若已選定邊，則從選取，使為無圈圖，是滿足a的盡可能小的權(quán)；步驟三：當(dāng)步驟二不能繼續(xù)執(zhí)行時(shí)停止；習(xí)題3：1,3,7,12,131.證明充分性: e是G的割邊，故G-e至少含有兩個(gè)連通分支，設(shè)V1是其中一個(gè)連通分支的頂點(diǎn)集，V2是其余分支的頂點(diǎn)集，對，因?yàn)镚中的u,v不連通，而在G中u與v連通，所以e在每一條(u,v)路上，G中的(u,v)必含e。必要性：取，由假設(shè)G中所有(u,v)路均含有邊e，從而在G-e中不存在從u與到v的路，這表明G不連通，所以e是割邊。3. 證明（1）（2）： G是塊，任取G的一點(diǎn)u，一邊e，在e邊插入一點(diǎn)v，使得e成為兩條邊，由此得到新圖，顯

6、然的是階數(shù)大于3的塊，由定理，G中的u,v位于同一個(gè)圈上，于是中u與邊e都位于同一個(gè)圈上。（2）（3）: 無環(huán)，且任意一點(diǎn)和任意一條邊都位于同一個(gè)圈上，任取的點(diǎn)u，邊e，若在上，則三個(gè)不同點(diǎn)位于同一個(gè)閉路，即位于同一條路，如不在上，由定理，的兩點(diǎn)在同一個(gè)閉路上，在邊插入一個(gè)點(diǎn)v，由此得到新圖，顯然的是階數(shù)大于3的塊，則兩條邊的三個(gè)不同點(diǎn)在同一條路上。(3)(1):連通，若不是塊，則中存在著割點(diǎn)，劃分為不同的子集塊,無環(huán)，點(diǎn)在每一條的路上，則與已知矛盾，是塊。7.證明 v是單圖G的割點(diǎn)，則G-v有兩個(gè)連通分支?，F(xiàn)任取x,yV(G-v), 如果x,y不在G-v的同一分支中，令u是與x,y處于不同分支的點(diǎn)，那么，x,與y在G-v的補(bǔ)圖中連通。若x,y在G-v的同一分支中，則它們在G-v的補(bǔ)圖中鄰接。所以，若v是G的割點(diǎn)，則v不是補(bǔ)圖的割點(diǎn)。12. 解： 最小點(diǎn)割 6,8 最小邊割（6,5）