圖論難題: “盒中蛇”和“盒中圈”問題

“盒中蛇”（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. 不買(賬)沒關係，歡迎您隨便參觀。