主题
Search

蛇

蛇是 欧拉路径 在 d-超立方体 中，它没有弦（即，连接蛇顶点的任何 超立方体 边都是蛇边）。Klee (1970) 询问了 s(d) 的最大长度 d-蛇。Klee (1970) 给出了界限

7/(4(d-1))<=(s(d))/(2^d)1/2-(1-12/2^(-d))/(7d(d-1)^2+2)
(1)

对于 d>=6 (Danzer and Klee 1967, Douglas 1969)，以及许多参考文献。Abbott 和 Katchalski (1988) 表明

s(d)>=77·2^(d-8),
(2)

Snevily (1994) 表明

s(d)>=2^(d-1)(1-1/(20d-41))
(3)

对于 d<=12，并推测

s(d)>=3·2^(d-3)+2
(4)

对于 d<=5。s(d) 对于 d=1, 2, ..., 的前几个值是 2, 4, 6, 8, 14, 26, ... (OEIS A000937)。

另请参阅

Apple Surface, Hypercube, Snake Eyes, Snake Lemma, Snake Oil Method, Snake Polyiamond

使用 探索

参考文献

Abbott, H. L. and Katchalski, M. "On the Snake in the Box Problem." J. Combin. Th. Ser. B 44, 12-24, 1988.Danzer, L. and Klee, V. "Length of Snakes in Boxes." J. Combin. Th. 2, 258-265, 1967.Douglas, R. J. "Some Results on the Maximum Length of Circuits of Spread k in the d-Cube." J. Combin. Th. 6, 323-339, 1969.Emelianov, P. "Snake-in-the-Box." http://mix.nsk.ru/epg/snake.html.Evdokimov, A. A. "Maximal Length of a Chain in a Unit n-Dimensional Cube." Mat. Zametki 6, 309-319, 1969.Guy, R. K. "Unsolved Problems Come of Age." Amer. Math. Monthly 96, 903-909, 1989.Guy, R. K. "Monthly Unsolved Problems." Amer. Math. Monthly 94, 961-970, 1989.Guy, R. K. and Nowakowski, R. J. "Monthly Unsolved Problems, 1696-1995." Amer. Math. Monthly 102, 921-926, 1995.Kautz, W. H. "Unit-Distance Error-Checking Codes." IRE Trans. Elect. Comput. 7, 177-180, 1958.Klee, V. "What is the Maximum Length of a d-Dimensional Snake?" Amer. Math. Monthly 77, 63-65, 1970.Sloane, N. J. A. Sequence A000937/M0995 in "The On-Line Encyclopedia of Integer Sequences."Snevily, H. S. "The Snake-in-the-Box Problem: A New Upper Bound." Disc. Math. 133, 307-314, 1994.Solov'jeva, F. I. "An Upper Bound for the Length of a Cycle in an n-Dimensional Cube." Diskret. Analiz. 45, 1987.

在 上被引用

蛇

引用为

Weisstein, Eric W. "Snake." 来自 -- 沃尔夫勒姆网络资源。 https://mathworld.net.cn/Snake.html

主题分类