關于自對偶平圖的平衡劃分的一個結論

2015-06-15 06:06:20沈云星

常熟理工學院學報 2015年4期

沈云星

（福建農林大學金山學院，福建福州 350002）

1 引言

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

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

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

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

在第二部分中，先給出關于自對偶平圖的定義、性質和幾個有用的引理，主要結論和證明過程在第三部分完成.

2 相關的定義、性質及引理

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

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

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

性質2.1 設G是自對偶平圖，則G是連通的.

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

性質2.2 一個具有n個頂點，m條邊，r個面的自對偶平圖G滿足m=2n-2.

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

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

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

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

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

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

3 主要結論

定理3.1設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]都連通，當且僅當G是 K4或K2+e.

證明先證明第一部分

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

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

設(V1, V2)是G'中使得eG'(V1, V2)最小的平衡二部劃分，進一步假設V1={u1, u2,…,uk} ，V2={v1, v2,…,vk}.由引理2.2知，存在k-2個頂點對{ui, vj}滿足ui∈V1，vj∈V2，uivj?E(G').通過改變它們的順序，不失一般性，假設k-2個頂點對為{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.此時eG(V1, V2)=eG'(V1, V2)≤2+n-2=n.

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

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

下面證明第二部分.

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

（說明：當i+1,…,i+[n-12] >n時，取 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條邊，則有

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

由（1）、（2）可知

下面根據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]沒有邊存在.根據 | V (C ) | =2k易知，在Cin中，vi可能的鄰點只能是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]沒有邊存在.根據 |V ( C ) | =2k，易知，在Cin中，vi可能的鄰點只能是 vi+k，i∈{k , k+1,…,2k}.

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

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

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

當k=1時，即n=2，可得G是一個長度為2的圈，記為G=K2+e.

當k=2時，即n=4，可得G是一個具有4個頂點的完全圖，即G=K4.

易知：這兩個圖都是自對偶平圖，且它們的最小平衡割的大小都為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]沒有邊存在.根據 | V (C ) | =2k+1易知，在 Cin中，vi沒有鄰點，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]沒有邊存在.根據 |V ( C ) | =2k+1易知，在Cin中，vi沒有鄰點，i∈{k + 1,k+2,…,2k+1}.

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

同理可得，在Cout中，vi沒有鄰點，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.圖論及其應用[M].北京：科學出版社，1984：145-161.