图的若干参数及算法研究

图的控制数与染色数是图的两个重要参数，在现代计算机科学、信息科学、管理科学等领域有着十分广泛的应用，得到了国内外同行的极大关注。本项目研究图的各种控制数、染色数及其算法，如图的控制数、符号控制数、减符号控制数、图的平方染色、Harmonious染色等。围绕著名的Vizing's猜想和Haynes猜想展开对图的控制数、Harmonious染色的重点研究，力争完全解决Haynes猜想，扩展满足Vizing猜想的图类。给出图的控制数、平方色数、Harmonious色数一些可达的界，对于一些特殊图类计算出符号控制数、平方色数、Harmonious色数的精确值，并设计高效可行的近似多项式时间算法。给出图与其补图的全符号控制数、减符号控制数、Harmonious色数的Nordaus-Gaddum不等式。拟四年内完成论文至少20篇.

图的控制数与标号是图的重要参数，在现代计算机科学、信息科学、管理科学等领域有着十分广泛的应用。本项目基本上按原项目计划执行，四年来，项目组成员主要研究图的控制数、图的符号控制数、图的减符号控制数、图的边符号控制数、图的团符号控制数、图的L（p,q)-标号、图的L（2,1)-标号、图论算法及其应用等问题。证明了四正则图、五正则图和K正则图的Upper减控制数的下界，且这些界是可达的，构造出了满足下界的图类；定义了图的团符号控制数，构造出了一般图的团符号控制函数，证明了一般图的团符号控制函数的界，并对一些特殊图类，得到了它们的团符号控制数的精确值，这些结果丰富改进了图的控制理论现有的研究结果，拓展了图的控制理论的研究范围。以G.Wenger 猜想为主要目标，研究图的L（p,q)-标号，力求改进M.Molloy 和 M.R.Salavatipour 给出的上界，扩展满足G.Wenger 猜想的图类，得到了不含4-9圈的平面图的L（p,q）-标号、围长至少为6的平面图的L（p,q）-标号、最大度至多为6的的平面图的L（2,1）-标号，证明了不含4、5、6 圈且无两个相交三角形的平面图满足Wenger 猜想，证明了不含4圈的平面图满足Wenger 猜想。利用图的控制理论和染色理论，研究了交巡警台优化设置问题、社会复杂网络成员影响力评价、破损文件的拼接复原等具有较大社会意义和经济意义的实际问题。利用图论最短路算法和和控制数优化算法给出了交巡警台的优化设置方案，基于图的TSP算法的改进，给出了一种高效可行的破损文件的拼接复原的新算法，基于图的控制理论，研究社会复杂网络成员影响力测量问题，设计了一种快速可行的算法并且在Erdos合作网络上得到了实现。这些算法不但从理论上丰富了理论计算机研究领域的研究内容，有一定的理论意义，而且能够在实践中应用，有一定的社会价值和经济价值。