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

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