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

On Problem for Vertex Separable Numbers of Graph and Joint Graph

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

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 as P n,C n,F1 n,W n,K m,n,m i = 1ΣK n i etc. are characterized and the influence of the vertex separable number resulting from deletion an influent edge set of K n is analyzed in this paper.