《图的平衡划分》由会员分享，可在线阅读，更多相关《图的平衡划分（88页珍藏版）》请在金锄头文库上搜索。
1、南京师范大学博士学位论文图的平衡划分姓名：颜娟申请学位级别：博士专业：基础数学指导教师：许宝刚20090428摘璎摘要本文研究有关图的平衡划分的一些问题设，垓是G的顶点集V(C)的一个忌戈0分，如果一llKIIl1，li，J忌，则称它是平衡的BollobSs和Scott在文献【13】中提出问题：给定图G，找G的顶点集v(c)的平衡划分，K使得maX_e()，e(K)最小特别地，他们提出了下述猜想：猜想211113】设G是一个最小度至少为2的图，则G存在顶点集v(c)的平衡二部划分，使得maX5X108，0(：)n一1，则存在G的二部划分V(C)=U使得e(，K)min情J+卧l掣j)如果Hn2
2、+Hk2l警p孽图是从+-中任思-v-去掉(竹j1)一(三)一(!)条边所得到的图如果I譬I+I等I摘要l掣I，则当k4时，极图是和K七的边不交的并；当尼=4时，极图是和致的边不交的并，或者和两个凰的边不交的并我们考虑n充分大时的有完美匹配的图得到下面这个定理：定理511设竹5108，0(：)sn一1，如果图G有m=(三)+(耋)条边，且G有完美匹酉己，则存在G的二部划分v(a)=VlU满足：(i)IflilI4k+8；(ii)e(，)minfI了n2l+I等l，l娥4l如果l百n2I+l了k2lI垃学I，则极图是从+-中任意去掉(njl)一(鸶)一(k2)条边并有完美匹配的图如果l百n2I+
3、l百k2ff巫#l，则当忌4时，极图是和Kk的边不交的并；当k4莳，破图皂哎和的边不交的并，或者和两个的边不交的并我们还具体研究了几个图类的公平平衡划分问题，得到以下结论：定理611设k3是奇数，G是一个边数为m的(k，七一1)双正则图假设G有n1个k度顶点那么v(a)存在一个平衡二部划分，使得(a)当ly(G)l是偶数时，maxe()，e()署一警；(b)当Iy(G)I是奇数时，maX【e()，e()署一警+譬定理612设k2是偶数，G是一个边数为m的(忌，k一1)双正则图假设G有佗2个k一1度顶点，那么v(a)存在一个平衡二部划分，场，使得(a)当Iy(G)I是偶数时，maXe()，e()
4、署+警；(b)当ly(G)I是奇数时，maxe(V1)，e()署+警+定理621设T是一个边数为m的树，如果diam(T)警+1，则T有一个平衡二部划分V(T)=U满足对于i1，2)，e(K)筹定理631设G为完全二部图m佗(a)当m和礼均为偶数时，取遍G的所有平衡二部划分v(a)=VlU，徽min糌酬刚哪=；竿雪喇nTheextremalgraphsareme铆。graphsobtainedbytakinganedgedisjointuni。n。fandKkifl譬J+l百k2J一XlAbstraet半l，and七4；andallgraphsobtainedbydeleting(n妄1)一(
5、：)一(!)edgesfrom珞+1iff百n2l+I譬lfQ趟4竺IIfk=4thentheextremalgraphsarcobtainedbyt描ngLallJedgeL-喇JointLunion占fandK4orandtwocopiesofKaInthispaper，weconsidersufficientlargegraphsthathaveperfectmatchingsTheorem511Let佗5108and0(；)n一1IfagraphGhas仇2(三)+(耋)edges，andGhasaperfectmatchingThenGadmitsabalancedbipartiti
6、onV(G1=HUsatisfying：(i)lJ一JIl冬4k+8and(；i)e(，)mtn1譬j+l等J，l垒jFurtherm。re，ifI了n2I+l了k2jI亟芋罡I，thentheex仃emalgraphsalegraphswithaperfectmatchingandobtainedbydeleting(几吉1)一(鸶)一(：)edgesfromKk+1ffl了n2I+蚓l她4I，thenwhenk4，theextremalgraphsarethe呐ographs晶t采ned、y讧远ane品edisjointunionofKIandKkIfk=4thenthee船emaLlgr
7、aphsareobtainedbytakinganedgedisjointunionofKnandK4orKnandtwocopiesof配Wealsostudybalancedjudiciouspartitionproblemsfor(忌，k一1)-biregulargraphs，treesandcompletebipartitegraphsThefollowingsareourmainresultsTheorem611Letk3beanoddintegerLetGbea(尼，k一1)-biregulargraphswith仇edgesIfGhasnlverticeswithdegreekT
8、henGadmitsabalancedbipartition纡，场suchthat(a)maXe()，e()予一警，iffy(G)Jiseven；(b)maxe(V1)，e(K)5署一等+譬，ifIy(G)lisoddTheorem612Let南2beallevenintegerLetGbea(k，k一1)-biregulargraphswithmedgesIfGhasn2verticeswithdegree七1ThenGadmitsabalancedbipartition纡，坯suchthat(a)maXlaibiIaibi，所以bi+Qai+di所以由(32。1)式，bt+caat+bli
9、+一c4+bi=rr9u若白Iaibilbiai，所以ai-4-也bi+c所以由(321)，ai4-diai+_bi+广c+一bi=孚则由(322)，几oe(谛，谇)譬+艺=等+吾，i=2。且I吁I=I吁I即定理成立口定理312的证明证明设V(H)=WU嵋是图日的一个平衡二部划分，满足e(W，昭)=丘(日)因为Iy(日)I是偶数，所以II=I昭I记V(G)v(n)=V不妨设IyI是偶数(若IyI是奇数，则给y加入一个新的孤立点)将y中的点两两配对，即令V”=u釜lVi，u)，对于iJ，Vi，un3m+3时，完全二部图n都不存在满足上述条件的平衡二部划分本章我们考虑这样的问题：满足什么条件的图存
10、在平衡二部划分v(a)=u，使得e(，v2)=厶(G)，同时maXe(vx)，e(v2)掣从Bollobis和Scott文献15】中的结果可以看出当(G)=6(G)时结论成立本章我们证明了当A(G)；6(G)时结论成立并将这个结论推广到掣的情况，其中2r4下面两个定理是本章的主要结果定理411设G是一个图，如果(G)；6(G)，那zG的任意一个使得e(，v2)=丘(G)的平衡二部划分，都满足e(K)e(G)3，i_1，2)从定理411和定理151可以看出，当(G)从；6(G)减少到J(G)时猜想211中的界由e(G)3减少到e(G)4事实上，下一个结论证明了类似的情形：当(G)从36(C)减少
11、到6(G)时，mal)(e()，e(K)的界由e(G)2减少到e(G)4注意到当r=2，3，4时，(7+4)(3r一4)的值分别为3，75，1一2l一筇4章最大平衔割与公平划分问题定理412设274是一个实数，G是一个图，如果当ly(G)I是偶数时(G)jr雨+4叭u，当Iv(a)l是奇数时A(G)鹦6(G)一百蕊4r，那么G的任意一个使得e(，)=丘(G)的平衡二部划分，耽都满足e(K)e(G)r，i1，2)42定理的证明首先证明三个引理设G是一个图，是G的顶点集v(a)的一个二部划分，对于J1，2)，i6(G)，6(G)+1，(G)，用nj，i表示所包含的i度点的个数不会产生混淆时，分别用
12、6和代替6(G)和(G)注意到对于6i，有0AiA一6对于J1，2)可得到如下简单结果：一6(a)唧，t=ni，At=I巧I；i=6i=0一6一占一6(b)i，At=，Ai一(Ai)nj，Ai(A一6)lyjl引理421和引理422是利用nj，估计e()的大小引理421设G是一个图，是G的顶点集v(a)的一个二部划分，则(i)e(G)=i1(AIV(G)I一inl，一i一n2，一i)；、0=ll=l7一占(ii)e()一e(y2)=丢i(n2，一inl，一i)会(1KlI1)证明由握手引理有2e(G)=i(n+n2，t)t=6一1=(礼1，t+n2，i)一(一i)(礼1，+n2，i)i=占讧=
13、6一占=A(IVlI+IV2I)一t(札“+n2，)t=1=Jy(G)I所以结论(i)得证因为所以A一占一占一inl小tin2-fi=li=l2e()+e(，)=2e()-4-e(，)=e()一e()=去i(n一九2，1)1。i=8溉mt=6，一艿=专(t)(礼蹦一n2A-i)。i=O=三(誊2小一蛐_+由结果(a)，结论(ii)得证A-8A一6札“一n2A-i)i=Oi=O口引理422设G是一个图，屹是G的顶点集y(G)的一个平衡二部划分满足e(，)=，-(G)对于勘y(G)，设如：=IN(v)nJl()nJ；t：maxtI幻)，则!：i)e()竽吲一笔in。，_；i=l(ii)e()学M一
14、三笔in2-；i=1证明-首先估计e()的大小注意到对于，如=IN(v)nIIN(v)nKIt，且IN(v)nKI+IN(口)nf=d)因此IN(v)nl垫乒，并且2e()=IN(v)nvE巧一23一岘两第4毒最大鼍7衙割与公习i划分问题TA+tn+学吼“+叶T5+t札6：竽吲一吾董吣“邮)。i=1所以结论(i)得证接下来估计e()的大小设Vl，且t。=t假设存在V2使得t。=IN(v2)nIIN(v2)nfe(G)lr，再由引理421(i)有三一A-6咖一A-6in2zl-i)(AIV(G)Ie(G)r，由引理421(i)有因此所以A一6A一6去(叭G)|-咖，-t一溉，-i)t=1i=1e(G)3特别地，此假设可推出e(M，)lN(v1)n1否则，对任意V，Ilv(v)nIlY(v)nI那么2e()=IN(v)n秽uIN(v)nK一二一I，一。VE=e(，)e(C)3，由引理421(i)和引理422(i)有An-Ap-6拍一A-6in2a-i)堕掣蚴)由(422)及引理421(ii)，e(咿e(咖去葚z(n2A_i-7。lA_i)一会Xe()一e()=专z()一了221因此由引理422(ii)，州，等孚一三Ap-52卜t+去A；-5i(n2A-i-7tIA-i)一会T
