圖論(張先迪-李正良)課后習(xí)題答案(第一章)

習(xí)題一習(xí)題一 作者作者-寒江獨(dú)釣寒江獨(dú)釣 1.證明：在 n 階連通圖中 (1) 至少有 n-1 條邊； (2) 如果邊數(shù)大于 n-1，則至少有一條閉跡； (3) 如果恰有 n-1 條邊，則至少有一個(gè)奇度點(diǎn)。 證明: (1) 若 G 中沒有 1 度頂點(diǎn)，由握手定理： () 2( )21 v V G md vnmnmn 若 G 中有 1 度頂點(diǎn) u，對 G 的頂點(diǎn)數(shù)作數(shù)學(xué)歸納。 當(dāng) n=2 時(shí)，結(jié)論顯然；設(shè)結(jié)論對 n=k 時(shí)成立。 當(dāng) n=k+1 時(shí)，考慮 G-u,它仍然為連通圖，所以，邊數(shù)k-1.于是 G 的邊數(shù)k. (2) 考慮 G 中途徑： 121 : nn Wvvvv L 若 W 是路，則長為 n-1;但由于 G 的邊數(shù)大于 n-1,因此，存在 vi與 vj,它們相異，但鄰接。于 是： 1iiji vvvv L 為 G 中一閉途徑，于是 也就存在閉跡。 (3) 若不然，G 中頂點(diǎn)度數(shù)至少為 2，于是由握手定理： () 2( )21 v V G md vnmnmn 這與 G 中恰有 n-1 條邊矛盾！ 2.(1)2 1 2 2 1 2 1 (2)22 1 (3) 22 3.證明下面兩圖不同構(gòu)。 證明:u1的兩個(gè)鄰接點(diǎn)與 v1的兩個(gè)鄰接點(diǎn)狀況不同。所以， 兩圖不同構(gòu)。 4.證明下面兩圖同構(gòu)。 u1 v1 證明:作映射 f : vi ui (i=1,2.10) 容易證明，對vi v j E (a),有 f (v i vj,),ui,uj,E,(b) (1 i 10, 1j 10 ) 由圖的同構(gòu)定義知，圖(a)與(b)是同構(gòu)的。 5.指出 4 個(gè)頂點(diǎn)的非同構(gòu)的所有簡單圖。 分析：四個(gè)頂點(diǎn)的簡單圖最少邊數(shù)為 0，最多邊數(shù)為 6，所以 可按邊數(shù)進(jìn)行枚舉。 (a) v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 u1 u2 u3 u4 u5 u6 u7 u8 u9 u10 (b) 6.證明: 1)充分性:當(dāng)G是完全圖時(shí)，每個(gè)頂點(diǎn)的度數(shù)都是n 1,共有n個(gè)頂點(diǎn)，總的度數(shù)為n(n 1)， 因此總的邊數(shù)是(1) 2 =( 2 ). 2)必要性:因?yàn)镚是簡單圖,所以當(dāng)G是完全圖的時(shí)候每個(gè)頂點(diǎn)的度數(shù)才達(dá)到最大:n 1.若G不 是完全圖，則至少有一個(gè)頂點(diǎn)的度數(shù)小于n 1,這樣的話，總的度數(shù)就要小于 n(n 1)，因此總的邊數(shù)小于 ( 2)，矛盾。所以G是完全圖。 8. 與是簡單圖 G 的最大度與最小度，求證： 證明：由握手定理有： 所以有： 9.證明： 設(shè)|V1 | = 1,|V2 | = 2,1中點(diǎn)的度數(shù)之和為1,2中點(diǎn)的度數(shù)之和為2,的邊數(shù)為 m.有偶 圖的定義可知d1= = d2.而d1= k1,d2= 2.所以1= 2. 10.證明： 將每個(gè)人看成一個(gè)頂點(diǎn)，若其中有兩個(gè)人是朋友，則將這兩個(gè)人所代表的頂點(diǎn)連接起 來，這樣便得到了一個(gè)簡單圖。這個(gè)圖中每個(gè)頂點(diǎn)的度數(shù)就是這個(gè)頂點(diǎn)所代表的人的朋友 的數(shù)目。因?yàn)楹唵螆D中至少有兩個(gè)頂點(diǎn)的度數(shù)相同，所以這些人中至少有兩個(gè)人這這個(gè)人 群中的朋友數(shù)目是相同的。 12.證明：若2，則 G 中必然含有圈。 證明：只就連通圖證明即可！ 設(shè) W=v1v2.vk-1vk是 G 中的一條最長路。由于 2，所以 vk必然有相異于 vk-1的鄰接頂點(diǎn)。 又 W 是 G 中最長路,所以，這樣的鄰接點(diǎn)必然是 v1,v2,.,vk-2中之一。設(shè)該點(diǎn)為 vm，則 vmvm+1.v kvm為 G 中圈。 13.證明: 不妨設(shè)G是連通的（否則可考慮其某一個(gè)連通分支）.設(shè)L = 121 是 G 中最長的一條路。因?yàn)?2,所以V(G)中還有 1 個(gè)點(diǎn)與相鄰。因?yàn)長 2m n () ( )2 v V G nd vmn 2m n 是最長的路,所以這些點(diǎn)在1,2,1 中。又因?yàn)镚是簡單圖，所以這些點(diǎn) 不可能是1.設(shè)從1開始(1 i k 1 )是這些點(diǎn)中第一個(gè)與 相鄰的點(diǎn),則+1是G中的一個(gè)圈，其長度至少為 + 1. 14.G 的圍長圍長是指 G 中最短圈的長；若 G 沒有圈，則定義 G 的圍長為無窮大。 證明： （1） 圍長為 4 的 k 的正則圖至少有 2k 個(gè)頂點(diǎn)，且恰有 2k 個(gè)頂點(diǎn)的這樣的圖（在 同構(gòu)意義下）只有一個(gè)。 （2） 圍長為 5 的 k 正則圖至少有 k2+1 個(gè)頂點(diǎn)。 證明證明 (1) 設(shè) u,v 是 G 中兩相鄰頂點(diǎn)，則 S(u)S(v)=,否則，可推出 G 中的圍長為 3，與 已知矛盾。因此，G 中至少有 2（k-1）+2 個(gè)頂點(diǎn)，即有 2k 個(gè)頂點(diǎn)。把 S(u) v，S(v) u連為完全偶圖，則得到 2k 個(gè)頂點(diǎn)的圍長為 4 的圖，由作法知，這樣的圖是唯一的。 (2)設(shè)G是圍長為 5 的 k 正則圖,任取u V(G)記S= ():(,) = ( = 0,1,2,).則:S1中不同的頂點(diǎn)不相鄰;2中每個(gè)頂點(diǎn)有且只有一條邊與S1相 連.(若或不成立,則G的圍長不是 5).這樣的話G的頂點(diǎn)數(shù)至少為 | 0| + |1| + |2| = 1 + + ( 1) = 2+ 1. 15.證明: (1)G連通 由 m n n 1 知,G 中至少有一個(gè)閉跡,所以 G 中包含圈. G 不連通 設(shè)G的所有的連通分支為1,2,.的頂點(diǎn)數(shù)為,邊數(shù)為,(i = 1,2,k) 則至少有一個(gè)0,使得0 0.由可知0中包含圈,所以 G 中包含圈. (2) 只就 m=n+4 證明就行了。 設(shè) G 是滿足 m=n+4，但不包含兩個(gè)邊不相交的圈的圖族中頂點(diǎn)數(shù)最少的一個(gè)圖。可以 證明 G 具有如下兩個(gè)性質(zhì)： 1) G 的圍長 g5。事實(shí)上，若 G 的圍長4，則在 G 中除去一個(gè)長度4 的圈 C1的一條 邊，所得之圖記為 G,顯然，m(G) V(G)=V(G),由(1),G中存在圈 C2, 使 C1,C2的邊不相 交這與假定矛盾； 2） (G)3。事實(shí)上，若 d(v0)=2,設(shè) v0v1,v0v2E(G),作 G1=G-v0+v1v2;若 d(v0)1,則 G1為在 G 中除去 v0及其關(guān)聯(lián)的邊(d(v0)=0,任去 G 中一條邊)所得之圖。顯然， m(G1)=V(G1)+4,G1仍然不含兩個(gè)邊不重的圈之圖。但V(G1)V(G)，與假定矛盾。 由 2),n+4=m3n/2 n 8. 但另一方面，由 1),在 G 中存在一個(gè)圈 Cg，其上的頂點(diǎn)之間的 邊，除 Cg 之外，再無其它邊，以 S0表示 Cg 上的頂點(diǎn)集，故由 2),S0上每個(gè)頂點(diǎn)均有伸向 Cg 外的的邊。記與 S0距離為 1 的頂點(diǎn)集為 S1，則 S0的每一個(gè)頂點(diǎn)有伸向 S1的邊，反過 來，S1中的每個(gè)頂點(diǎn)僅有唯一的一邊與 S0相連，不然在 G 中則含有長不大于 g/2+2 的圈， 這與 G 的圍長為 g 相矛盾，故S0 S1,于是有：nS0+ S1g+g10,但這與 n8 矛盾。所 以，假定條件下的 G 不存在。 18.證明: 因?yàn)閑只能屬于G的某一個(gè)連通分支,所以只需考慮G是連通圖的情況. 若G e仍然連通,則(G) = 1 = (G e) 2 = (G) + 1. 若G e不連通,則(G) = 1 2 = (G e) = (G) + 1. 19.證明: 設(shè)1是 G v 的任一個(gè)連通分支,則在 G 中 v 通過偶數(shù)條天與1相連,否則1 中有奇數(shù)個(gè)奇頂點(diǎn).所以 v 至少通過兩條邊與1相連,因此 (G v) d(v)/2 20證明: (1)G不連通的時(shí)候,設(shè) G中的兩個(gè)連通分支1,G2。則在 中, 1中的每個(gè)頂點(diǎn)與G2 中的每個(gè)頂點(diǎn)都相鄰，于是G的同一個(gè)連通分支中的頂點(diǎn)在 中的距離為 2 或 0，G中不同的連通分支中的頂點(diǎn)在 中的距離都為 1。所以d( ) 3.因此u不同時(shí)和1,2相鄰，v也不能同時(shí)與1,2相鄰。 所以在中,d(u,v) = 2. 結(jié)合可知d( ) 2.不妨假設(shè) u 和 v1,v2vk鄰接。 為了保證 u 到各點(diǎn)距離不超過 2,vk+1,.vn-2這些頂點(diǎn)的每一個(gè)必須和前面 v1,v2,vk中某點(diǎn)鄰 接，這樣，圖中至少又有 n-2 條邊。總共至少有 2n-4 條邊。 22.證明: 因