题目: 区间图的路与圈

报告人: 吴耀琨  上海交通大学数学系

时间:6月2日下午4:30―5:30

地点:管理科研楼1518

摘要：一个区间图以实轴上一族区间为顶点集，两个顶点相邻当且仅当它们表示的区间有非空交。一般图上的难题往往当限制在区间图上以后变得容易。给定图中一个顶点，1HP问题要求判断是否存在以该点为一个端点的哈密顿路。我们最近针对区间图设计了1HP问题的线性算法。不幸的是，即使区间图足够简单，我们还是没有把握在50分钟内解释清楚这个线性算法的构造，更无法勾勒其正确性的分析。我们的算法涉及区间图中路与圈结构的大量讨论，该算法的摸索过程引领我们涉足区间图的路与圈结构方面的一些新风景。

图中路与圈的结构，刻画和算法问题是一个广大的研究领域，图中哈密顿圈/路的容错性，圈可扩性，给定端点或子图的路与圈的存在性， 按一定顺序经过某些给定路的路与圈的存在性等等专题都有大量文献。作为前述线性算法工作的部分副产品，我们展示一系列的结果来说明上面提到的一般图上诸多貌似不相关的性质在区间图类上的紧密联系。这一系列结果背后蕴含着多得多的疑问和猜想以及一些可能有意义的新概念，有兴趣的本科生可以来此一展身手。

本报告基于我的在读博士生李鹏与我的近期工作。

演讲人简介： 吴耀琨2002年上海交大数学系博士毕业，随后留校任教至今。目前学习和研究的一个方向是各种简单组合结构的表示，刻画和算法，尤其是树与区间的组合学。吴耀琨也着迷于一些最简单的离散动力系统的电脑模拟和数学分析。他喜欢与优秀的本科生一起学习和欣赏各种有缘相识的数学。

主办单位：中国科学技术大学数学科学学院   中科院吴文俊数学重点实验室

欢迎感兴趣的师生参加!