图论难题: “盒中蛇”和“盒中圈”问题

“盒中蛇”（Snake-in-the-box" Problem ）问题是图论学中(数学和计算机科学)的一大难题，最早由 Prof. Kautz 于1958 年提出."盒中蛇"是指在超立方图中最长诱导路的长度.

"盒中圈"（Coil-in-the-box）是指在超立方图中最长诱导圈的长度.

“盒中蛇”和"盒中圈", 这两个量均有相当广泛的应用: “盒中蛇”的编码问题在电子工程、编码理论、计算机网络拓扑结构的研究、设计等方面有许多的应用，尤其在给定维数下“蛇”的长度更为有用 (Prof. K.lee 1970).



半个世纪的研究中，对诱导圈最大长度的传统的数学研究方法可分为两个阶段：第一阶段主要是利用逻辑推理、离散数学、图论的方法进行研究；第二阶段利用计算机进行详尽的大量的计算进行估计。

对7维以内的超立方图内诱导圈、诱导路的最大长度的精确值, 已经得到结果。1). 1994年 Potter 等人利用遗传推进算法，给出了7维超立方图的最长诱导圈、最长诱导路的长度的下界. 2). 1996 年 Kochut 利用穷举方法给出了7维超立方图的最长诱导圈、最长诱导路的长度的下界。

到目前为止，对8维, 9维, 10维, 11维 和 12维超立方图中( “盒中蛇”)最长诱导路的长度的下界已经得到结果: 它们的下界分别为 97、168、338、618 和 1236。



随着维数的增加，要计算“盒中蛇” 和“盒中圈”的长度是十分困难的。甚至对它们的上下界的估计也变得十分困难。

1). 到目前为止, 没有给出13维以上超立方图的最长诱导圈、最长诱导路的长度的上下界。

2). 到目前为止, 没有给出非一致的稳定解的存在性等问题。

3). 有人将研究的超立方图类拓宽到一般的简单图。对一般简单图中的诱导圈、诱导路的最大值进行计算或估计也十分有意义。

4) 利用图谱理论进行超立方图类研究, 类推到一般维.

5).利用拓扑理论分析进行超立方图类研究, 类推到一般维.

在50年的研究中，有关超立方图的界的研究结果、有关领域的新进展及新动向均发表在组合、图论方面的重要杂志上。有兴趣者请研讨。

-----
*1. 一人不做二业。小鬼可以搬金刚。研讨此问题, 得到个小结果, 保证你拿博士. 回国去说不定可以当个院士.
*2. 不买(账)没关系，欢迎您随便参观。