运筹学讨论班
题目：Snake-In-The-Box Problem
报告人：束金龙教授
时间： 3月29号（星期三）下午4点-5点
地点： 理科大楼A1510

摘要：“盒中的蛇”（Snake-in-the-box）问题是数学和计算机科学中的十分困难问题，最早由 Kautz 于1958 年提出，盒中的蛇是指在超立方图中最长诱导路的长度，盒中的圈（Coil-in-the-box）是指在超立方图中最长诱导圈的长度，这两个量均有相当广泛的应用。“盒中的蛇”的编码问题在电子工程、编码理论、计算机网络拓扑结构的研究、设计等方面有许多的应用，尤其在给定维数下“蛇”的长度更为有用 (Klee 1970).

近半个世纪的研究中，对诱导圈最大长度的传统的数学研究方法可分为两个阶段：第一阶段主要是利用逻辑推理、离散数学、图论的方法进行研究；第二阶段利用计算机进行详尽的大量的计算进行估计。到现在为止已经得到7维以内的超立方图内诱导圈、诱导路的最大长度的精确值，1994年 Potter 等人利用遗传算法，1996 年 Kochut 利用穷举方法分别给出了7位超立方图的最长诱导圈、路的长度的下界。到目前为止，对 8 维到 12 维超立方图中最长诱导路的长度的下界为别为 97、168、338、618、1236。

然而随着维数的增加，要计算“盒中的蛇” 和“盒中的圈”的长度十分困难的，甚至对它们的上下界的估计也变得十分困难。在近50年的研究中，有关它们界的研究的结果均发表在组合、图论方面的重要杂志上，吸引了一大批学者进行这方面的研究。
近年来，人们将研究的图类拓宽到一般的简单图。对一般简单图中的诱导圈、诱导路的最大值进行计算或估计也十分有意义。

本次讲座重点讲述作者利用图谱理论进行这方面研究所得到的主要结果。


欢迎大家光临！