离散数学及其应用教育部重点实验室工作总结报告.doc

1、离散数学及其应用教育部重点实验室工作总结报告（2011 年 3 月 18 日）实验室名称： 离散数学及其应用教育部重点实验室 主管部门： 福建省教育厅依托单位： 福州大学实验室概况: 在迅速发展的计算机科学技术及信息技术等领域，离散数学是重要的基础学科和支撑学科，它的发展和应用是影响一个国家科学技术发展水平的重要因素。以福州大学“离散数学与理论计算机科学研究中心”为依托的离散数学及其应用教育部重点实验室于 2007 年 7 月获教育部批准立项建设。目前，实验室共有固定研究人员 27 人，其中教授 16 人，副教授 4 人。实验室由马志明院士担任学术委员会主任，范更华教授担任实验室主任。实验室位

2、于福州大学铜盘校区。2007 年 11 月完成了实验室装修一期工程；2009年 3 月完成了二期装修工程，达到 “环境优美、设备一流” 。按国际研究所标准建设基础设施，为每位研究人员及来访学者提供 40 平米宽敞办公室及一流科研设备。为每位研究生提供一个工作位及台式电脑。已建成无线网覆盖实验室 3000 平米的科研、办公场所。重视网络建设，保证网络高速畅通。订购相关专业的国外数据库及原版图书，已基本建成一流的专业图书资料室。一、 实验室现有三个研究方向：图论与组合数学、大规模集成电路设计中的数学方法、优化理论与算法。二、 在本年度，实验室主任范更华教授获全国优秀科技工作者。实验室在研科研项目国

3、家 973 计划课题 1 项，国家自然科学基金7 项，其中重点项目 1 项，面上项目 6 项，新增国家 973 计划课题 1 项，为1. 大规模集成电路物理设计中关键应用数学理论和方法（2011CB808003） ，范更华 新增国家自然科学基金 3 项，其中面上项目 2 项，青年项目 1 项，分别是：1. 超大规模集成电路多目标划分的算法研究（61070020） ，朱文兴，国家基金面上项目。2. 近景摄影测量中的自动图像分割技术（11071270） ，王美清，国家基金面上项目。3. 几类图染色问题的研究（11001055） ，侯建锋，国家基金青年项目。实验室在 2010 年 8 月顺利完成了国

4、家重点基础研究发展计划（973 计划）课题“大规模集成电路设计中的图论与代数方法（2006CB805904） ”。课题实施期间，课题组共发表研究论文 133 篇，其中被 SCI 收录 104 篇；由于出色完成了该课题，我们将继续承担新一轮的 973课 题 ： 大规模集成电路物理设计中关键应用数学理论和方法（2011 年 1 月至 2015 年 12 月）。三、 实验室不仅是高水平科学研究中心，也是高层次人才培养基地。实验室以应用数学、计算机应用技术省级重点学科，国家集成电路人才培养基地，离散数学“211 工程”建设重点学科，应用数学博士点以及两个一级学科硕士点（数学、计算机科学与技术）为支撑，

5、形成具有一定规模的离散数学高层次人才培养体系。实验室将充分利用自身的条件，围绕主攻方向，提升开放层次，促进学术交流与合作，使实验室整体研究水平达到国内领先水平，某些研究方向达到国际先进水平，为国家及福建地方建设做出突出贡献。本年度培养博士研究生 2 名，硕士研究生 21 名。四、 年度科研成果实验室在各个研究问题方面开展了深入地研究工作，在课题研究中取得了一些很好的研究结果。本年度课题组研究成员在国内外重要专业刊物上发表 SCI 收录论文 27 篇， EI 收录论文 6 篇，具体研究成果如下：（1）图论与组合研究工作关于连通图支撑树的计数问题，给出了连通图支撑树个数的紧的上界，并且考虑的连通度

6、为 k 的图的支撑树的个数，同时给出了连通图支撑树的个数和图色数之间的关系，其结果发表在Applied Mathematics Letters上。一个图的 Laplacian 谱半径是指该图 Laplacian 矩阵的最大特征值，对于图 n 个顶点，最大度为，直径为 D 的非正则图，Shi给出了该图的 Laplacian 谱半径的上界，我们改进了该上界，并且证明了该上界给出了在某些情况是紧的，同时，给出了不含三角形图的 Laplacian 谱半径的上界。对于连通二部图，给出了Laplacian 谱半径紧的上界和下界，从而改进了 Shi 的结果。在图染色领域，考虑了图的列表染色问题，给出了考虑图

7、列表染色的新的思路，并且用该思路证明了某些形式的完全 k 部图是(2, 2)-total weight choosable，并证明了除了一条边外的所有完全二部图都是(1, 2)-total weight choosable。研究了稀疏图和平面图的列表全染色问题，证明了如果平面图的最大度不超过 8，则其列表全色数不超过 11；如果平面图最大度至少是 8，且不含 5-圈，则其列表全色数等于最大度加一；如果图的最大度是 4，并且最大平均度不超过 3，则其列表全色数是 5，该项成果发表在Information Processing Letters上。考虑了有向图博弈染色，给出了有向图博弈色数以及弱的博

8、弈色数的定义，证明每个定向平面图的博弈色数不超过 9，每个定向外平面图的博弈色数不超过4，同时研究了有向图强博弈染色，证明了每个定向平面图的强博弈色数不超过 16。考虑的外平面图的无圈边染色问题，完全确定了外平面图无圈边色数的上界，其结果发表在Journal of Graph Theory上。在化学图论方面，一个图的能量是指该图所有特征值绝对值的和，一个图的能量小于图的顶点数，称该图是 hypoenergetic，我们研究了图的能量，构造了顶点数为 4n+2 的树 T，使得 T 是hypoenergetic，从而验证了 Gutman 等人在 2008 年提出的猜想，该文发表在Applied M

9、athematics Letters上。同时考虑的图的能量和 Estrada 指标之间的关系，给出了图 Estrada 指标紧的上界。（2）VLSI 中的图论与优化算法研究工作为了开展大规模集成电路设计领域的研究工作，实验室于 2010年建立了一个 150m2 的大规模集成电路设计 EDA 实验室，拥有 16 个研究工作位，装备国产熊猫 EDA 系统软件 16 台套，对所有实验室研究成员和研究生开放使用。布局是大规模集成电路电路设计重要环节，决定了超大规模集成电路芯片的性能，尺寸，产量和可靠性，我们给出了基于粒子群优化算法新的智能决策，利用该决策可以超大规模集成电路较快的获得一个可行的电路物理

10、布局。同时在遗传算法的变异和交叉的原则中引入了粒子群优化算法，可以使得该算法脱离局部最优和实现更好的多样性。实验通过采用 MCNC 和 GSRC 基准测试表明，该算法是有效的。同时该算法可以避免局部最小，并有很好的收敛性。实验结果表明所提出的方法可以大大帮助集成电路设计中的布局决策，其结果发表在Soft Comput.上。从计算的角度来看，超大规模集成电路布局规划是一个 NP-困难问题。我们给出了非分层和模块 VLSI 布图规划问题的一个混合演化算法（HGA） ，该算法使用一个有效的遗传搜索方法来探索搜索空间和一种有效的局部搜索方法，利用信息在搜索区域。MCNC 基准的实验结果表明该算法是有效

11、的。同时，借助于进化算法和模拟退火算法的概念，给出了另外一种混合演化算法，实验表明该算法也是有效的。（3）优化理论与算法我们提出了一个高效求解三维装箱问题（Three Dimensional Container Loading Problem 3D-CLP）的混合模拟退火算法；研究了极大可满足性问题的局部搜索算法，提出了用单纯形法产生“初始概率”(每个变量取 1 的概率)，用“初始概率”对局部搜索算法中变量的初始随机指派进行适当的约束；研究了箱约束非线性整数规划问题，提出了该问题的离散动态凸化算法，同时还证明了算法的收敛性；对非线性约束连续全局优化问题，我们构造一个结合罚函数的辅助函数，构造了

12、解非线性约束连续全局优化的一个动态凸化算法，该算法避免了传统罚函数法中罚参数选取困难的问题。五、 学术交流为推动福建省数学教育和研究活动开展，在范更华教授的大力倡导下，协同福建省数学会，于 2010 年 10 月 16 日至 17 日召开福建省首届数学大会，1100 多名来自全省各地高校和中学的数学教师参会。为了使基层农村学校数学教师有机会参加会议，在省政府、省教育厅等部门的大力支持下，会议为 300 名工作在乡镇学校的教师提供了交通、住宿等经费支持。会议期间， “院士与中学教师互动座谈会”和“专家讲座”等专项活动交流和讨论热烈，这种面对面的交流让来自中小学的数学教师受益匪浅、耳目一新，为广大基层学校特别是农村学校教师提供了良好的学习机会，有效地调动了全省中学教师参与数学研究的积极性，对提升福建省数学教育水平起到了积极的推动作用。2010 年 5 月，实验室协同中国运筹学会，召开中国运筹学会第八届三次常务理事会。在本年度，共有 10 余位国内外知名学者到校访问，并作报告和进行合作研究，其中包含千人计划入选者，浙江师范大学教授朱绪鼎，香港浸会大学数学系主任朱力行，加拿大 Simon Fraser 大学教授 Pavol Hell 等。