| 王建芸,徐正华.分离三圈不相交的极大平面图上的平衡二部划分猜想的一个证明[J].南华大学学报(自然科学版),2025,(1):82~87.[WANG Jianyun,XU Zhenghua.A Proof of the Balanced Bipartition Conjecture on Maximal Planar Graphs with Disjoint Separating 3-cycles[J].Journal of University of South China(Science and Technology),2025,(1):82~87.] |
| 分离三圈不相交的极大平面图上的平衡二部划分猜想的一个证明 |
| A Proof of the Balanced Bipartition Conjecture on Maximal Planar Graphs with Disjoint Separating 3-cycles |
| 投稿时间：2024-08-02 |
| DOI： |
| 中文关键词: 平面图 平衡划分 分离三圈 极图 |
| 英文关键词:planar graph balanced bipartition separating 3-cycle pole graph |
| 基金项目: |
|
| 摘要点击次数: 0 |
| 全文下载次数: 1 |
| 中文摘要: |
| 关于平面图的平衡二部划分问题的研究有一个猜想:若图G是一个拥有n个顶点的简单平面图,那么图G必定含有一个平衡二部划分V1,V2,使得e(V1,V2)≤n。平衡二部划分可应用于算法设计、电路设计等诸多领域。本文利用寻找划分圈的方法证明了分离三圈不相交的极大平面图G含有一个平衡二部划分V1,V2,使得e(V1,V2)≤n,并且这个结论也适用于它的生成子图。 |
| 英文摘要: |
| Research on the problem of balanced bipartition of planar graphs has a conjecture:if graph G is a simple planar graph with n vertices, then the graph must contain a balanced bipartition V1,V2, such that e(V1,V2)≤n. Balanced bipartition can be applied in many fields such as algorithm design and circuit design. This article uses the method of finding partitioning cycles to prove that a maximal planar graph G with disjoint separating 3-cycles contains a balanced bipartition V1,V2, such that e(V1,V2)≤n, and this conclusion also applies to its generating subgraphs. |
| 查看全文 查看/发表评论 下载PDF阅读器 |
| 关闭 |
|
|
|