网络的划分 network partition

网络的划分是图研究中的一个热点，在集成电路设计中有很多应用。我们首先考虑图的平衡二分问题，也就是说给定一个图G(V,E)，把他的顶点划分成两个部分 C, V\C, 使得这两个顶点集的大小差不多，也就是|C|约等于|V\C|.而两个点集之间的边数最少，也就是 |{e(vi,vj) : vi in C and vj in V\C}|的大小最小化。

我们给顶点一个标号，如果vi属于C，那么t(vi)=0，否则t(vi)=1。那么我们定义两种边：
inter-edge(C,V\C) : {e(vi,vj) : t(vi) == t(vj)}
intra-edge(C,V\C) : {e(vi,vj) : t(vi) != t(vj)}

一般来说，图的b-二分问题定义为:
min intra-edge(C,V\C)
s.t. max{|C|,|V\C|} * 2 / |V| < b

未完待续...