沈云星

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

1 引言

圖的頂點(diǎn)劃分問題是圖論研究中的一個(gè)重要問題.它在超大規(guī)模集成電路設(shè)計(jì)中有著重要的作用.最大割問題是一個(gè)著名的問題，就是尋找圖的一個(gè)頂點(diǎn)劃分V(G)=V1?V2使得 e (V1, V2)最大，其中e(V1, V2)表示滿足兩個(gè)端點(diǎn)分別在不同子集V1和V2的邊的數(shù)目.一個(gè)圖G的劃分V(G)=V1?V2稱為G的平衡二部劃分如果滿足-1≤ |V1|- | V2|≤1.用(V1, V2)表示二部劃分V(G)=V1?V2.圖的最小平衡二部劃分問題，就是尋求頂點(diǎn)集的一個(gè)平衡二部劃分(V1,V2)使得e(V1,V2)最小.這是一個(gè)NP-難的問題，對于平圖，關(guān)于這個(gè)問題的復(fù)雜性[1]至今還是未知的.很多學(xué)者致力于一些特殊圖類或具有限制條件的平圖[2]的研究.

設(shè)V(G),E(G)分別表示圖G的頂點(diǎn)集合、邊集合.設(shè) Φ≠S?V(G)，用Ns(u)表示u∈V(G)的鄰點(diǎn)在S中的這些點(diǎn)構(gòu)成的集合.G[S]表示以S為頂點(diǎn)集，以兩端點(diǎn)均在S中的邊的全體為邊集所組成的子圖.用[u , v ]表示圖G的一個(gè)圈C上按順時(shí)針方向從u到v的所有頂點(diǎn)（包含u，v）.用K2+e表示K2加上一條邊得到的圖.

猜想[2]提出：一個(gè)階為n的平圖存在平衡二部劃分(V1, V2)滿足e(V1, V2)≤n.

本文證明了具有n個(gè)頂點(diǎn)的自對偶平圖存在平衡二部劃分(V1, V2)使得e(V1, V2)≤n，并且還給出了它的一類極圖，只有K4和K2+e.

在第二部分中，先給出關(guān)于自對偶平圖的定義、性質(zhì)和幾個(gè)有用的引理，主要結(jié)論和證明過程在第三部分完成.

2 相關(guān)的定義、性質(zhì)及引理

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

定義2.2[3]給出平圖G，定義另一個(gè)圖G*如下：對于G的每個(gè)面 f，都有G*的頂點(diǎn) f*與之對應(yīng)；對于G的每一條邊e，都有G*的邊e*與之對應(yīng)；G*中頂點(diǎn) f*與g*由e*連接，當(dāng)且僅當(dāng)G中與頂點(diǎn) f*和 g*對應(yīng)的面 f和g被邊e分隔.圖G*稱為G的對偶圖.

定義2.3[3]若一個(gè)平圖G與它的對偶圖G*同構(gòu)，則稱G為自對偶平圖.

性質(zhì)2.1 設(shè)G是自對偶平圖，則G是連通的.

證明設(shè) G*是G的對偶圖，由對偶圖的性質(zhì)可知：G*連通，且由于G是自對偶的，所以G也連通.

性質(zhì)2.2 一個(gè)具有n個(gè)頂點(diǎn)，m條邊，r個(gè)面的自對偶平圖G滿足m=2n-2.

證明由于G是自對偶的，從而 n=r.由性質(zhì)2.1，G滿足歐拉公式，即 n -m+r=2，從而得到m=2n-2.

引理2.1[2]設(shè)(V1, V2)是G中使得e(V1, V2)為最小的平衡二部劃分，則對于任意的一對頂點(diǎn)ui∈V1和vj∈ V2，有：|NV1(ui) |+ | NV2(vj)|≥ |NV2(ui)|+ | NV1(vj) |，uivj? E (G ) 和 | NV1(ui)|+ | NV2(vj)|≥ |NV2(ui)|+ | NV1(vj)|-2 ，uivj∈E(G ) .

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

引理2.3[3]設(shè)G連通且S是V(G ) 的非空真子集，Sˉ=V(G)S，則邊割[S , S ˉ]是G的鍵當(dāng)且僅當(dāng)G[S]和G[Sˉ] 都連通.

引理2.4[3]設(shè)G=(V , E,F ) 是連通的平圖，G*是G的對偶圖，則有：

（1）如果B是G的鍵，則 B*是G*的圈；

（2）如果C是G的圈，則C*是G*的鍵.

3 主要結(jié)論

定理3.1設(shè)G是具有 ||V(G)=n，||E(G)=m的自對偶平圖，則G存在平衡二部劃分(V1, V2)使得e(V1, V2)≤n.且min{e ( V1, V2):(V1, V2)是G的平衡二部劃分 }=n且G[V1]，G[V2]都連通，當(dāng)且僅當(dāng)G是 K4或K2+e.

證明先 證明第一部分

由于G是自對偶的，從而由性質(zhì)2.2，得到m=2n-2.注意到G必定存在一個(gè)度為3或度為2的頂點(diǎn)，將其記為x，否則有4n-4≥4n，矛盾.

若n=2k+1，則令G'=G-x；若n=2k，則令G'=G，此時(shí)得到的G'也是平圖.

設(shè)(V1, V2)是G'中使得eG'(V1, V2)最小的平衡二部劃分，進(jìn)一步假設(shè)V1={u1, u2,…,uk} ，V2={v1, v2,…,vk}.由引理2.2知，存在k-2個(gè)頂點(diǎn)對{ui, vj}滿足ui∈V1，vj∈V2，uivj?E(G').通過改變它們的順序，不失一般性，假設(shè)k-2個(gè)頂點(diǎn)對為{ui, vi}，i≤k-2.由引理2.1知

|NV1(ui) |+ | NV2(vi)|≥ |NV2(ui)|+ | NV1(vi) |，i≤k-2和 | NV1(ui)|+ | NV2(vi)|≥ |NV2(ui)|+ | NV1(vi)|-2，i≥k-1.

將上面所有的不等式加起來，得到：

從而得到eG'(V1, V2)≤2+(| E ( G')|-2).

若 n =2k，則 | E (G')|= | E (G ) | =2n-2.此時(shí)eG(V1, V2)=eG'(V1, V2)≤2+n-2=n.

若 n =2k+1，則 | E (G')|≤ |E ( G ) | -2=2n-4.此時(shí)eG'(V1, V2)≤2+n-3=n-1.注意到dG(x)=3或dG(x)=2，現(xiàn)將 x 加入V1或V2，則有，其中 V1'=V1?{x}，或=V2?{x}.

綜上所述，證明了G存在平衡二部劃分(V1, V2)使得e(V1, V2)≤n.

下面證明第二部分.

不妨假設(shè)(V1, V2)是G中使得e(V1, V2)=n為最小的平衡二部劃分且G[V1]、G[V2]是連通的.由性質(zhì)2.1和引理2.3、2.4可知，圖G存在一個(gè)長度為n的圈C，即是G的一個(gè)哈密頓圈.設(shè)V(C)={v1, v2,…,vn} ，分別將C的內(nèi)部和外部記為Cin，Cout.下面考慮所有可能的頂點(diǎn)集V(G)的平衡二部劃分(Vi,1,Vi,2)，形如：

（說明：當(dāng)i+1,…,i+[n-12] >n時(shí)，取 i +1=(i + 1) mod n，…，i+[n-12] =(i + [n-12] )mod n.后面遇到類似情形，如此說明）

下面證明e(Vi,1,Vi,2)=n，i∈{1 , 2,…,n}.

由m=2n-2，| E ( C ) | =n可得：G中剩下n-2條邊，則有

又由于此時(shí)G的最小平衡割的大小為n，所以

由（1）、（2）可知

下面根據(jù)n為偶數(shù)和奇數(shù)分兩種情況進(jìn)行討論.

情形1 n=2k.

由(?)式可知，e(Vi,1,Vi,2)=2k且e(Vi+k+1,1,Vi+k+1,2)=2k，i∈{1 , 2,…,k-1} ，所以在 Cin中，[vi, vi+k-1]和[vi+k+1,vi]沒有邊存在.根據(jù) | V (C ) | =2k易知，在Cin中，vi可能的鄰點(diǎn)只能是vi+k，i∈{1 , 2,…,k-1}.又由(?)式可知e(Vi,1,Vi,2)=2k且e(Vi-k+1,1,Vi-k+1,2)=2k，i∈{k , k+1,…,2k} ，所以在Cin中，[vi, vi+k-1]和[vi-k+1,vi]沒有邊存在.根據(jù) |V ( C ) | =2k，易知，在Cin中，vi可能的鄰點(diǎn)只能是 vi+k，i∈{k , k+1,…,2k}.

綜上可得，在Cin中，vi可能的鄰點(diǎn)只能是vi+k，i∈{1 , 2,…,2k}.

同理可得，在Cout中，vi可能的鄰點(diǎn)只能是vi+k，i∈{1 , 2,…,2k}.

由G的平面性和自對偶性可知，Cin和Cout中最多各含有一條邊.也就是2k-2≤2?k≤2.由k的整數(shù)性質(zhì)易知，k=1或k=2.

當(dāng)k=1時(shí)，即n=2，可得G是一個(gè)長度為2的圈，記為G=K2+e.

當(dāng)k=2時(shí)，即n=4，可得G是一個(gè)具有4個(gè)頂點(diǎn)的完全圖，即G=K4.

易知：這兩個(gè)圖都是自對偶平圖，且它們的最小平衡割的大小都為n.

情形2 n=2k+1.

由(?)式可知，e(Vi,1,Vi,2)=2k+1且e(Vi+k+1,1,Vi+k+1,2)=2k+1，i∈{1 , 2,…,k} ，所以在 Cin中，[vi, vi+k]和[vi+k+1,vi]沒有邊存在.根據(jù) | V (C ) | =2k+1易知，在 Cin中，vi沒有鄰點(diǎn)，i∈{1 , 2,…,k}.又由(?)式可知e(Vi,1,Vi,2)=2k+1且e(Vi-k,1,Vi-k,2)=2k+1，i∈{k + 1,k+2,…,2k+1} ，所以在 Cin中，[vi, vi+k]和[vi-k,vi]沒有邊存在.根據(jù) |V ( C ) | =2k+1易知，在Cin中，vi沒有鄰點(diǎn)，i∈{k + 1,k+2,…,2k+1}.

綜上可得，在Cin中，vi沒有鄰點(diǎn)，i∈{1 , 2,…,2k+1}.

同理可得，在Cout中，vi沒有鄰點(diǎn)，i∈{1 , 2,…,2k+1}.

即2k-1=0?k=12，矛盾.

綜上所述，找到了自對偶平圖的一類極圖，只有K4和K2+e.即定理第二部分得證.

[1]Karpinski M.On approximability of minimum bisection problem[R].Trier:Electronic Colloquium on Computational Complexity,2002.

[2]Fan G,Xu B,Yu X,et al.Upper bounds on minimum balanced bipartitions[J].Discrete Math,2012,312:1077-1083.

[3]邦迪J A，默蒂U S R.圖論及其應(yīng)用[M].北京：科學(xué)出版社，1984：145-161.