下载文档原格式
离散数学及其应用教育部重点实验室工作总结报告（2011年3月18日）实验室名称：离散数学及其应用教育部重点实验室主管部门：福建省教育厅依托单位：福州大学实验室概况: 在迅速发展的计算机科学技术及信息技术等领域，离散数学是重要的基础学科和支撑学科，它的发展和应用是影响一个国家科学技术发展水平的重要因素。
以福州大学“离散数学与理论计算机科学研究中心”为依托的离散数学及其应用教育部重点实验室于2007年7月获教育部批准立项建设。
目前，实验室共有固定研究人员27人，其中教授16人，副教授4人。
实验室由马志明院士担任学术委员会主任，范更华教授担任实验室主任。
实验室位于福州大学铜盘校区。
2007年11月完成了实验室装修一期工程；2009年3月完成了二期装修工程，达到“环境优美、设备一流”。
按国际研究所标准建设基础设施，为每位研究人员及来访学者提供40平米宽敞办公室及一流科研设备。
为每位研究生提供一个工作位及台式电脑。
已建成无线网覆盖实验室3000平米的科研、办公场所。
重视网络建设，保证网络高速畅通。
订购相关专业的国外数据库及原版图书，已基本建成一流的专业图书资料室。
一、实验室现有三个研究方向：图论与组合数学、大规模集成电路设计中的数学方法、优化理论与算法。
二、在本年度，实验室主任范更华教授获全国优秀科技工作者。
实验室在研科研项目国家973计划课题1项，国家自然科学基金7项，其中重点项目1项，面上项目6项，新增国家973计划课题1项，为1.大规模集成电路物理设计中关键应用数学理论和方法（2011CB808003），范更华新增国家自然科学基金3项，其中面上项目2项，青年项目1项，分别是：1.超大规模集成电路多目标划分的算法研究（），朱文兴，国家基金面上项目。
2.近景摄影测量中的自动图像分割技术（），王美清，国家基金面上项目。
3.几类图染色问题的研究（11001055），侯建锋，国家基金青年项目。
实验室在2010年8月顺利完成了国家重点基础研究发展计划（973计划）课题“大规模集成电路设计中的图论与代数方法（2006CB805904）”。
开题报告信息与计算科学哈密顿图的判定与应用一、综述本课题国内外研究动态, 说明选题的依据和意义图论(graphic theory)是一门既古老又年轻的学科. 它诞生于18世纪上半叶. 到19世纪下半叶这个领域才发展成为数学的一个系统的分支, 直到20世纪上半叶, 这门学科才有自己的著作出现. 自20世纪下半叶开始, 随着计算机科学与技术的发展, 图的理论研究和应用研究才得到迅速广泛的重视, 图论作为一个数学的分支, 才真正确立了自己的地位. 哈密顿(爱尔兰科学家)在1859年提出一个名叫“周游世界”游戏问题是: 能否遍历正12面体的每个顶点一次且一次后回到原地. 由此引申出哈密顿图的定义: 如果图上有一条G 经过图所用顶点一次且仅一次的回路, 则称此回路为哈密顿回路, 具有哈密顿回路的图G 称为哈密顿图.哈密顿图具有六个领域: 哈密顿圈, H 连通, 泛圈, 点泛圈, 边泛圈, 泛连通. 哈密顿图是有哈密顿圈的图. 至今没有一个像欧拉图的充要条件那样的“非平凡的”(不是定义的同义反复)关于哈密顿图、哈密顿通路的充分必要条件, 但关于他们的充分性和必要性分别有一些研究成果. 而哈密顿图不光在金字塔图、扇面蜂巢图及马图上有体现它性质的研究, 且在四正则连环图和彼得森中有它独特的应用.而且哈密顿图在哈密顿通路、哈密顿轨、多哈密顿轨问题上也有很多细致的研究和应用.1984年时在连续10年排名加拿大第一大学的范更华教授得到名垂青史的“范定理”: 2连通阶图的距离是2的任意两点均有, 则是有圈, n G ,x y max{(),()}/2d x d y c ≥G c 当时是哈密顿图. 当然, 关于如此著名的范定理, 各国不少专家也对范定理企求做出c n =改进发展. 1987年Wojda 院士和欧洲最古老的著名大学之一的法国奥大的运筹学科创建奠基人Benhocine 教授2人合作仅局部推广上面范定理. 又如法国 Benhocine 教授1977年发表在法国科学院学报的哈密顿图论文就一直有国际影响, 但他至今仅有25篇数学论文且18篇是哈密顿图的, 他是排名哈密顿图研究前30名大师之一.哈密顿图已经历了一个多世纪的跋涉, 容易攀登的时代已经过去了, 其进展已非常不容易, 如此即使是世界级的大师泰斗, 不论你多么聪明利害都好, 面对的下一个问题猜想都永远是相关学科的全世界的专家经过多年仍不能解决的, 就是想做点进展都非常不容易, 每一篇论文都是超越最权威大师的成果. 哈密顿图的难如两个权威说“非常不容易”. 但它却具有重大历史意义以及广泛而重要的应用价值.现国际数学联盟主席是哈密顿图权威, 并且琼州大学赵克文和美国权威等合作改进耶鲁大学Ore 院士等大师权威的代表性结果已在“哈密顿图”居世界领先.在国内, 宁宣熙和宁安琪提出了哈密顿圈自组织算法的实证研究结果和其在哈密顿图判定上的应用, 介绍了SOA 算法在大约 12000个规模不同()104000,208000n m =-=-的一般任意图中构造哈密顿圈的实证研究结果, 验证了SOA 算法的可靠性和时间的多项式性. 在此基础上论证了SOA 算法用于判断一般任意图是否为哈密顿图的可行性, 并用一些实例进行了实证研究. 在阻塞流理论的研究中, 利用网络最小阻塞流与哈密顿轨之间的关系建立了哈密顿轨问题的无环最小支撑流模型. 通过这个模型可以把一步内构造无环最小支撑流这一数学难题分解成分别在多项式时间内完成的两个阶段,从而为解决这一数学难题找到了新的思路,开发研制了在一般任意图中构造哈密顿圈的自组织算法(或SOA 算法). 在文献, 全面详细地介绍了作者经过10多年潜心研究这一算法的理论及进行12000余[14]-例实证研究的结果. 到目前为止尚未遇到反例. 由于不少学者根据NPC 理论认定这是绝对不可能的, 因此作者只好通过大量的实证研究来显示这一多项式算法存在的可能性. 况且, 作者进行这项研究的目的并不是为了解决计算复杂性理论中NP 是否等于P 的问题,而是为学术研究和工程应用提供一种在一般图中构造哈密顿圈的实用有效工具. 即便有人能找到反例, 说明SOA 算法只不过是像线性规划单纯形算法那样, 是一个实用的好算法, 应当说这也是一个很幸运的结果. 因为有了它, 不但可以在用相关定理(如范定理或者其它更新的定理)判定存在哈密顿圈的一般图中构造出至少一条具体的哈密顿圈, 也可以对超出这些定理范围之外的一般图进行是否是哈密顿图的判定, 这岂不也是一项有实用价值的成果. 如果这些研究结果还能对数学家们在解决哈密顿图判定的理论研究上有所启迪和帮助, 那么这项研究就更有意义了. 二、研究的基本内容, 拟解决的主要问题研究的基本内容: 1. 哈密顿图的判定;2. 哈密顿图的应用.解决的主要问题: 1. 判定一个图是否是哈密顿的必要条件.2. 判定一个图是否是哈密顿的充分条件.3. 哈密顿图问题的应用.三、研究步骤、方法及措施研究步骤: 1. 查阅相关资料, 做好笔记;2. 仔细阅读研究文献资料;3. 在老师指导下, 确定整个论文的思路, 列出论文提纲, 撰写开题报告;4. 翻译英文资料;5. 修改英文翻译, 撰写文献综述;6.撰写毕业论文;7. 上交论文初稿;8. 反复修改论文;9. 论文定稿.四、参考文献[1] 宁宣熙, 堵塞流理论及其应用[M]. 北京: 科学出版社, 2005.[2] Xuanxi Ning and Angelika Ning, The Blocking Flow Theory and its Application toHamiltonian Graph Problems[J]. Shaker Verlag. Aachen, 2006, 21(2): 286~318.[3] Ning Xuanxi. The Minimum Spanning Flow in a Network and its Self-organizationPrinciple[J]. The International Journal of Systems & Cybernetics, 2004, 33(2): 331~338.[4] Xuanxi Ning and Angelika Ning, The Minimum Spanning Flow Model of the HamiltonianPath Problem in a Digraph and its Polynomial Algorithm[J]. Information Processing and Management, 2006, 38(3): 356~361.[5] 同济大学应用数学系. 离散数学[M]. 上海: 同济大学出版社, 2003.[6] 同济大学应用数学系. 离散数学[M]. 上海: 同济大学出版社, 2003.[7] 王小东. 算法分析与设计[M]. 北京: 清华大学出版社, 1900.[8] 付寒冰, 周恒为. 数据结构中常用的三类算法[J]. 伊犁师范学院学报, 1997, 17(2):12~138.[9] 宁安琪, 宁宣熙. 金字塔图的哈密顿图性质研究[J]. 南京航空航天大学经济与管理学院学报, 2006, 21(3): 17~23.[10] 田媛, 刘铎. 金字塔图存在哈密顿回路的构造性证明[J]. 清华大学学报, 2007, 13(2): 38~52.。
组合数学的发展现状1985年9月，中国数学会组合数学与图论专业委员会成立，标记着中国组合数学学科的形成和创立，并于2001年正式成为中国组合数学与图论学会。
随着近年来组合数学理论体系的逐步完善和发展，越来越多的学者更加关注这一计算机与数学结合学科的发展。
中国数学会组合数学与图论专业委员会是中国数学会的分支机构，成立于1985年5月。
专业委员会的成立得到吴文俊先生的直接关心与支持。
首届专业委员会由25人组成，主任为徐利治。
专业委员会成立后，原有的全国组合数学研究会和全国图论研究会继续独立存在，各自组织活动。
直到2001年，两研究会正式合并成立中国组合数学与图论学会，同时完成了专业委员会的调整和换届。
专业委员会委员即学会常务理事；专业委员会主任，副主任即学会理事长，副理事长。
第一届专业委员会由26人组成，主任为范更华。
专业委员会于2004年在新疆乌鲁木齐组织召开了首届全国组合数学与图论大会，200多位代表参加了这次会议。
专业委员会于2004年在福州举办了为期三个月由福州大学离散数学研究中心承办的全国性研究生班，邀请海外留学人员利用学术休假回国开设完整的研究生课程，有50多位来自国内14所院校的研究生参加了这期研究生班。
专业委员会于2005年在福州举办了为期一个月由福州大学离散数学研究中心承办的全国性青年教师研讨班，旨在为组合数学与图论培养后继人才。
2005年3月在南京师范大学召开的理事长会议上草拟了学会的章程和关于举办学术会议的办法及工作程序，2005年6月在金华召开的第三届海峡两岸图论与组合数学会议上通过了这两个文件。
2006年8月学会在南开大学召开了第二届全国组合数学与图论大会，有400多位代表参加了此次会议。
由于第一届理事会四年任期已满，会议期间，学会根据章程进行了换届选举，南开大学陈永川当选为理事长。
在国外，组合数学早已成为十分重要的学科，甚至可以说是计算机科学的基础。
一些大公司，如IBM，AT&T都有全世界最强的组合研究中心。
图论综述一、简介图论是数学的一个分支。
它以图为研究对象。
图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
图G=（V,E）是一个二元组（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。
集合V中的元素称为图G的定点（或节点、点），而集合E的元素称为边（或线）。
通常，描绘一个图的方法是把定点画成一个小圆圈，如果相应的顶点之间有一条边，就用一条线连接这两个小圆圈，如何绘制这些小圆圈和连线时无关紧要的，重要的是要正确体现哪些顶点对之间有边，哪些顶点对之间没有边。
图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。
关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。
目前，图论已形成很多分支：如随机图论、网络图论、代数图论、拓扑图论、极值图论等。
图论的应用已经涵盖了人类学、计算机科学、化学、环境保护、非线性物理、心理学、社会学、交通管理、电信以及数学本身等。
二、基本内容2.1 图的基本概念本章首先介绍了图的一些基本性质和一些不同模型的图，包括偶图，完全图和补图，引入了定点度的来描述图的性质。
其次介绍了子图的相关概念，介绍了图的一些基本运算规则，对图的路和连通性进行了阐释。
紧接着讲解了最短路算法，定义设G为边赋权图。
u与v是G中两点，在连接u与v的所有路中，路中各边权值之和最小的路，称为u与v间的最短路。
图的代数表示，包括图的邻接矩阵和图的关联矩阵。
最后对极图理论进行了简介，主要介绍了极值图论中的一个经典结论——托兰定理。
2.2 树本章主要介绍了树的概念与性质，阐述了生成树与最小生成树的基本概念与一些常用结论与定理。
树是不含圈的无圈图，也是连通的无圈图。
树是图论中应用最为广泛的一类图。
在理论上，由于树的简单结构，常常是图论理论研究的“试验田”。
图论的发展及其在生活中的应用数学与应用数学张佳丽指导教师刘秀丽摘要主要介绍了图论的起源与发展及其生活中的若干应用，如：渡河问题、旅游推销员问题、最小生成树问题、四色问题、安排问题、中国邮递员问题。
同时也涉及到了几种在图论中应用比较广泛的方法，如：最邻近法、求最小生成树的方法、求最优路线的方法等。
关键词图论生活问题应用Graph Theory Development and the Application in LifeMathematics and applied mathematics Zhang JialiTutor Liu XiuliAbstract This paper mainly introduces the origin and development of graph theory and its several applications in our life, such as: crossing river problem, traveling salesman problem, minimum spanning tree problem, four color problem，arrangement problem，Chinese postman problem．It also researches several methods that are more widely applied in graph theory, for example: the method of most neighboring, the method of solving the minimum spanning tree，the method of the best route，and so on．Key words graph theory life problem application引言图论是一门古老的学科，是数学中有广泛应用的一个分支，与其他的数学分支，如群论、矩阵论、概率论、拓扑学、数分析等有着密切的联系．图论中以图为研究对象，图形中我们用点表示对象，两点之间的连线表示对象之间的某种特定的关系．事实上，任何一个包含了二元关系的系统都可以用图论来模拟．而且,图论能把纷杂的信息变的有序、直观、清晰．由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点间连接与否尤为重要，而图形的位置、大小、形状及连接线的曲直长短则无关紧要．图论在自然科学、社会科学等各个领域都有广泛的应用．随着科学的发展，以及生产管理、军事、交通运输等方面提出了大量实际的需要，图论的理论及其应用研究得到飞速发展。
图论及其应⽤-哈密尔顿图（alpha）图论及其应⽤-哈密尔顿图(alpha)⼩结：2010-04。
todo 没有粘贴公式。
1重要的概念是闭包。
注意 ppt定义42重点汇总与闭包定理3其他的2个定理对⽐：（第⼀阶级：是不是两个反⾯）⼀个是存在不相邻的点u , v, 围绕 du + dv >=n; G 是H图，那么G+uv也是H图（66：增边）满⾜du + dv >=n 都有u,v相邻，那么G是闭包、本次课主要内容(⼀)、哈密尔顿图的概念(⼆)、性质与判定哈密尔顿图1、背景(⼀)、哈密尔顿图的概念1857年，哈密尔顿发明了⼀个游戏(Icosian Game).它是由⼀个⽊制的正⼗⼆⾯体构成，在它的每个棱⾓处标有当时很有名的城市。
游戏⽬的是“环球旅⾏”。
为了容易记住被旅游过的城市，在每个棱⾓上放上⼀个钉⼦，再⽤⼀根线绕在那些旅游过的城市上(钉⼦),由此可以获得旅程的直观表⽰。
哈密尔顿(1805---1865),爱尔兰数学家。
个⼈⽣活很不幸，但兴趣⼴泛：诗歌、光学、天⽂学和数学⽆所不能。
他的主要贡献是在代数领域，发现了四元数(第⼀个⾮交换代数)，他认为数学是最美丽的花朵。
哈密尔顿把该游戏以25英镑的价格买给了J.Jacques and Sons公司 (该公司如今以制造国际象棋设备⽽著名) ，1859年获得专利权。
但商业运作失败了。
该游戏促使⼈们思考点线连接的图的结构特征。
这就是图论历史上著名的哈密尔顿问题。
2、哈密尔顿图与哈密尔顿路定义1 如果经过图G的每个顶点恰好⼀次后能够回到出发点，称这样的图为哈密尔顿图，简称H图。
所经过的闭途径是G的⼀个⽣成圈，称为G的哈密尔顿圈。
例1、正⼗⼆⾯体是H图。
例2 下图G是⾮H图。
证明：因为在G中，边uv是割边，所以它不在G的任意圈上，于是u与v不能在G的同⼀个圈上。
故G不存在包括所有顶点的圈，即G是⾮H图。
定义2 如果存在经过G的每个顶点恰好⼀次的路，称该路为G的哈密尔顿路，简称H路。
