有向图的公平划分问题研究

项目名称： 有向图的公平划分问题研究

项目编号： No.11626036

项目类型： 专项基金项目

立项/批准年度： 2016

项目学科： 数理科学和化学

项目作者： 徐鑫

作者单位： 北方工业大学

项目金额： 3万元

中文摘要： 图的划分是图论研究的重要组成部分，近年来图的公平划分问题成为了领域内的热点和难点课题。本项目拟从有向图的结构性质入手，综合应用极值理论、组合优化、概率方法等数学工具，研究有向图的公平划分问题。围绕Scott提出的有向图划分的猜想，力争刻画有向图在公平二部划分下子集之间弧的数目，给出弧数目的下界和对应的极图；研究某些特殊类型的有向图，如无圈有向图的公平划分问题。拟在1年内完成学术论文3篇左右，其中1篇发表在SCI可检索的期刊上。

中文关键词： 公平划分；有向图；超图；圈结构；

英文摘要： Graph partitioning theory is an important branch of graph theory research. In particular, judicious partitioning problems on graphs have attracted considerable attention in the latest decades. In this project, through analyzing the structural properties o

英文关键词： judicious partition；digraph；hypergraph；cycle；