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

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 of digraphs, we will study judicious partitions of digraphs, using extremal techniques, combinatorial optimization and probabilistic methods. Aiming at the Scott conjecture on digraphs, we will study the number of arcs between each part and improve the currently known lower bound. Moreover, we will discuss judicious partitions of acyclic digraphs and other special digraphs. At least three papers are completed after the project is finished, one of which is indexed by SCI.

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

图的公平划分问题是图划分的重要内容，更是当前图论研究领域内的热点课题。项目通过综合运用极值理论、组合优化、概率方法等工具，结合图的拓扑结构性质，研究有向图的公平二部划分问题，刻画二部划分下子集之间弧的数目，给出相应的下界；研究某些特殊有向图的公平划分问题，并给出了相关参数的表达形式；定义了超图中的圈结构，刻画了圈结构与超图拓扑结构之间的对应关系，给出了圈的存在性定理。上述结果丰富了相关领域的研究工作，为进一步的研究提供了理论依据。