关于平面图平衡二部划分的一个结论

沈云星

(福建农林大学金山学院，福建 福州 350002)

0 引言

图的顶点划分问题是图论研究的重要问题之一，图的平衡划分问题在并行计算机领域和大规模集成电路设计领域中有很多的应用.设G是具有V(G)=n,E(G)=m的图，V1,V2是V(G)的一个划分，且V1,V2满足-1≤|V1|-|V2|≤1，则称V1,V2是V(G)的一个平衡二部划分.G的最小平衡划分问题是指寻找顶点集V(G)的一个平衡二部划分V1,V2，使得连接一个顶点在V1，另一个顶点在V2的边的数目e(V1,V2)最小. 最小平衡二部划分问题是一个NP-完全问题[1]，因其重要性，平衡二部划分问题受到国内外学者的广泛研究.

关于平面图的最小划分问题的复杂性至今未解决[2]. 平面图的平衡二部划分问题有一个猜想：任意具有n个顶点的平面图必定含有一个平衡二部划分V1,V2，使得e(V1,V2)≤n.FAN等[3]证明了对于无可分离三角形的平面图G，它必含有一个平衡二部划分V1,V2，使得e(V1,V2)≤n+1.同时，FAN等[3]证明了无三角形的连通平面图G，它必含有一个平衡二部划分V1,V2，使得e(V1,V2)≤n-2，且极图是K1,3，K3,3-e，K2,k，k≥1.对于更多的平衡二部划分的相关结果可参考文献[4-11].

设V(G),E(G)分别表示图G的顶点集合和边集合.设Vi⊆V(G)，用NVi(x)表示顶点x在Vi中的邻点的集合，|NVi(x)|表示顶点x在Vi中的邻点的数目，N(x)表示顶点x的邻点集合，d(x)表示顶点x的度数，δ(G)表示图G的最小度，ω(G)表示图G中所含最大完全图的顶点的个数，e(Vi)表示顶点都在Vi中的边的数目.

下面将证明n阶平面图G，如果它的边数m≤2n-2，则G含有一个平衡二部划分V1,V2，使得e(V1,V2)≤n，并给出了极图有且仅有K4.

1 相关的定义与引理

定义1[12]如果一个图能画在平面上使得它的边仅与端点相交，则称这个图是可嵌入平面的或者平面图.

引理2[12](Kuratowski 定理) 一个图是平面图当且仅当它不含有K5或者K3,3的剖分图.

引理4[3]设V1,V2是G中使得e(V1,V2)为最小的平衡二部划分，则对于任意的一对顶点ui∈V1,vj∈V2，有

(i)|NV1(ui)|+|NV2(vj)|≥|NV2(ui)|+|NV1(vj)|,uivj∉E(G)；

(ii)|NV1(ui)|+|NV2(vj)|≥|NV2(ui)|+|NV1(vj)|-2,uivj∈E(G).

2 主要结论

定理1设G是具有V(G)=n,E(G)=m的一个平面图，且满足m≤2n-2，则G存在一个平衡二部划分V1,V2，使得e(V1,V2)≤n.且min{e(V1,V2)}=n当且仅当G是K4.

证明 首先证明第一部分，由引理2可知，一个平面图的团数最多是4，且由已知条件m≤2n-2，根据引理1，则G存在一个平衡二部划分V1,V2，使得e(V1,V2)≤n.

下面证明第二部分，为了描述极图，设G是具有最小顶点数的一个反例.

假设x是图G中具有最小度的顶点，则d(x)≤3.否则，4n-4≥4n，产生矛盾.

设G′=G-x，则G′不是极图.

下面根据G的顶点数的奇偶性分别讨论.

当n=2k+1时，G′的顶点集可被分成两个子集U1,U2，使得|U1|=|U2|，且e(U1,U2)≤n-2.此时，把顶点x加入到与其邻点多的子集中，则得到了关于G的一个平衡二部划分的大小最多为n-1，与G的选择矛盾.因此，进一步讨论n=2k≥6.

设U1,U2是G′中使e(U1,U2)最小的平衡二部划分.不失一般性，不妨设|U1|=|U2|+1，则得到

n-3≤e(U1,U2)≤n-2.

(1)

否则，将x放到U2，发现存在G的一个平衡二部划分的大小至多是n-1，产生矛盾，因此(1)成立.

注意到：若|NU1(x)|≤|NU2(x)|，直接将x放到U2，存在G的一个平衡二部划分的大小最多是n-1，与G中不含平衡二部划分的大小最多为n-1的要求矛盾.

因此，下面讨论|NU1(x)|>|NU2(x)|的情形.

当d(x)=1时，直接将x放到U2，很容易发现G的一个平衡割大小最多为n-1，产生矛盾.

当d(x)=2时，设v是G中的一个顶点，满足vx∉E(G)且d(x)+d(v)为最小.则G-x-v不是极图. 否则，G-x-v是K4.由m≤2n-2可推出，在G中，d(v)≤2，易找到G的一个平衡二部划分的大小最多为n-1，产生矛盾.

设v1,v2是x的两个邻点，则d(v1)≥2，d(v2)≥2.因为，若d(v1)=1，则将x放到U1,将v1放到U2，产生G的一个平衡二部划分的大小最多为n-1，产生矛盾.当d(v2)=1时，产生同样的矛盾.且有

d(v1)+d(v2)≥7.

(2)

因此，下面仅需考虑d(x)=3，即δ(G)=3.进一步假设U1={u1,u2,…,uk}，U2={v1,v2,…,vk-1}.

根据顶点x在U1中的邻点的情形讨论，主要为两种情形.

情形1：N(x)⊆U1.

不妨设N(x)={uk-2,uk-1,uk}，如果存在顶点t∈U1N(x)，使得|NU1(t)|≤|NU2(t)|+1或者存在顶点t∈N(x)，使得|NU1(t)|≤|NU2(t)|.设V1=U1{t}∪{x}，V2=U2∪{t}，则V1,V2是G中的一个平衡划分，使得e(V1,V2)≤n-1，与G的每个最小平衡二部划分的大小为n矛盾.从而有

|NU1(ui)|≥|NU2(ui)|+2,i∈{1,2,…,k-3}和|NU1(ui)|≥|NU2(ui)|+1,i∈{k-1,k-2,k}.

(3)

将(3)式中的k个不等式相加，根据引理3可得

由n≥6，则n-3≤e(U1,U2)≤n-4，与(1)式矛盾.

情形2：|NU1(x)|-|NU2(x)|=1.

此时有e(U1,U2)=n-2.因为如果e(U1,U2)=n-3，可通过把x放到U2，得到G的一个平衡割大小最多为n-1，则产生矛盾.不失一般性，假设N(x)={uk-1,uk,vk-1}.从而有

|NU1(ui)|≥|NU2(ui)|+1,i∈{1,2,…,k-2}且|NU1(ui)|≥|NU2(ui)|,i∈{k-1,k}.

(4)

否则，V1=U1{ui}∪{x}，V2=U2∪{ui}为G中的一个平衡二部划分，且e(V1,V2)≤n-1，产生矛盾.

由引理3和(4)式可知，

又由δ(G)=3，则有

其中，“-1”是由于边xvk-1.

故有

(5)

下面证明如下论断：

(6)

假设(6)式不成立，即存在顶点集{v1,v2,…,vk-1}中的一个点v，使得|NU2(v)|=0.

如果v=vk-1，由(5)式d(vk-1)=3，则有|NU1(vk-1)|=2.应用引理4，得到

|NU1(u)|≥|NU2(u)|+2,

其中，对于U1中k-2个顶点u，使得uvk-1∉E(G).

|NU1(u)|≥|NU2(u)|+3,uv∉E(G),

其中，这样的u有k-3个.

|NU1(u)|≥|NU2(u)|+1,uv∈E(G),

其中，这样的u有3个.

将上述的k个不等式相加，得到

这要求n≤4，与n≥6矛盾.因此(6)式成立.

如果对于某个i0∈{1,2,…,k-1}，使得ukvi0∉E(G)，由引理4可得

|NU1(uk)|≥|NU2(uk)|+1,

(7)

再由(4)式可知，

|NU1(ui)|≥|NU2(ui)|+1,i∈{1,2,…,k-2},

(8)

|NU1(uk-1)|≥|NU2(uk-1)|.

(9)

同理，如果对于某个i0∈{1,2,…,k-1}，使得uk-1vi0∉E(G)，产生类似矛盾.因此，ukvi∈E(G)，uk-1vi∈E(G)，i∈{1,2,…,k-1}.

3 结语

图的顶点划分问题是图论研究的重要问题之一，本文通过图的特点，结合平衡二部划分的相关知识，得到除了K4以外，满足m≤2n-2的n阶平面图G含有一个平衡二部划分V1,V2，使得e(V1,V2)≤n-1.