图及联图的点分割数的计数研究

许冰

（福建农林大学 计算机与信息学院，福建 福州，350002）

图及联图的点分割数的计数研究

许冰

（福建农林大学 计算机与信息学院，福建 福州，350002）

图划分具有广泛的应用,主要应用于VLSI(大规模集成电路)设计,并行计算,数据挖掘和图像分割等领域,因此得到了国内外学者的普遍关注和大量研究。由于图划分是NP-完全问题,因此本文在一般图划分问题基础上提出了特殊点割集及点分割数的概念，主要应用图的连通性原理分析，给出路、圈、扇图、轮图及完全二部图及联图Pn,Cn,F1n,Wn,Km,n等的点分割数，并分析讨论了完全图Kn删除一个独立边集后，其点分割数的变化情况。

图点分割数；特殊点割集；独立边集

1 预备知识

由于在生物基因组合排列及超大规模集成电路 (VLSI)设计中，经常遇到图的划分问题，常用的方法是将网络图分割为两个子集 ,使得不同子集顶点之间的相连边数尽可能少，转化为图论问题此即图的二等分问题（Bisection）。

同时图划分问题也是经典的完全问题，通常很难在有限时间内找到最优解。尽管其实难解问题，从世纪年代至今，国内外研究者不断对其进行深入研究，提出了许多性能较好的图划分算法。现主要有年R.Leland提出的谱方法，年S.Ranka提出的空间填充曲线的几何方法，年S.Dutt提出的启发式方法以及年P.Chardaire提出的种群智能优化算法[1]等，对图划分问题给出了一些解决方案。

因为作者的基金项目涉及图论设计在生物信息学中的应用，所以重点研究了图的划分问题，尤其需要讨论研究满足某种条件下的图的划分问题，由此我们在一般图划分的点割集的基础之上，提出了特殊点割集及点分割数的概念，研究满足该种条件下的图的点分割数的计数问题。

定义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的最小特殊点割集所含顶点个数称为图的点分割数，记为vsn（G）。显而易见，对于任意一条路Pn（n≥3）,都有vsn（Pn）=1。

另外，由定义1可得，设G是一个连通图，并且有Φ≠C⊆VG，若C是G的一个特殊点割集，则可以得到以下两点：

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

(2)G-C任一连通分支所含点数至多为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 一些特殊图的点分割数

显而易见，对任意一条路Pn（n≥3）,vsn（Pn）=1。另外，对于圈图、扇图[2]、轮图、完全二部图等，可得以下结论：

定理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}，现在令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）的一个连通生成子图，所以根据引理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}。现在令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）的一个连通生成子图，所以根据引理1，有2≤vsn（Wn)≤3。因为显然vsn（Wn)≠1，现在证明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。现在令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 某些联图的点分割数

这一节将就两个图的一种二元运算图的联图[3]运算下，寻找某些图的联图的点分割数。所谓两图的联图，即图G1与G2的联图我们记为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的一个连通生成子图，根据引理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，根据引理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都考虑的是可平分图和另一图的联图的点分割数，下面两个引理我们将考虑可分离图与另一图的联图的点分割数问题。

引理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的一个连通生成子图，所以根据引理1和定理4可得出min{nG，nH}≤vsn（G+H），因此min{nG，nH}≤vsn（G+H）。

引理6若图G是一个可分离偶图，则vsn（G+K1）=1+vsnG。

证明：根据引理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为奇数，与图G为偶图矛盾，所以vsn（G+K1）＞vsn（G）m，可得结论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）≤现在我们假设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)。

现在考虑一个完全图删除一个独立边集甚至删除一个独立边集后，对其点分割数影响情形。

定理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的某些边）的一个连通生成子图，根据引理1和（1）中证明可得vsn(Kn-S）≤vsn(Kn-e≤n-2)。现在来证明vsn(Kn-S）≥n-2，若n为偶数，则Gn=K2,2,L,2是Kn-S的一个连通生成子图，根据引理1和推论1可得vsn(Kn-S）≥vsn(Gn)=n-2；若n为奇数，则Gn=[(n-1)/2]2+ K1是Kn-S的一个连通生成子图，根据引理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 总结

通过对图特殊点割集的分析，得到路、圈、扇图、轮图及完全二部图的点分割数为vsn(Pn)=1、vsnffffedffffec

(Cn)=2、vsn(F1,n)=2、vsn(Wn)=3及vsn(Km,n)=min{m,n}。同时还得到联图的点分割数为vsn（)i =2(n-1)，并证明得知对于完全图Kn(n≥3)的任意一个非空独立边集S，都满足vsn(Kn-S）=n-2，即完全图Kn(n≥3)删除任意一个独立边集后，对其点分割数都只比完全图顶点个数n减少两个，不会随独立边集的不同而产生变化。

当然，本文还有值得深入研究发展之处，若能对特殊点割集定义中第3个条件max{A,B} ≤n/2进行扩展，讨论在max{A,B }≤n/k（∀k∈N+）条件下的点分割数，则将会有更广泛的应用空间，这也是将要继续努力的方向。

［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］张园萍，强会英，孙亮萍．星扇轮联图的邻点可约边染色［J］．数学的实践与认识，2012，42（13）：207-213．

［3］周志东，黄元秋，彭小多，等．一个小图和路与圈的联图的交叉数［J］．系统科学与数学，2013，33（2）：206-216．

(责任编辑：朱联九）

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

福建省农林大学校青年基金项目（2011xjj26）

许冰，男，福建长乐人，讲师。研究方向：数据挖掘。