沈云星

(福建農(nóng)林大學(xué)金山學(xué)院，福建 福州 350002)

0 引言

圖的頂點劃分問題是圖論研究的重要問題之一，圖的平衡劃分問題在并行計算機(jī)領(lǐng)域和大規(guī)模集成電路設(shè)計領(lǐng)域中有很多的應(yīng)用.設(shè)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的邊的數(shù)目e(V1,V2)最小. 最小平衡二部劃分問題是一個NP-完全問題[1]，因其重要性，平衡二部劃分問題受到國內(nèi)外學(xué)者的廣泛研究.

關(guān)于平面圖的最小劃分問題的復(fù)雜性至今未解決[2]. 平面圖的平衡二部劃分問題有一個猜想：任意具有n個頂點的平面圖必定含有一個平衡二部劃分V1,V2，使得e(V1,V2)≤n.FAN等[3]證明了對于無可分離三角形的平面圖G，它必含有一個平衡二部劃分V1,V2，使得e(V1,V2)≤n+1.同時，F(xiàn)AN等[3]證明了無三角形的連通平面圖G，它必含有一個平衡二部劃分V1,V2，使得e(V1,V2)≤n-2，且極圖是K1,3，K3,3-e，K2,k，k≥1.對于更多的平衡二部劃分的相關(guān)結(jié)果可參考文獻(xiàn)[4-11].

設(shè)V(G),E(G)分別表示圖G的頂點集合和邊集合.設(shè)Vi?V(G)，用NVi(x)表示頂點x在Vi中的鄰點的集合，|NVi(x)|表示頂點x在Vi中的鄰點的數(shù)目，N(x)表示頂點x的鄰點集合，d(x)表示頂點x的度數(shù)，δ(G)表示圖G的最小度，ω(G)表示圖G中所含最大完全圖的頂點的個數(shù)，e(Vi)表示頂點都在Vi中的邊的數(shù)目.

下面將證明n階平面圖G，如果它的邊數(shù)m≤2n-2，則G含有一個平衡二部劃分V1,V2，使得e(V1,V2)≤n，并給出了極圖有且僅有K4.

1 相關(guān)的定義與引理

定義1[12]如果一個圖能畫在平面上使得它的邊僅與端點相交，則稱這個圖是可嵌入平面的或者平面圖.

引理2[12](Kuratowski 定理) 一個圖是平面圖當(dāng)且僅當(dāng)它不含有K5或者K3,3的剖分圖.

引理4[3]設(shè)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 主要結(jié)論

定理1設(shè)G是具有V(G)=n,E(G)=m的一個平面圖，且滿足m≤2n-2，則G存在一個平衡二部劃分V1,V2，使得e(V1,V2)≤n.且min{e(V1,V2)}=n當(dāng)且僅當(dāng)G是K4.

證明 首先證明第一部分，由引理2可知，一個平面圖的團(tuán)數(shù)最多是4，且由已知條件m≤2n-2，根據(jù)引理1，則G存在一個平衡二部劃分V1,V2，使得e(V1,V2)≤n.

下面證明第二部分，為了描述極圖，設(shè)G是具有最小頂點數(shù)的一個反例.

假設(shè)x是圖G中具有最小度的頂點，則d(x)≤3.否則，4n-4≥4n，產(chǎn)生矛盾.

設(shè)G′=G-x，則G′不是極圖.

下面根據(jù)G的頂點數(shù)的奇偶性分別討論.

當(dāng)n=2k+1時，G′的頂點集可被分成兩個子集U1,U2，使得|U1|=|U2|，且e(U1,U2)≤n-2.此時，把頂點x加入到與其鄰點多的子集中，則得到了關(guān)于G的一個平衡二部劃分的大小最多為n-1，與G的選擇矛盾.因此，進(jìn)一步討論n=2k≥6.

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

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

(1)

否則，將x放到U2，發(fā)現(xiàn)存在G的一個平衡二部劃分的大小至多是n-1，產(chǎn)生矛盾，因此(1)成立.

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

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

當(dāng)d(x)=1時，直接將x放到U2，很容易發(fā)現(xiàn)G的一個平衡割大小最多為n-1，產(chǎn)生矛盾.

當(dāng)d(x)=2時，設(shè)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，產(chǎn)生矛盾.

設(shè)v1,v2是x的兩個鄰點，則d(v1)≥2，d(v2)≥2.因為，若d(v1)=1，則將x放到U1,將v1放到U2，產(chǎn)生G的一個平衡二部劃分的大小最多為n-1，產(chǎn)生矛盾.當(dāng)d(v2)=1時，產(chǎn)生同樣的矛盾.且有

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

(2)

因此，下面僅需考慮d(x)=3，即δ(G)=3.進(jìn)一步假設(shè)U1={u1,u2,…,uk}，U2={v1,v2,…,vk-1}.

根據(jù)頂點x在U1中的鄰點的情形討論，主要為兩種情形.

情形1：N(x)?U1.

不妨設(shè)N(x)={uk-2,uk-1,uk}，如果存在頂點t∈U1N(x)，使得|NU1(t)|≤|NU2(t)|+1或者存在頂點t∈N(x)，使得|NU1(t)|≤|NU2(t)|.設(shè)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個不等式相加，根據(jù)引理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，則產(chǎn)生矛盾.不失一般性，假設(shè)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，產(chǎn)生矛盾.

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

又由δ(G)=3，則有

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

故有

(5)

下面證明如下論斷：

(6)

假設(shè)(6)式不成立，即存在頂點集{v1,v2,…,vk-1}中的一個點v，使得|NU2(v)|=0.

如果v=vk-1，由(5)式d(vk-1)=3，則有|NU1(vk-1)|=2.應(yīng)用引理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)，產(chǎn)生類似矛盾.因此，ukvi∈E(G)，uk-1vi∈E(G)，i∈{1,2,…,k-1}.

3 結(jié)語

圖的頂點劃分問題是圖論研究的重要問題之一，本文通過圖的特點，結(jié)合平衡二部劃分的相關(guān)知識，得到除了K4以外，滿足m≤2n-2的n階平面圖G含有一個平衡二部劃分V1,V2，使得e(V1,V2)≤n-1.