English

运筹学学报 ›› 2020, Vol. 24 ›› Issue (3): 161-166.doi: 10.15960/j.cnki.issn.1007-6093.2020.03.013

• • 上一篇    

哈密尔顿平面图最小平衡二部划分的上界

陈涛*   

  1. 南京工业大学浦江学院, 南京 211112
  • 收稿日期:2018-08-14 发布日期:2020-09-05
  • 通讯作者: 陈涛 E-mail:3237479269@qq.com
  • 基金资助:
    江苏省高校自然科学基金（No.18KJB110014）

Upper bounds on minimum balanced bipartition of Hamilton plane graphs

CHEN Tao*   

  1. Nanjing Tech University Pujiang Institute, Nanjing 211112, China
  • Received:2018-08-14 Published:2020-09-05

PDF

126

摘要： 设$G（V，E）$是一个图，$V_{1}，V_{2}$是$V$的一个二部划分，用$e（V_{1}，V_{2}）$表示一条边的两个端点在不同划分里边的总数目，当$||V_{1}|-|V_{2}||\leq 1$时，称$V_{1}，V_{2}$是$V$的一个平衡二部划分。最小平衡二部划分是指寻找$G（V，E）$的一个平衡二部划分使得$e（V_{1}，V_{2}）$最小。对于哈密尔顿平面图$G（V，E）$，研究了当Perfect-内部三角形最大边函数值与最小边函数值之差为$d$时，$e（V_{1}，V_{2}）$最小值的上界与$d$之间的关系。

关键词: 平面图, 哈密尔顿圈, 平衡二部划分

Abstract: A balanced bipartition of a graph $G(V,E)$ is a bipartition $V_{1}$ and $V_{2}$ of V(G) such that $||V_{1}|-|V_{2}||\leq 1$. The minimum balanced bipartition problem asks for a balanced bipartition minimizing $e(V_{1},V_{2})$, where $e(V_{1},V_{2})$ is the number of edges joining $V_{1}$ and $V_{2}$. In this paper, for Hamilton plane graphs, we study the relation between upper bounds on the minimum of $e(V_{1},V_{2})$ and $d$, which is the difference between the maximum edge function value and the minimum edge function value of Perfect-inner triangle.

Key words: plane graph, Hamilton cycle, balanced bipartite bipartition

中图分类号: