论文部分内容阅读
平衡二部划分问题是图论的一个重要研究课题,本文研究了哈密尔顿平面图最小平衡二部划分上界的问题,主要证明了:哈密尔顿平面图G(V,E), |V| = n,1)若G(V,E)含有normal子图,则G(V,E)至少含有一个连续平衡二部划分V1,V2使得 e(V1,V2) ≤ n; 2)若 G(V, E)含有 h - normd 子图,则 G(V, E)至少含有一个平衡二部划分V1,V2使得e(V1,V2)≤n.