论文部分内容阅读
本文研究有关图的平衡划分的一些问题.
设V1,...，Vk是G的顶点集V(G)的一个k-划分，如果-1≤|Vi|-|Vi|≤1，1≤i，j≤k，则称它是平衡的.Bollobás和Scott在文献[13]中提出问题：给定图G，找G的顶点集V(G)的平衡划分Vi,...,Vk使得max{e(V1),...,e(Vk)}最小.特别地，他们提出了下述猜想：
猜想2.1.1[13]设G是一个最小度至少为2的图，则G存在顶点集V(G)的平衡二部划分V1，V2使得max{e(V1)，e(V2)}≤|E(G)|/3.
Bollobás和Scott在文献[15]中讨论了正则图的公平平衡划分问题.
定理1.5.1[15]设k≥2是整数，G是一个边数为m的k-正则图，则G存在一个平衡二部划分V(G)=V1ＵV2使得(a)当k是奇数时，max{e(V1)，e(V2)}≤k-1/4km；(b)当k和|V(G)|都是偶数时，max{e(V1)，e(V2)}≤1/4k/k+1m；(c)当k是偶数，|V(G)|是奇数时，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.
他们的结果说明猜想2.1.1对正则图是成立的.
我们几乎完全解决了这一猜想.我们证明了这个猜想对所有平均度大于或等于6的图都成立.实际上，我们给出了平衡划分max{e(V1)，e(V2)}的一个上界.这个界对于偶数个点的星图是最好可能的.并且对于任意一个给定的图，我们的证明表明可以在多项式时间内找到满足定理条件的平衡二部划分.
定理2.1.1设G是一个有n个点，m条边的图，则G存在平衡二部划分V(G)=V1∪V2满足e(V1，V2)≥m/2，且(1)如果n是偶数，则max{e(V1)，e(V2)}≤m/4+△(G)-δ(G)/4；(2)如果n是奇数，则max{e(V1)，e(V2)}≤m/4+△(G)+1/4.
下面的推论2.1.1说明对于平均度至少是6的图猜想2.1.1成立.推论2.1.2回答了Bollobás和Scott[13]提出的一个问题：满足什么条件的图存在平衡二部划分，使得每个点集导出子图所包含的边数都不超过(1+0(1))m/4?或许△(G)=0(n)或者当n→∞时δ(G)→∞就足够了. 推论2.1.1设G是一个平均度至少是6的图，则G存在顶点集V(G)的平衡二部划分V1，V2使得max{e(V1)，e(V2)}≤|E(G)|/3.
推论2.1.2设G是一个有m条边，n个点的图，如果△(G)=o(n)或者当n→∞时δ(G)→∞，则G存在顶点集V(G)的平衡二部划分V1,V2使得max{e(V1)，e(V2)}≤(1+0(1))m/4.
Bollobás和Scott在文献[13]中提出问题：对于平衡划分问题，是否能找到与一般最大割问题中Edwards界类似的结论?我们完整的回答了这一问题.我们用图的边数和最大匹配数α(G)给出平衡二部划分最大割的一个下界，并证明了这个界是最好可能的.由于求α(G)是有多项式时间算法的(见文献[25，51]).从定理的证明可以看出寻找达到这个界的平衡二部划分有多项式时间算法.令f=(G)=max{e(V1,V2)|V(G)=V1∪V2是G的平衡二部划分}.则有：
定理3.1.1设G是一个有m条边的图，最大匹配数为α(G)，则f=(G)≥m/2+α(G)/2.
用类似定理3.1.1的证明方法，我们证明了下面的定理：
定理3.1.2设G是一个图，H是G的导出子图，且|V(H)|是偶数，则f=(G)≥f=(H)+1/2(|E(G)|-|E(H)|).
受到猜想2.1.1和定理3.1.1的启发，很自然地有这样的问题：满足什么条件的图存在平衡二部划分V(G)=V1∪V2，使得e(V1,V2)=f=(G)的同时也满足Bollobás和Scott猜想中的要求max{e(V1)，e(V2)}≤|E(G)|/3通过研究，我们有下面的结论，其中e(G)=|E(G)|.
定理4.1.1设G是一个图，如果△(G)≤7/5δ(G)，则G的任意一个使得e(V1，V2)=f=(G)的平衡二部划分V1,V2都满足e(Vi)≤e(G)/3，i∈{1，2}.
定理4.1.2设2≤r≤4是一个实数，G是一个图，如果当|V(G)|是偶数时△(G)≤r+4/3r-4δ(G)；当|V(G)|是奇数时△(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}.
Bollobás和Scott在文献[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」，则当k≠4时，极图是Kn和Kk的边不交的并；当k=4时，极图是Kn和K4的边不交的并，或者Kn和两个K3的边不交的并.我们考虑n充分大时的有完美匹配的图.得到下面这个定理：
定理5.1.1设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」}如果「n2/4」+「k2/4」≥「(n+1)2/4」，则极图是从Kn+1中任意去掉(n+12)-(n2)-(kn)条边并有完美匹配的图.如果「n2/4」+「k2/4」≤「(n+1)2/4」，则当k≠4时，极图是Kn和Kk的边不交的并；当k=4时，极图是Kn和K4的边不交的并，或者Kn和两个K3的边不交的并.
我们还具体研究了几个图类的公平平衡划分问题，得到以下结论：
定理6.1.1设k≥3是奇数，G是一个边数为m的(k，k-1)-双正则图.假设G有n1个k度顶点.那么V(G)存在一个平衡二部划分V1，V2使得(a)当|V(G)|是偶数时，max{e(V1)，e(V2)}≤m/4-n1/8；(b)当|V(G)|是奇数时，max{e(V1)，e(V2)}≤m/4-n1/8+k-1/8.
定理6.1.2设k≥2是偶数，G是一个边数为m的(k，k-1)-双正则图.假设G有n2个k-1度顶点，那么V(G)存在一个平衡二部划分V1，V2，使得(a)当|V(G)|是偶数时，max{e(V1)，e(V2)}≤m/4+n2/8；(b)当|V(G)|是奇数时，max(e(V1)，e(V2)}≤m/4+n2/8+k/8.
定理6.2.1设T是一个边数为m的树，如果diam(T)≥m/3+1，则T有一个平衡二部划分V(T)=V1∪V2满足对于i∈{1，2}，e(Vi)≤m/3.
定理6.3.1设G为完全二部图Km,n,m≤n.(a)当m和n均为偶数时，取遍G的所有平衡二部划分V(G)=V1∪V2，公式略.(b)当m和n均为奇数时，取遍G的所有平衡二部划分V(G)=V1∪V2，公式略.(c)当m是奇数，n是偶数时，取遍G的所有平衡二部划分V(G)=V1∪V2，公式略.(d)当m是偶数，n是奇数时，取遍G的所有平衡二部划分V(G)=V1∪V2，公式略.
定理6.3.2设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.
我们用随机的方法讨论了图的平衡二部划分与均匀色数之间的关系，进而利用有关平面图和外可平面图均匀色数的己知结论得到平衡二部划分最大割的一些下界.特别的，证明了对于某些平面图，Bollobás和Scott的猜想2.1.1成立.
引理6.4.1设G是一个有m条边的图，△(G)=△，若G有t-均匀着色，t是偶数，则f=(G)≥1/2t/t-1(m-△).
定理6.4.5设G是一个有m条边的平面图，△(G)=△，且δ(G)≥2，g(G)≥14，则f=(G)≥2/3(m-△).
定理6.4.6设G是一个有m条边的平面图，|V(G)|是4的整数倍，且δ(G)≥2，g(G)≥14，则G存在平衡二部划分V(G)=V1∪V2满足max{e(V1)，e(V2)}≤m/3.
定理6.4.7设G是一个有m条边的外可平面图，△(G)=△≥3，则公式略.
定理6.4.8设G是一个2-连通的外可平面图，g(G)≥4，则f=(G)≥2/3(m-△).
定理6.4.9设G是一个2-连通的外可平面图，|V(G)|是4的整数倍，且g(G)≥4，则G存在平衡二部划分V(G)=V1∪V2满足max{e(V1)，e(V2)}≤m/3.
论文的最后我们列出一些关于平衡划分的可进一步研究的问题.