許冰

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

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

許冰

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

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

圖點(diǎn)分割數(shù)；特殊點(diǎn)割集；獨(dú)立邊集

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

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

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

因?yàn)樽髡叩幕痦?xiàng)目涉及圖論設(shè)計(jì)在生物信息學(xué)中的應(yīng)用，所以重點(diǎn)研究了圖的劃分問(wèn)題，尤其需要討論研究滿足某種條件下的圖的劃分問(wèn)題，由此我們?cè)谝话銏D劃分的點(diǎn)割集的基礎(chǔ)之上，提出了特殊點(diǎn)割集及點(diǎn)分割數(shù)的概念，研究滿足該種條件下的圖的點(diǎn)分割數(shù)的計(jì)數(shù)問(wèn)題。

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

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

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

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

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

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

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

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

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

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

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

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

（3）A中任何一點(diǎn)都不予B中任何一點(diǎn)相鄰。

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

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

定理1對(duì)任意一個(gè)圈，Cn（n≥3）,都有vsn（Cn）=2。

證明 ：首先設(shè)圈圖 Cn=x1x2Lxnx1，令 C={x1，x[n/2]+1}，則 Cn-C只包含兩個(gè)連通分支：路 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都為非空點(diǎn)子集，{A，B，C}為的Cn一個(gè)劃分，且有A ≤[n/2]-1≤n/2和B =n-[n/2]-1≤[n/2]-1≤n/2，另外A與B之間無(wú)邊相連，所以C={x1，x[n/2]+1}是圈圖Cn的一個(gè)特殊點(diǎn)割集，可得vsn（Cn）≤2。其次，我們易推出圈圖Cn的任一單點(diǎn)點(diǎn)子集都不可能是的Cn一個(gè)特殊點(diǎn)割集，所以vsn（Cn）=2。

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

證明：設(shè)Fn（n≥3）為一個(gè)扇圖，其有點(diǎn)集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之間無(wú)邊相連，所以C={x[n/2]，z}為Cn的一個(gè)特殊點(diǎn)割集，因此vsn（F1,n)≤2。又因?yàn)镃n+1為F1,n（n≥3）的一個(gè)連通生成子圖，所以根據(jù)引理1，有vsn（F1,n)≥2，所以vsn（F1,n)=2。

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

證明：設(shè)Wn（n≥4）為一個(gè)輪圖，其有點(diǎn)集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之間無(wú)邊相連，所以C={x1，x[n/2]+1，z}為Cn的一個(gè)特殊點(diǎn)割集，因此vsn（Wn)≤3。又因?yàn)镃n+1為Wn（n≥4）的一個(gè)連通生成子圖，所以根據(jù)引理1，有2≤vsn（Wn)≤3。因?yàn)轱@然vsn（Wn)≠1，現(xiàn)在證明vsn（Wn)≠2。假設(shè)D（D =2）為輪圖Wn（n≥4）的點(diǎn)集的子集，所以要么D={z，xi}（1≤i≤n），要么D= {xi，xj}（i≠j），無(wú)論D是上面兩種中的何種情況，都有Wn-D是連通圖，所以D（D =2）不會(huì)是輪圖Wn（n≥4）的一個(gè)特殊點(diǎn)割集，所以vsn（Wn)=3。

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

證明：設(shè)Km，n（m+n≥3)為一個(gè)完全二部圖，其有點(diǎn)集V={x1,x2,L,xm,y1,y2,L,yn}和邊集E={xi,yj∶1≤i≤m, 1≤j≤n}。為了不失一般性，假設(shè)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個(gè)條件，所以C={x1，x2，L,xm}是Km，n（m+n≥3)的一個(gè)特殊點(diǎn)割集，因此vsn(Km，n)≤m。另外還要證vsn(Km，n)≥m，假設(shè)D?V（D =p＜m），因?yàn)閜＜m≤n，所以一定存在點(diǎn)x∈{x1,x2,L,xm}D同時(shí)有點(diǎn)y∈{y1,y2,L,ym}D，所以Km，n-D是一個(gè)連通圖，可得任意的D?V（D =p＜m）都不會(huì)是Km，n（m+n≥3)的一個(gè)特殊點(diǎn)割集，所以vsn(Km，n)=min{m,n}。

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

這一節(jié)將就兩個(gè)圖的一種二元運(yùn)算圖的聯(lián)圖[3]運(yùn)算下，尋找某些圖的聯(lián)圖的點(diǎ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）同時(shí)v∈V（G2）}。

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

證明：令D是G+H的點(diǎn)集VG+H的一個(gè)子集，且有D ＜nH。因?yàn)镈 ＜nH≤nG，顯然（G+H）-D是連通圖，可得D（D ＜nH）不可能是圖G+H的一個(gè)特殊點(diǎn)割集，所以vsn（G+H）≥nH。

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

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

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

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

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

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

證明：假設(shè)nG≥n，根據(jù)引理3易得vsn（G+Kn）=n。若假設(shè)nG≥n，引理3有vsn（G+Kn）≤n。設(shè)D≠?且D?VG+Kn同時(shí)還滿足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）。無(wú)論上面是3種情況中的何種情況，都有（G+Kn）-D是連通的，可知D（D ＜n）不可能是圖G+Kn的一個(gè)特殊點(diǎn)割集，所以vsn（G+Kn）=n。

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

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

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

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

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

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

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

若D?VG或D=VK1,則 （G+K1）-D是一個(gè)連通圖；若D∩VG≠?且D∩VK1≠?時(shí)，則有1≤D∩VG≤vsnG，因此D∩VG不是圖G的一個(gè)特殊點(diǎn)割集。由于假設(shè)D是圖G+K1的一個(gè)特殊點(diǎn)割集，所以存在VG+K1的非空子集A,B，使得滿足定義1的3個(gè)條件，所以A ≤(nG+1)/2且有B≤(nG+1)/2。因?yàn)锳∪B∪（DVK1）=（A∪B∪D）VK1=VG+K1VK1=VG，所以{A,B,DVK1}是圖G的一個(gè)劃分，但D∩VG不是圖G的一個(gè)特殊點(diǎn)割集，因?yàn)镈∩VG=DVK1，所以A ＞nG/2或B ＞nG/2。不失一般性，我們假設(shè)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且對(duì)任意i的都有ni≥2，則vsn(G)max{ni∶1≤i≤m}。

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

推論1若圖Gn=K2,2,L,2(n≥2)是一個(gè)完全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)在考慮一個(gè)完全圖刪除一個(gè)獨(dú)立邊集甚至刪除一個(gè)獨(dú)立邊集后，對(duì)其點(diǎn)分割數(shù)影響情形。

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

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

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

4 總結(jié)

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

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

當(dāng)然，本文還有值得深入研究發(fā)展之處，若能對(duì)特殊點(diǎn)割集定義中第3個(gè)條件max{A,B} ≤n/2進(jìn)行擴(kuò)展，討論在max{A,B }≤n/k（?k∈N+）條件下的點(diǎn)分割數(shù)，則將會(huì)有更廣泛的應(yīng)用空間，這也是將要繼續(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］張園萍，強(qiáng)會(huì)英，孫亮萍．星扇輪聯(lián)圖的鄰點(diǎn)可約邊染色［J］．?dāng)?shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012，42（13）：207-213．

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

(責(zé)任編輯：朱聯(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">文章編號(hào)：1

1673-4343（2014）04-0028-04

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

2014-06-08

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

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