圖的平衡劃分.pdf

1、本文研究有關(guān)圖的平衡劃分的一些問題. 設(shè)V1,...，Vk是G的頂點集V(G)的一個k-劃分，如果-1≤|Vi|-|Vi|≤1，1≤i，j≤k，則稱它是平衡的.Bollobás和Scott在文獻(xiàn)[13]中提出問題：給定圖G，找G的頂點集V(G)的平衡劃分Vi,...,Vk使得max{e(V1),...,e(Vk)}最小.特別地，他們提出了下述猜想： 猜想2.1.1[13]設(shè)G是一個最小度至少為2的圖，則G存在頂點集V(G)的平衡二部

2、劃分V1，V2使得max{e(V1)，e(V2)}≤|E(G)|/3. Bollobás和Scott在文獻(xiàn)[15]中討論了正則圖的公平平衡劃分問題. 定理1.5.1[15]設(shè)k≥2是整數(shù)，G是一個邊數(shù)為m的k-正則圖，則G存在一個平衡二部劃分V(G)=V1ＵV2使得(a)當(dāng)k是奇數(shù)時，max{e(V1)，e(V2)}≤k-1/4km；(b)當(dāng)k和|V(G)|都是偶數(shù)時，max{e(V1)，e(V2)}≤1/4k/k+1m；(c)當(dāng)k

3、是偶數(shù)，|V(G)|是奇數(shù)時，max{e(V1)，e(V2)}≤1/4k/k+1m+k/4.并且，(a)的極圖是sKk+1，s≥1；(b)的極圖是2sKk+1，s≥1；(c)的極圖是(2s+1)Kk+1，s≥0. 他們的結(jié)果說明猜想2.1.1對正則圖是成立的. 我們幾乎完全解決了這一猜想.我們證明了這個猜想對所有平均度大于或等于6的圖都成立.實際上，我們給出了平衡劃分max{e(V1)，e(V2)}的一個上界.這個界對于偶數(shù)個點的星

4、圖是最好可能的.并且對于任意一個給定的圖，我們的證明表明可以在多項式時間內(nèi)找到滿足定理條件的平衡二部劃分. 定理2.1.1設(shè)G是一個有n個點，m條邊的圖，則G存在平衡二部劃分V(G)=V1∪V2滿足e(V1，V2)≥m/2，且(1)如果n是偶數(shù)，則max{e(V1)，e(V2)}≤m/4+△(G)-δ(G)/4；(2)如果n是奇數(shù)，則max{e(V1)，e(V2)}≤m/4+△(G)+1/4. 下面的推論2.1.1說明對于平均度至少

5、是6的圖猜想2.1.1成立.推論2.1.2回答了Bollobás和Scott[13]提出的一個問題：滿足什么條件的圖存在平衡二部劃分，使得每個點集導(dǎo)出子圖所包含的邊數(shù)都不超過(1+0(1))m/4?或許△(G)=0(n)或者當(dāng)n→∞時δ(G)→∞就足夠了.
　　推論2.1.1設(shè)G是一個平均度至少是6的圖，則G存在頂點集V(G)的平衡二部劃分V1，V2使得max{e(V1)，e(V2)}≤|E(G)|/3. 推論2.1.2設(shè)G是一

6、個有m條邊，n個點的圖，如果△(G)=o(n)或者當(dāng)n→∞時δ(G)→∞，則G存在頂點集V(G)的平衡二部劃分V1,V2使得max{e(V1)，e(V2)}≤(1+0(1))m/4. Bollobás和Scott在文獻(xiàn)[13]中提出問題：對于平衡劃分問題，是否能找到與一般最大割問題中Edwards界類似的結(jié)論?我們完整的回答了這一問題.我們用圖的邊數(shù)和最大匹配數(shù)α'(G)給出平衡二部劃分最大割的一個下界，并證明了這個界是最好可能的.由

7、于求α'(G)是有多項式時間算法的(見文獻(xiàn)[25，51]).從定理的證明可以看出尋找達(dá)到這個界的平衡二部劃分有多項式時間算法.令f=(G)=max{e(V1,V2)|V(G)=V1∪V2是G的平衡二部劃分}.則有： 定理3.1.1設(shè)G是一個有m條邊的圖，最大匹配數(shù)為α'(G)，則f=(G)≥m/2+α'(G)/2. 用類似定理3.1.1的證明方法，我們證明了下面的定理： 定理3.1.2設(shè)G是一個圖，H是G的導(dǎo)出子圖，且|V(H)|

8、是偶數(shù)，則f=(G)≥f=(H)+1/2(|E(G)|-|E(H)|). 受到猜想2.1.1和定理3.1.1的啟發(fā)，很自然地有這樣的問題：滿足什么條件的圖存在平衡二部劃分V(G)=V1∪V2，使得e(V1,V2)=f=(G)的同時也滿足Bollobás和Scott猜想中的要求max{e(V1)，e(V2)}≤|E(G)|/3通過研究，我們有下面的結(jié)論，其中e(G)=|E(G)|. 定理4.1.1設(shè)G是一個圖，如果△(G)≤7/5δ(

9、G)，則G的任意一個使得e(V1，V2)=f=(G)的平衡二部劃分V1,V2都滿足e(Vi)≤e(G)/3，i∈{1，2}. 定理4.1.2設(shè)2≤r≤4是一個實數(shù)，G是一個圖，如果當(dāng)|V(G)|是偶數(shù)時△(G)≤r+4/3r-4δ(G)；當(dāng)|V(G)|是奇數(shù)時△(G)≤r+4/3r-4δ(G)-4r/3r-4]，則G的任意一個使得e(V1,V2)=f=(G)的平衡二部劃分V1,V2都滿足e(Vi)≤e(G)/r，i∈{1，2}. B

10、ollobás和Scott在文獻(xiàn)[14]中證明了如果一個圖G有m=(n2)+(k2)條邊，其中n＞5×108，0≤(k2)≤n-1，則存在G的二部劃分V(G)=V1∪V2使得e(V1，V2)≥min{「n2/4」+「k2/4」，「(n+1)2/4」}.如果「n2/4」+「k2/4」≥「(n+1)2/4」，則極圖是從Kn+1中任意去掉(n+12)-(n2)-(k2)條邊所得到的圖.如果「n2/4」+「k2/4」≤「(n+1)2/4」，則當(dāng)

11、k≠4時，極圖是Kn和Kk的邊不交的并；當(dāng)k=4時，極圖是Kn和K4的邊不交的并，或者Kn和兩個K3的邊不交的并.我們考慮n充分大時的有完美匹配的圖.得到下面這個定理： 定理5.1.1設(shè)n＞5×108，0≤(k2)≤n-1，如果圖G有m=(n2)+(k2)條邊，且G有完美匹配，則存在G的二部劃分V(G)=V1∪V2滿足：(i)||V1|-|V2‖≤4k+8；(ii)e(V1，V2)≥min{「n2/4」「k2/4」，「(n+1)2/4

12、」}如果「n2/4」+「k2/4」≥「(n+1)2/4」，則極圖是從Kn+1中任意去掉(n+12)-(n2)-(kn)條邊并有完美匹配的圖.如果「n2/4」+「k2/4」≤「(n+1)2/4」，則當(dāng)k≠4時，極圖是Kn和Kk的邊不交的并；當(dāng)k=4時，極圖是Kn和K4的邊不交的并，或者Kn和兩個K3的邊不交的并. 我們還具體研究了幾個圖類的公平平衡劃分問題，得到以下結(jié)論： 定理6.1.1設(shè)k≥3是奇數(shù)，G是一個邊數(shù)為m的(k，k-1)

13、-雙正則圖.假設(shè)G有n1個k度頂點.那么V(G)存在一個平衡二部劃分V1，V2使得(a)當(dāng)|V(G)|是偶數(shù)時，max{e(V1)，e(V2)}≤m/4-n1/8；(b)當(dāng)|V(G)|是奇數(shù)時，max{e(V1)，e(V2)}≤m/4-n1/8+k-1/8. 定理6.1.2設(shè)k≥2是偶數(shù)，G是一個邊數(shù)為m的(k，k-1)-雙正則圖.假設(shè)G有n2個k-1度頂點，那么V(G)存在一個平衡二部劃分V1，V2，使得(a)當(dāng)|V(G)|是偶數(shù)時

14、，max{e(V1)，e(V2)}≤m/4+n2/8；(b)當(dāng)|V(G)|是奇數(shù)時，max(e(V1)，e(V2)}≤m/4+n2/8+k/8. 定理6.2.1設(shè)T是一個邊數(shù)為m的樹，如果diam(T)≥m/3+1，則T有一個平衡二部劃分V(T)=V1∪V2滿足對于i∈{1，2}，e(Vi)≤m/3. 定理6.3.1設(shè)G為完全二部圖Km,n,m≤n.(a)當(dāng)m和n均為偶數(shù)時，取遍G的所有平衡二部劃分V(G)=V1∪V2，公式略.(b

15、)當(dāng)m和n均為奇數(shù)時，取遍G的所有平衡二部劃分V(G)=V1∪V2，公式略.(c)當(dāng)m是奇數(shù)，n是偶數(shù)時，取遍G的所有平衡二部劃分V(G)=V1∪V2，公式略.(d)當(dāng)m是偶數(shù)，n是奇數(shù)時，取遍G的所有平衡二部劃分V(G)=V1∪V2，公式略. 定理6.3.2設(shè)G是完全二部圖Km,n,m≤n.(a)如果n-m≡0(mod2)，則f=(G)=m·n+m/2；(b)如果n-m≡1(mod2)，則f=(G)=m·n+m+1/2. 我們用隨

16、機(jī)的方法討論了圖的平衡二部劃分與均勻色數(shù)之間的關(guān)系，進(jìn)而利用有關(guān)平面圖和外可平面圖均勻色數(shù)的己知結(jié)論得到平衡二部劃分最大割的一些下界.特別的，證明了對于某些平面圖，Bollobás和Scott的猜想2.1.1成立. 引理6.4.1設(shè)G是一個有m條邊的圖，△(G)=△，若G有t-均勻著色，t是偶數(shù)，則f=(G)≥1/2t/t-1(m-△). 定理6.4.5設(shè)G是一個有m條邊的平面圖，△(G)=△，且δ(G)≥2，g(G)≥14，則f=

17、(G)≥2/3(m-△). 定理6.4.6設(shè)G是一個有m條邊的平面圖，|V(G)|是4的整數(shù)倍，且δ(G)≥2，g(G)≥14，則G存在平衡二部劃分V(G)=V1∪V2滿足max{e(V1)，e(V2)}≤m/3. 定理6.4.7設(shè)G是一個有m條邊的外可平面圖，△(G)=△≥3，則公式略. 定理6.4.8設(shè)G是一個2-連通的外可平面圖，g(G)≥4，則f=(G)≥2/3(m-△). 定理6.4.9設(shè)G是一個2-連通的外可平面圖，