關于平面圖平衡二部劃分的一個結論

沈云星

(福建農林大學金山學院，福建 福州 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.