------------------------------------------------------------------------圖論及應用第一章完整作業習題11.證明在n階連通圖中至少有n-1條邊。如果邊數大于n-1，則至少有一條閉通道。如恰有n-1條邊，則至少有一個奇度點。證明(1)若對vV(G),有d(v)2,則：2m=d(v)2nmnn-1,矛盾！若G中有1度頂點，對頂點數n作數學歸納。當n=2時，G顯然至少有一條邊，結論成立。設當n=k時，結論成立，當n=k+1時，設d(v)=1，則G-v是k階連通圖，因此至少有k-1條邊，所以G至少有k條邊。(2)考慮v1v2vn的途徑，若該途徑是一條路，則長為n-1,但圖G的邊數大于n-1,因此存在vi,vj,使得viadgvj,這樣，vivi+1vj并上vivj構成一條閉通道；若該途徑是一條非路，易知，圖G有閉通道。(3)若不然，對vV(G),有d(v)2,則：2m=d(v)2nmnn-1,與已知矛盾！設G是n階完全圖，試問有多少條閉通道？包含G中某邊e的閉通道有多少？任意兩點間有多少條路？答(1)(n-2)!(2)(n-1)!/2(3)1+(n-2)+(n-2)(n-3)+(n-2)(n-3)(n-4)+…+(n-2)…1.證明圖1-27中的兩圖不同構：圖1-27圖1-27證明容易觀察出兩圖中的點與邊的鄰接關系各不相同，因此，兩圖不同構。證明圖1-28中的兩圖是同構的圖1-28圖1-28證明將圖1-28的兩圖頂點標號為如下的(a)與(b)圖作映射f:f(vi)ui(1i10)容易證明，對vivjE((a)),有f(vivj)uiujE((b))(1i10,1j10)由圖的同構定義知，圖1-27的兩個圖是同構的。證明：四個頂點的非同構簡單圖有11個。證明m=0123456由于四個頂點的簡單圖至多6條邊，因此上表已經窮舉了所有情形，由上表知：四個頂點的非同構簡單圖有11個。設G是具有m條邊的n階簡單圖。證明：m=當且僅當G是完全圖。證明必要性若G為非完全圖，則vV(G),有d(v)n-1d(v)n(n-1)2mn(n-1)mn(n-1)/2=,與已知矛盾！充分性若G為完全圖，則2m=d(v)=n(n-1)m=。證明：（1）m(Kl,n)=ln，（2）若G是具有m條邊的n階簡單偶圖，則m。證明(1)Kl,n的總度數為2ln,所以，m(Kl,n)=ln。(2)設G的兩個頂點子集所含頂點數分別為n1與n2,G的邊數為m,可建立如下的二次規劃：m=n1n2s.tn1+n2=nn11,n21當n為偶數時，n1=n2=n/2時，m取最大值：m=n2/4當n為奇數時，取n1=(n+1)/2,n2=(n-1)/2時，m取最大值：m=(n2-1)/4所以，m。設△和δ是簡單圖G的最大度和最小度，則δ≤2m/n≤△。證明證明：若k正則偶圖具有二分類V=V1∪V2，則|V1|=|V2|。證明由于G為k正則偶圖，所以，kV1=m=kV2V1=V2。證明：由兩人或更多個人組成的人群中，總有兩人在該人群中恰好有相同的朋友數。證明將人用圖的頂點表示，圖的兩頂點鄰接當且僅當人群中的兩人相認識，于是，問題轉化為：證明在任意一個簡單圖中必有一對度數相等的頂點。若圖G為連通單圖，則對vV(G),有1d(v)n-1,因此，n個頂點中必存在兩個頂點，其度數相同；若G為非連通圖，設G1為階數n1的連通分支，則vV(G1),有1d(v)n1-1，于是在G1中必存在兩個頂點，其度數相同。證明：序列(7,6,5,4,3,3,2)和(6,6,5,4,3,3,1)不是圖序列。證明由于7個頂點的簡單圖的最大度不會超過6，因此序列(7,6,5,4,3,3,2)不是圖序列；(6,6,5,4,3,3,1)是圖序列（5，4，3，2，2，0）是圖序列，然（5，4，3，2，2，0）不是圖序列，所以(6,6,5,4,3,3,1)不是圖序列。證明：若δ≥2，則G包含圈。證明只就連通圖證明即可。設V(G)=｛v1,v2,…,vn｝,對于G中的路v1v2…vk,若vk與v1鄰接，則構成一個圈。若vi1vi2…vin是一條路，由于2，因此，對vin，存在點vik與之鄰接，則vikvinvik構成一個圈。證明：若G是簡單圖且δ≥2，則G包含長至少是δ+1的圈。證明設v0v1…vk為G中一條最長路，則v0的鄰接頂點一定在該路上，否則，與假設矛盾。現取與v0相鄰的腳標最大者，記為l，則l,于是得圈v0v1v2vlv0,該圈長為l+1，顯然不小于δ+1。`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)對uV(G),設u的鄰接頂點為u1,u2,uk,由于G的圍長為5，所以，u1,u2,uk互不鄰接。又設ui的鄰接頂點為ui1,ui2,uik-1,(i=1,2,…,k),顯然，S(ui)S(uj)=u(ij),否則，G中有長為4的圈，所以，G的頂點數至少有k2+1個。對具有m條邊的階n圖G，證明：（1）若m≥n，則G包含圈；（2）若m≥n+4，則G包含兩個邊不重的圈。證明（1）若G含有環或平行邊，則G有圈。假定G為n階簡單圖。若G中頂點度大于等于2，則G中有圈。設G中有一度頂點，去掉該頂點和其關聯的邊得圖G1,由條件，顯然有m(G1)V(G1),若G1中有一度頂點，去掉該頂點和其關聯的邊得圖G2,有m(G2)V(G2),，如此進行下去，該過程不可能進行到n=1或n=2的情形，否則，不滿足m≥n所以，過程進行到Gm,Gm是度數2的圖，它含有圈。(2)只就m=n+4證明就行了。設G是滿足m=n+4，但不包含兩個邊不相交的圈的圖族中頂點數最少的一個圖。可以證明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及其關聯的邊(d(v0)=0,任去G中一條邊)所得之圖。顯然，m(G1)=V(G1)+4,G1仍然不含兩個邊不重的圈之圖。但V(G1)V(G)，與假定矛盾。由2),n+4=m3n/2n8.但另一方面，由1),在G中存在一個圈Cg，其上的頂點之間的邊，除Cg之外，再無其它邊，以S0表示Cg上的頂點集，故由2),S0上每個頂點均有伸向Cg外的的邊。記與S0距離為1的頂點集為S1，則S0的每一個頂點有伸向S1的邊，反過來，S1中的每個頂點僅有唯一的一邊與S0相連，不然在G中則含有長不大于g/2+2的圈，這與G的圍長為g相矛盾，故S0S1,于是有：nS0+S1g+g10,但這與n8矛盾。所以，假定條件下的G不存在。在圖1-13的賦權圖中，找出a到所有其它頂點的距離。vv11v463429a8v22v56b7242v3v6圖1-139解1.A1={a}，t(a)=0，T1=Φ2.3.m1=1,a2=v3,t(v3)=t(a)+l(av3)=1(最小)，T2={av3}2.A2={a,v3},3.m2=1,a3=v1,t(v1)=t(a)+l(av1)=2(最小)，T3={av3,av1}2.A3={a,v3,v1},3.m3=3,a4=v4,t(v4)=t(v1)+l(v1v4)=3(最小)，T4={av3,av1,v1v4}2.A4={a,v3,v1,v4}，b1(4)=v2，b2(4)=v2，b3(4)=v2,b4(4)=v53.m4=4,a5=v5,t(v5)=t(v4)+l(v4v5)=6(最小)，T5={av3,av1,v1v4,v4v5}2.A5={a,v3,v1,v4,v5}，b1(5)=v2，b2(5)=v2，b3(5)=v2,b4(5)=v2,b5(5)=v23.m5=4,t(v2)=t(v4)+l(v4v2)=7(最小)，T6={av3,av1,v1v4,v4v5,v4v2}2.A6={a,v3,v1,v4,v5,v2},b2(6)=v6,b4(6)=b，b5(6)=v6，b6(6)=v63.m6=6,a7=v6,t(v6)=t(v2)+l(v2v6)=9(最小)，T7={av3,av1,v1v4,v4v5,v4v2,v2v6}2.A7={a,v3,v1,v4,v5,v2,v6},b4(7)=b，b5(7)=b，b7(7)=b3.m7=7,a8=b,t(b)=t(v6)+l(v6b)=11(最小)，T8={av3,av1,v1v4,v4v5,v4v2,v2v6,v6b}于是知a與b的距離d(a,b)=t(b)=11由T8導出的樹中a到b路就是最短路。證明：若G不連通，則連通。證明對,若u與v屬于G的不同連通分支，顯然u與v在中連通；若u與v屬于g的同一連通分支，設w為G的另一個連通分支中的一個頂點，則u與w，v與w分別在中連通，因此，u與v在中連通。證明：若e∈E(G)，則ω(G)≤ω(G-e)≤ω(G)+1。證明若e為G之割邊，則ω(G-e)=ω(G)+1，若e為G之非割邊，則ω(G-e)=ω(G)，所以，若e∈E(G)，則ω(G)≤ω(G-e)≤ω(G)+1。證明：若G連通且G的每個頂點的度均為偶數，則對于任意的v∈V(G)，ω(G-v)≤d(v)/2成立。證明設C為ω(G-v)的一連通分支，則在G中，v有偶數條邊伸向C，若不然，C中奇度點個數為奇數。因此，v至少有兩條邊伸向C，有ω(G-v)≤d(v)/2成立。證明：若G的直徑大于3，則的直徑小于3。證明，若uvE(G)uvE()。若uvE(G)，則uvE()。分兩種情況：(1)若在V(G)中任意頂點至少和u,v之一相連，在這種情況下，對G中任意兩個頂點x,y，有，矛盾。(2)V(G)中存在一點w,使得uw,wvE(G),則uw,wvE()，此時，。所以，的直徑小于3。21．設G是具有m條邊的n階簡單圖，證明：若G的直徑為2且△=n-2，則m≥2n-4。證明在G中，設d(v)=△=n-2,與v鄰接的頂點設為：v1,v2,…,vn-2,剩下的一個頂點為u,u與v不能鄰接。如下圖所示。