二部图平衡二部划分的上界
Upper Bounds On Minimum Bisections Of Bipartite Graphs作者机构：南京工业大学浦江学院基础教学部
出 版 物：《数学的实践与认识》 (Mathematics in Practice and Theory)
年 卷 期：2019年第49卷第24期
页 面：167-171页
学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学]
基 金：江苏省高校自然科学基金(18KJB110014) 2018年南京工业大学浦江学院科研重点项目(njpj2018-1-03) 江苏省高校自然科学基金(16KJB110011)
摘 要：设G(V,E)是一个图,V1,V2是V的一个二部划分,当||V1|-|V2||≤1时,称V1,V2是V的一个平衡二部划分,用e(V1,V2)表示一条边的两个端点在不同划分里边的总数目.最小平衡二部划分是指寻找G(V,E)的一个平衡二部划分使得e(V1,V2)最小.研究了二部图和哈密尔顿二部图,得到它们的最小平衡二部划分的上界分别为[m/2]和(n+2)/2.
维普期刊数据库
同方期刊数据库