运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2015年
1期
108-116
,共9页
judicious划分%平衡二部划分%最大度%最小度
judicious劃分%平衡二部劃分%最大度%最小度
judicious화분%평형이부화분%최대도%최소도
judicious bipartition%balanced bipartition%maximum degree%minimum degree
图G的顶点集V(G)的一个二部划分V1和V2叫做平衡二部划分,如果‖ V1 |-|V2‖≤1成立.Bollobás和Scott猜想:每一个有m条边且最小度不小于2的图,都存在一个平衡二部划分V1,V2,使得max{e(V1),e(V2)}≤m/3,此处e(Vi)表示两顶点都在Vi(i=1,2)中的边的条数.他们证明了这个猜想对正则图(即Δ(G)=δ(G))成立.颜娟和许宝刚证明了每个(k,k-1)-双正则图(即Δ(G)-δ(G)≤1)存在一个平衡二部划分V1,V2,使得每一顶点集的导出子图包含大约m/4条边.这里把该结论推广到最大度和最小度相差不超过2的图G.
圖G的頂點集V(G)的一箇二部劃分V1和V2叫做平衡二部劃分,如果‖ V1 |-|V2‖≤1成立.Bollobás和Scott猜想:每一箇有m條邊且最小度不小于2的圖,都存在一箇平衡二部劃分V1,V2,使得max{e(V1),e(V2)}≤m/3,此處e(Vi)錶示兩頂點都在Vi(i=1,2)中的邊的條數.他們證明瞭這箇猜想對正則圖(即Δ(G)=δ(G))成立.顏娟和許寶剛證明瞭每箇(k,k-1)-雙正則圖(即Δ(G)-δ(G)≤1)存在一箇平衡二部劃分V1,V2,使得每一頂點集的導齣子圖包含大約m/4條邊.這裏把該結論推廣到最大度和最小度相差不超過2的圖G.
도G적정점집V(G)적일개이부화분V1화V2규주평형이부화분,여과‖ V1 |-|V2‖≤1성립.Bollobás화Scott시상:매일개유m조변차최소도불소우2적도,도존재일개평형이부화분V1,V2,사득max{e(V1),e(V2)}≤m/3,차처e(Vi)표시량정점도재Vi(i=1,2)중적변적조수.타문증명료저개시상대정칙도(즉Δ(G)=δ(G))성립.안연화허보강증명료매개(k,k-1)-쌍정칙도(즉Δ(G)-δ(G)≤1)존재일개평형이부화분V1,V2,사득매일정점집적도출자도포함대약m/4조변.저리파해결론추엄도최대도화최소도상차불초과2적도G.
