喬曉云

(山西大學(xué)商務(wù)學(xué)院，山西 太原 030031)

0 引言

1 預(yù)備知識(shí)

定義1[6]二部圖是指一個(gè)圖，它的頂點(diǎn)集可以分解為兩個(gè)非空子集X和Y,使得每條邊都有一個(gè)端點(diǎn)在X中，另一個(gè)端點(diǎn)在Y中.完全二部圖是指二部圖中X的每個(gè)頂點(diǎn)都與Y的每個(gè)頂點(diǎn)相連.若|X|=m,|Y|=n,則這樣的圖記為Km,n.

2 主要結(jié)論

定理：設(shè)G=Km,n(1≤m≤n)為完全二部圖，2≤k≤m+n,則

證明 設(shè)G=Km,n(1≤m≤n)為完全二部圖，V(Km,n)=U∪W,其中U={u1,u2,…,um},W={w1,w2,…,wn}.

(H1)當(dāng)2≤k≤m時(shí)，對(duì)于?S?V(G),|S|=k,則有以下三種情況S∩U=φ或者S∩W=φ或者S∩U≠φ,S∩W≠φ.

①對(duì)于S∩U=φ,則S?W.不失一般性，令S={w1,w2,…,wk},E′={u1w1,u1w2,…,u1wk},則G[E′]是包含S的Steiner樹，則d(S)≤k.另一方面，由于G=Km,n是完全二部圖，則包含S的任何樹至少有k條邊，即d(S)≥k.所以d(S)=k.

②對(duì)于S∩W=φ,同理可得d(S)=k.

③對(duì)于S∩U≠φ,S∩W≠φ,不失一般性，令S={u1,u2,…,ut,w1,w2,…,wk-t},E′={u1w1,w1u2,w1u3…,w1ut,u1wt,…,u1wk-t},則G[E′]是包含S的Steiner樹，則d(S)≤k-1.另一方面，|S|=k,則連接S的任何樹至少有k-1條邊，即d(S)≥k-1.所以d(S)=k-1

由定義得

(H2)當(dāng)m≤k≤n時(shí)，對(duì)于?S?V(G),|S|=k,則有以下兩種情況S∩U=φ或者或者S∩U≠φ,S∩W≠φ.根據(jù)(H1)的情況①③同理可得S∩U=φ時(shí)，d(S)=k.S∩U≠φ,S∩W≠φ時(shí)，d(S)=k-1.

由定義得

(H3)當(dāng)n≤k≤m+n時(shí)，對(duì)于?S?V(G),|S|=k,則S∩U≠φ,S∩W≠φ.根據(jù)(H1)的情況③同理可得.S∩U≠φ,S∩W≠φ時(shí)，d(S)=k-1.

由定義得

綜上所述，定理得證.