圖及聯(lián)圖的點分割數(shù)的計數(shù)研究

許冰

（福建農(nóng)林大學 計算機與信息學院，福建 福州，350002）

圖及聯(lián)圖的點分割數(shù)的計數(shù)研究

許冰

（福建農(nóng)林大學 計算機與信息學院，福建 福州，350002）

圖劃分具有廣泛的應用,主要應用于VLSI(大規(guī)模集成電路)設計,并行計算,數(shù)據(jù)挖掘和圖像分割等領域,因此得到了國內(nèi)外學者的普遍關注和大量研究。由于圖劃分是NP-完全問題,因此本文在一般圖劃分問題基礎上提出了特殊點割集及點分割數(shù)的概念，主要應用圖的連通性原理分析，給出路、圈、扇圖、輪圖及完全二部圖及聯(lián)圖Pn,Cn,F1n,Wn,Km,n等的點分割數(shù)，并分析討論了完全圖Kn刪除一個獨立邊集后，其點分割數(shù)的變化情況。

圖點分割數(shù)；特殊點割集；獨立邊集

1 預備知識

由于在生物基因組合排列及超大規(guī)模集成電路 (VLSI)設計中，經(jīng)常遇到圖的劃分問題，常用的方法是將網(wǎng)絡圖分割為兩個子集 ,使得不同子集頂點之間的相連邊數(shù)盡可能少，轉(zhuǎn)化為圖論問題此即圖的二等分問題（Bisection）。

同時圖劃分問題也是經(jīng)典的完全問題，通常很難在有限時間內(nèi)找到最優(yōu)解。盡管其實難解問題，從世紀年代至今，國內(nèi)外研究者不斷對其進行深入研究，提出了許多性能較好的圖劃分算法?，F(xiàn)主要有年R.Leland提出的譜方法，年S.Ranka提出的空間填充曲線的幾何方法，年S.Dutt提出的啟發(fā)式方法以及年P.Chardaire提出的種群智能優(yōu)化算法[1]等，對圖劃分問題給出了一些解決方案。

因為作者的基金項目涉及圖論設計在生物信息學中的應用，所以重點研究了圖的劃分問題，尤其需要討論研究滿足某種條件下的圖的劃分問題，由此我們在一般圖劃分的點割集的基礎之上，提出了特殊點割集及點分割數(shù)的概念，研究滿足該種條件下的圖的點分割數(shù)的計數(shù)問題。

定義1 G是一個連通圖，我們稱圖G的點集VG的一個子集C為圖G的一個特殊點割集，若滿足：

(1)同時存在點集V的另外兩個非空子集A,B，使得{A,B，C}是點集VG的一個劃分;

(2)A中任一點都不與B中任一點相鄰，

(3)max{A，B }≤n/2。

若圖G存在特殊點割集，我們就稱圖G是可分離的，或稱圖G為可分離圖。另外把圖G的最小特殊點割集所含頂點個數(shù)稱為圖的點分割數(shù)，記為vsn（G）。顯而易見，對于任意一條路Pn（n≥3）,都有vsn（Pn）=1。

另外，由定義1可得，設G是一個連通圖，并且有Φ≠C?VG，若C是G的一個特殊點割集，則可以得到以下兩點：

（1)G-C是非平凡圖，而且不是連通圖;

(2)G-C任一連通分支所含點數(shù)至多為n/2。

引理1若是可分離圖G的一個連通的生成子圖，則H也是可分離圖，并且有vsn（H）≤vsn（G）。

另外，我們稱圖G是可平分圖，如果圖G存在兩個非空點子集A與B，滿足以下3個條件：

（1）{A,B}是圖的一個劃分；

（2）A ≤nG/2 并且B ≤nG/2；

（3）A中任何一點都不予B中任何一點相鄰。

2 一些特殊圖的點分割數(shù)

顯而易見，對任意一條路Pn（n≥3）,vsn（Pn）=1。另外，對于圈圖、扇圖[2]、輪圖、完全二部圖等，可得以下結(jié)論：

定理1對任意一個圈，Cn（n≥3）,都有vsn（Cn）=2。

證明 ：首先設圈圖 Cn=x1x2Lxnx1，令 C={x1，x[n/2]+1}，則 Cn-C只包含兩個連通分支：路 x2x3Lx[n/2]和路 x[n/2]+2x[n/2]+3Lxn。取A={x2,x3,L,x[n/2]}和B={x[n/2]+2,x[n/2]+3,L,xn/2}，顯然A與B都為非空點子集，{A，B，C}為的Cn一個劃分，且有A ≤[n/2]-1≤n/2和B =n-[n/2]-1≤[n/2]-1≤n/2，另外A與B之間無邊相連，所以C={x1，x[n/2]+1}是圈圖Cn的一個特殊點割集，可得vsn（Cn）≤2。其次，我們易推出圈圖Cn的任一單點點子集都不可能是的Cn一個特殊點割集，所以vsn（Cn）=2。

定理2對任意一個扇圖F1,n（n≥3），vsn（F1,n)=2。

證明：設Fn（n≥3）為一個扇圖，其有點集V={x1,x2,L,x[n/2]}和邊集E={xi,xi+1∶1≤i≤n-1}∪{zxj∶1≤j≤n}，現(xiàn)在令C={x[n/2]，z}，取A={x1,x2,L,x[n/2]-1}以及B={x[n/2]+1,x[n/2]+2,L,xn}。顯然A，B,C兩兩不交且有A∪B∪C=V，A ≤[n/2]-1≤（n+1）/2和B ≤n-[n/2]≤(n+1)/2，另外A和B之間無邊相連，所以C={x[n/2]，z}為Cn的一個特殊點割集，因此vsn（F1,n)≤2。又因為Cn+1為F1,n（n≥3）的一個連通生成子圖，所以根據(jù)引理1，有vsn（F1,n)≥2，所以vsn（F1,n)=2。

定理3對任意一個輪圖Wn（n≥4），vsn（Wn)=3。

證明：設Wn（n≥4）為一個輪圖，其有點集V={x1,x2,L,x[n/2]}和邊集E={x1,x2,x2,x3，L,xn-1，xn，xn，x1}∪{zxj∶1≤j≤n}?，F(xiàn)在令C={x1，x[n/2]+1，z}，取A={x2,x3,L,x[n/2]}以及B={x[n/2]+2,x[n/2]+3,L,xn}。顯然A，B,C兩兩不交且有A∪B∪C=V，A ≤[n/2]-1≤n/2-1＜(n+1)/2和B ≤n-[n/2]-1≤(n+1)/2-1＜(n+1)/2，另外A 和B之間無邊相連，所以C={x1，x[n/2]+1，z}為Cn的一個特殊點割集，因此vsn（Wn)≤3。又因為Cn+1為Wn（n≥4）的一個連通生成子圖，所以根據(jù)引理1，有2≤vsn（Wn)≤3。因為顯然vsn（Wn)≠1，現(xiàn)在證明vsn（Wn)≠2。假設D（D =2）為輪圖Wn（n≥4）的點集的子集，所以要么D={z，xi}（1≤i≤n），要么D= {xi，xj}（i≠j），無論D是上面兩種中的何種情況，都有Wn-D是連通圖，所以D（D =2）不會是輪圖Wn（n≥4）的一個特殊點割集，所以vsn（Wn)=3。

定理4對任意一個完全二部圖Km，n（m+n≥3)，vsn(Km，n)=min{m,n}。

證明：設Km，n（m+n≥3)為一個完全二部圖，其有點集V={x1,x2,L,xm,y1,y2,L,yn}和邊集E={xi,yj∶1≤i≤m, 1≤j≤n}。為了不失一般性，假設m≤n?，F(xiàn)在令C={x1，x2，L,xm}，A={y1,y2,L,y[n/2]}以及B={y[n/2]+1,y[n/2]+2,L, yn]}，顯然A，B,C滿足定義1的3個條件，所以C={x1，x2，L,xm}是Km，n（m+n≥3)的一個特殊點割集，因此vsn(Km，n)≤m。另外還要證vsn(Km，n)≥m，假設D?V（D =p＜m），因為p＜m≤n，所以一定存在點x∈{x1,x2,L,xm}D同時有點y∈{y1,y2,L,ym}D，所以Km，n-D是一個連通圖，可得任意的D?V（D =p＜m）都不會是Km，n（m+n≥3)的一個特殊點割集，所以vsn(Km，n)=min{m,n}。

3 某些聯(lián)圖的點分割數(shù)

這一節(jié)將就兩個圖的一種二元運算圖的聯(lián)圖[3]運算下，尋找某些圖的聯(lián)圖的點分割數(shù)。所謂兩圖的聯(lián)圖，即圖G1與G2的聯(lián)圖我們記為G=G1+G2，滿足：V（G）=V（G1）∪V（G2）且有E（G）=E（G1）∪E（G2）∪{uv|u∈V（G1）同時v∈V（G2）}。

引理2G和H是兩個圖，并且nG≥nH，則有vsn（G+H）≥nH。

證明：令D是G+H的點集VG+H的一個子集，且有D ＜nH。因為D ＜nH≤nG，顯然（G+H）-D是連通圖，可得D（D ＜nH）不可能是圖G+H的一個特殊點割集，所以vsn（G+H）≥nH。

引理3若圖G是一個可平分圖，圖H為一任意圖，則有

1)圖G+H是可分離的；

2)min{nG，nH}≤vsn（G+H）≤nH；

3)若nG≥nH，則vsn（G+H）=nH。

證明：因為圖G是一個可平分圖，所以存在圖G的一個劃分{A，B}，滿足定義可平分圖的3個條件，尤其是A ≤nG/2 并且B ≤nG/2 ，顯而易見{A，VH，B}是圖的一個劃分，滿足定義1的3個條件，因此VH是圖G+H的一個特殊點割集，所以圖G+H是可分離的，可得vsn（G+H）≤nH。另外完全二部圖KnGnH是圖G+H的一個連通生成子圖，根據(jù)引理1和定理4得vsn（G+H）≥min{nG，nH}，所以min{nG，nH}≤vsn（G+H）≤nH。當nG≥nH時，由（2）可得vsn（G+H）=nH。

引理4若圖G是一個可平分圖，則vsn（G+Kn）=n。

證明：假設nG≥n，根據(jù)引理3易得vsn（G+Kn）=n。若假設nG≥n，引理3有vsn（G+Kn）≤n。設D≠?且D?VG+Kn同時還滿足D ＜n，若D=VG，則（G+Kn）-D=Kn；若D?VKn，則（G+Kn）-D=G+（Kn-D）；若DIVG≠?且DIVKn≠?，則（G+Kn）-D=（G-D）+（Kn-D）。無論上面是3種情況中的何種情況，都有（G+Kn）-D是連通的，可知D（D ＜n）不可能是圖G+Kn的一個特殊點割集，所以vsn（G+Kn）=n。

引理3和引理4都考慮的是可平分圖和另一圖的聯(lián)圖的點分割數(shù)，下面兩個引理我們將考慮可分離圖與另一圖的聯(lián)圖的點分割數(shù)問題。

引理5若圖G是一個可分離圖，圖H為一任意圖，則有

1)圖G+H是可分離的；

2)min{nG，nH}≤vsn（G+H）≤nH+vsn（G）。

證明：令C為圖G中取到C =vsn（G）的一個特殊點割集，則存在圖G的一個劃分{A，B,C}滿足定義1中的3個條件。顯然{A，B,C∪VH}也是VG+H的一個劃分，且C∪VH是圖G+H的一個特殊點割集，因此vsn（G+H）≤nH+vsn（G）。因為完全二部圖KnGnH是圖G+H的一個連通生成子圖，所以根據(jù)引理1和定理4可得出min{nG，nH}≤vsn（G+H），因此min{nG，nH}≤vsn（G+H）。

引理6若圖G是一個可分離偶圖，則vsn（G+K1）=1+vsnG。

證明：根據(jù)引理5有vsn（G+K1）≤1+vsnG，反證法證明vsn（G+K1）＞1+vsnG。假設圖G+K1存在一個特殊點D割集滿足D ≤vsn(G)，考慮以下兩種情況：

若D?VG或D=VK1,則 （G+K1）-D是一個連通圖；若D∩VG≠?且D∩VK1≠?時，則有1≤D∩VG≤vsnG，因此D∩VG不是圖G的一個特殊點割集。由于假設D是圖G+K1的一個特殊點割集，所以存在VG+K1的非空子集A,B，使得滿足定義1的3個條件，所以A ≤(nG+1)/2且有B≤(nG+1)/2。因為A∪B∪（DVK1）=（A∪B∪D）VK1=VG+K1VK1=VG，所以{A,B,DVK1}是圖G的一個劃分，但D∩VG不是圖G的一個特殊點割集，因為D∩VG=DVK1，所以A ＞nG/2或B ＞nG/2。不失一般性，我們假設A ＞nG/2，則nG/2＜A ≤(nG+1)/2，所以只能有A =(nG+1)/2，因此nG為奇數(shù)，與圖G為偶圖矛盾，所以vsn（G+K1）＞vsn（G）m，可得結(jié)論vsn（G+K1）=1+vsnG。

定理5若圖G=，m≥3且對任意i的都有ni≥2，則vsn(G)max{ni∶1≤i≤m}。

證明：假設n1≤n2≤L≤nm，因為nm是一個可平分圖，因此存在VKˉn的兩個非空子集A和B，使得mA ≤[nm]/2及B ≤[nm]/2，顯然A ≤nm/2≤（）/2以及B ≤（nm+1）/2≤/2，所以C=是圖G的一個特殊點割集，我們有vsn（G）≤現(xiàn)在我們假設D是圖G滿足D≤的一個非空點子集，則有D +nm＜ni，即nm+1＜ni-D ，所以G-D是連通的，則D（D＜）不是圖G的一個特殊點割集，所以vsn(G)=ni-max{ni∶1≤i≤m}。

推論1若圖Gn=K2,2,L,2(n≥2)是一個完全n部圖，則vsn(Gn)=2(n-1)。

證明：令Gn=Kmi(mi=2)，若n=2，則Gn=G4，可得vsn(Gn)=vsn(Cn)=2=2(n-1)。若n≥3，則由定理2i可得vsn(Gn)=2(n-1)。

現(xiàn)在考慮一個完全圖刪除一個獨立邊集甚至刪除一個獨立邊集后，對其點分割數(shù)影響情形。

定理6（1）若e是完全圖Kn(n≥3)的任意一條邊，則Kn-e是可分離圖，且vsn(Kn-e)=n-2。（2）若是S完全圖Kn(n≥3)的一個非空獨立邊集，則有vsn(Kn-S)=n-2。

證明：（1）令G=Kn-e且e=ab，則C=VG{a,b}是圖G的一個特殊點割集，所以vsn(Gn)≤n-2。若，n=3則有vsn(Gn)=1≤n-2；若n≥4，令?≠D?VG且有D ＜n-2，因為CD≠?,所以G-D是連通的，可知D不會是圖G的一個特殊點割集，所以vsn(Kn-e)=n-2。

（2）因為Kn-S是Kn-e(e為Kn的某些邊）的一個連通生成子圖，根據(jù)引理1和（1）中證明可得vsn(Kn-S）≤vsn(Kn-e≤n-2)?，F(xiàn)在來證明vsn(Kn-S）≥n-2，若n為偶數(shù)，則Gn=K2,2,L,2是Kn-S的一個連通生成子圖，根據(jù)引理1和推論1可得vsn(Kn-S）≥vsn(Gn)=n-2；若n為奇數(shù)，則Gn=[(n-1)/2]2+ K1是Kn-S的一個連通生成子圖，根據(jù)引理1和引理6可得vsn(Kn-S）≥vsn(Gn)=1+vsn([(n-1)/2]Kˉ2)= 1+2[(n-1)/2-1]=n-2，所以無論何種情況，都有vsn(Kn-S）=n-2。

4 總結(jié)

通過對圖特殊點割集的分析，得到路、圈、扇圖、輪圖及完全二部圖的點分割數(shù)為vsn(Pn)=1、vsnffffedffffec

(Cn)=2、vsn(F1,n)=2、vsn(Wn)=3及vsn(Km,n)=min{m,n}。同時還得到聯(lián)圖的點分割數(shù)為vsn（)i =2(n-1)，并證明得知對于完全圖Kn(n≥3)的任意一個非空獨立邊集S，都滿足vsn(Kn-S）=n-2，即完全圖Kn(n≥3)刪除任意一個獨立邊集后，對其點分割數(shù)都只比完全圖頂點個數(shù)n減少兩個，不會隨獨立邊集的不同而產(chǎn)生變化。

當然，本文還有值得深入研究發(fā)展之處，若能對特殊點割集定義中第3個條件max{A,B} ≤n/2進行擴展，討論在max{A,B }≤n/k（?k∈N+）條件下的點分割數(shù)，則將會有更廣泛的應用空間，這也是將要繼續(xù)努力的方向。

［1］LIPPONEN L．Exploring foundations for computer—supported collaborative learning[A]//In Gerry Stahl.Ed．Computer Support Collaborative Learning：Foundations for a CSCL Community．Proceedings of CSCL 2002．HillsdaIe，NewJersey：Lawrence Erlbaum Associatesjnc．，2002：72．8 1．

［2］張園萍，強會英，孫亮萍．星扇輪聯(lián)圖的鄰點可約邊染色［J］．數(shù)學的實踐與認識，2012，42（13）：207-213．

［3］周志東，黃元秋，彭小多，等．一個小圖和路與圈的聯(lián)圖的交叉數(shù)［J］．系統(tǒng)科學與數(shù)學，2013，33（2）：206-216．

(責任編輯：朱聯(lián)九）

On Problem for Vertex Separable Numbers of Graph and Joint Graph

XU Bing
(College of Computer and Information,Fujian Agriculture and Forestry University,Fuzhou 350002,China)

Graph partitioning has extensive application in the fields of VLSI design,parallel computing,data mining and image segmentation,etc.which attracts the researchers at home and abroad.The graph partitioning problem is NP-complete,so the definition of special separator similar to the definitions of bisection and the vertex separator number is introduced.The vertex separable numbers of some special graphs,the vertex separable numbers of some special graphs,such asPn,Cn,F1n,Wn,Km,netc.are characterized and the influence of the vertex separable number resulting from deletion an influent edge set of Knis analyzed in this paper.

griph vertex separable number；special separator；influent edge set

O157．6

A< class="emphasis_bold">文章編號：1

1673-4343（2014）04-0028-04

10．14098／j．cn35－1288／z．2014．04．006

2014-06-08

福建省農(nóng)林大學校青年基金項目（2011xjj26）

許冰，男，福建長樂人，講師。研究方向：數(shù)據(jù)挖掘。