图与超图若干划分问题的研究

In network design，many problems can be identified as the problems of graph or hygergraph partition. For example，the analysis of community structure in complex networks and the very large scale integrated circuit partitioning problem. The studies of the above problems not only is closely related to the development of computer science，network，modern information science and technology，but also has an important influence over the development of graph theory. We have been engaged in the work of graph theory，algorithms and theirs application for a long time and obtained a series of achievements. In this project，we will study some main problems in graph and hypergraph partition. Specifically，we will consider the Max-Cut problem of graphs and confirm the conjecture about Max-Cut of graphs with large girth posed by Alon et al.. Combining probabilistic methods and techniques of Combinatorics, we will investigate judicious partition problems of graphs and hypergraphs, and give the new ideas to study the hypergraph partition problems. We also discuss the digraph partition problems and design the effective algorithms of community analysis and circuit partitioning in VLSI. We hope to make a great breakthrough and promote the development of related problems through the study of the project.

网络设计中的许多问题都可以转化为图与超图的划分问题，例如复杂网络的社团分析、大规模集成电路的划分问题,这些问题的研究不仅与计算机学科、网络、现代信息科学与技术等学科的发展密切相关，并对之产生重要影响，而且在图论中具有影响整个学科发展的重要地位。本课题申请人和研究人员长期从事图论与算法及其应用领域研究工作,取得了一系列的研究成果。本项目主要利用随机方法和组合方法，对图与超图划分中的几个主要问题进行研究。具体的说，研究图的最大割问题，解决Alon等人提出的关于围长较大的图的最大割猜想；将随机方法与组合技巧相结合，研究图与超图的公平划分，给出超图划分问题研究的新的思路；研究有向图的划分问题；设计图划分的有效算法，并将其应用到社团划分和大规模集成设计上。计划将通过本项目拟定的各个课题研究，在图与超图划分理论和方法上取得较大突破。

网络设计中的许多问题都可以转化为图与超图的划分问题，例如复杂网络的社团分析、大规模集成电路的划分问题,这些问题的研究不仅与计算机学科、网络、现代信息科学与技术等学科的发展密切相关，并对之产生重要影响，而且在图论中具有影响整个学科发展的重要地位。本项目主要从事图论及其应用研究，解决了图与超图划分领域的多个猜想和公开问题，取得的主要创新成果如下：.1.构建了基于概率方法的图与有向图公平划分新方法，解决了若干公开问题和重要猜想.将概率方法、图的结构分析、优化理论等方法相结合，创造性地给出了图与有向图划分研究新方法，解决了Bollobas等人提出的关于图k-部划分性质的猜想和公开问题；回答了Bollobas等人在图平衡划分领域的问题；在有向图双向割方面的Lee-Loh-Sudakov猜想上取得突破性进展；给出了定向图半度条件下双向割紧的下界。.2.完善了图划分的移点技术，并引入了超图划分的移点技术.移点技术是图划分最基本技术之一，因超图结构的复杂性，移点技术在超图领域难以应用，本项目将图的结构分析与概率方法相结合，完善了图的移点技术，证明了图k-部划分领域的Ma-Yu猜想；给出了基于概率方法的超图划分移点技术，并利用该技术在超图划分基本猜想上取得突破性的进展；将一致超图的移点技术应用到非一致超图划分上，解决了1,2-超图上的Bollobas-Scott猜想。.3.给出了估计最大割的Ramsey方法，并将其应用到现代信息通讯中.利用Ramsey理论，给出了Alon等人在2005年提出的不含偶圈图的最大割猜想的唯一进展；将Erdos最大割的结果推广到最大平衡割上。.发表SCI检索论文18篇。召开专业学术研讨会5次，邀请国内外学术专家100余人次。培养硕士研究生12人，博士研究生5人。