關(guān)于平面圖平衡二部劃分的一個(gè)結(jié)論

沈云星

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

0 引言

圖的頂點(diǎn)劃分問題是圖論研究的重要問題之一，圖的平衡劃分問題在并行計(jì)算機(jī)領(lǐng)域和大規(guī)模集成電路設(shè)計(jì)領(lǐng)域中有很多的應(yīng)用.設(shè)G是具有V(G)=n,E(G)=m的圖，V1,V2是V(G)的一個(gè)劃分，且V1,V2滿足-1≤|V1|-|V2|≤1，則稱V1,V2是V(G)的一個(gè)平衡二部劃分.G的最小平衡劃分問題是指尋找頂點(diǎn)集V(G)的一個(gè)平衡二部劃分V1,V2，使得連接一個(gè)頂點(diǎn)在V1，另一個(gè)頂點(diǎn)在V2的邊的數(shù)目e(V1,V2)最小. 最小平衡二部劃分問題是一個(gè)NP-完全問題[1]，因其重要性，平衡二部劃分問題受到國內(nèi)外學(xué)者的廣泛研究.

關(guān)于平面圖的最小劃分問題的復(fù)雜性至今未解決[2]. 平面圖的平衡二部劃分問題有一個(gè)猜想：任意具有n個(gè)頂點(diǎn)的平面圖必定含有一個(gè)平衡二部劃分V1,V2，使得e(V1,V2)≤n.FAN等[3]證明了對于無可分離三角形的平面圖G，它必含有一個(gè)平衡二部劃分V1,V2，使得e(V1,V2)≤n+1.同時(shí)，F(xiàn)AN等[3]證明了無三角形的連通平面圖G，它必含有一個(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的頂點(diǎn)集合和邊集合.設(shè)Vi?V(G)，用NVi(x)表示頂點(diǎn)x在Vi中的鄰點(diǎn)的集合，|NVi(x)|表示頂點(diǎn)x在Vi中的鄰點(diǎn)的數(shù)目，N(x)表示頂點(diǎn)x的鄰點(diǎn)集合，d(x)表示頂點(diǎn)x的度數(shù)，δ(G)表示圖G的最小度，ω(G)表示圖G中所含最大完全圖的頂點(diǎn)的個(gè)數(shù)，e(Vi)表示頂點(diǎn)都在Vi中的邊的數(shù)目.

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

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

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

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

引理4[3]設(shè)V1,V2是G中使得e(V1,V2)為最小的平衡二部劃分，則對于任意的一對頂點(diǎn)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的一個(gè)平面圖，且滿足m≤2n-2，則G存在一個(gè)平衡二部劃分V1,V2，使得e(V1,V2)≤n.且min{e(V1,V2)}=n當(dāng)且僅當(dāng)G是K4.

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

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

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

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

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

當(dāng)n=2k+1時(shí)，G′的頂點(diǎn)集可被分成兩個(gè)子集U1,U2，使得|U1|=|U2|，且e(U1,U2)≤n-2.此時(shí)，把頂點(diǎn)x加入到與其鄰點(diǎn)多的子集中，則得到了關(guān)于G的一個(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的一個(gè)平衡二部劃分的大小至多是n-1，產(chǎn)生矛盾，因此(1)成立.

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

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

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

當(dāng)d(x)=2時(shí)，設(shè)v是G中的一個(gè)頂點(diǎn)，滿足vx?E(G)且d(x)+d(v)為最小.則G-x-v不是極圖. 否則，G-x-v是K4.由m≤2n-2可推出，在G中，d(v)≤2，易找到G的一個(gè)平衡二部劃分的大小最多為n-1，產(chǎn)生矛盾.

設(shè)v1,v2是x的兩個(gè)鄰點(diǎn)，則d(v1)≥2，d(v2)≥2.因?yàn)?，若d(v1)=1，則將x放到U1,將v1放到U2，產(chǎn)生G的一個(gè)平衡二部劃分的大小最多為n-1，產(chǎn)生矛盾.當(dāng)d(v2)=1時(shí)，產(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ù)頂點(diǎn)x在U1中的鄰點(diǎn)的情形討論，主要為兩種情形.

情形1：N(x)?U1.

不妨設(shè)N(x)={uk-2,uk-1,uk}，如果存在頂點(diǎn)t∈U1N(x)，使得|NU1(t)|≤|NU2(t)|+1或者存在頂點(diǎn)t∈N(x)，使得|NU1(t)|≤|NU2(t)|.設(shè)V1=U1{t}∪{x}，V2=U2∪{t}，則V1,V2是G中的一個(gè)平衡劃分，使得e(V1,V2)≤n-1，與G的每個(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個(gè)不等式相加，根據(jù)引理3可得

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

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

此時(shí)有e(U1,U2)=n-2.因?yàn)槿绻鹐(U1,U2)=n-3，可通過把x放到U2，得到G的一個(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中的一個(gè)平衡二部劃分，且e(V1,V2)≤n-1，產(chǎn)生矛盾.

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

又由δ(G)=3，則有

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

故有

(5)

下面證明如下論斷：

(6)

假設(shè)(6)式不成立，即存在頂點(diǎn)集{v1,v2,…,vk-1}中的一個(gè)點(diǎn)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個(gè)頂點(diǎn)u，使得uvk-1?E(G).

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

其中，這樣的u有k-3個(gè).

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

其中，這樣的u有3個(gè).

將上述的k個(gè)不等式相加，得到

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

如果對于某個(gè)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)

同理，如果對于某個(gè)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é)語

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