Том 19, номер 2, 2012 г., Стр. 76-84
УДК 519.95
Потапов В. Н.
Построение гамильтоновых циклов с заданным спектром направлений рёбер в булевом n-мерном кубе
Аннотация:
Спектром гамильтонова цикла (кода Грея) в булевом$n$ -мерном кубе называется набор$a=(a_1,\dots,a_n)$ , где$a_i$ – число рёбер$i$ -го направления в цикле. Известны необходимые условия существования кода Грея со спектром$a$ : числа$a_i$ чётные и для любого$k=1,\dots,n$ сумма$k$ произвольных компонент набора$a$ не меньше чем$2^k$ . Доказано существование такой размерности$N$ , что если необходимые условия на спектр являются достаточными для существования гамильтонова цикла с таким спектром в булевом$N$ -мерном кубе, то сформулированные выше условия являются достаточными и для всех размерностей$n$ .
Библиогр. 10.
Ключевые слова: гамильтонов цикл, совершенное паросочетание, булев куб, код Грея.
Потапов Владимир Николаевич 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: vpotapov@math.nsc.ru
Статья поступила 6 июня 2011 г.
Исправленный вариант — 22 ноября 2011 г.
Литература
[1] Пережогин А. Л., Потапов В. Н. О числе гамильтоновых циклов в булевом кубе // Дискрет. анализ и исслед. операций. Сер. 1. — 2001. — Т. 8, № 2. — C. 52–62.
[2] Пережогин А. Л., Потапов В. Н. О cовершенных паросочетаниях в двоичном кубе // Дискретные модели в теории управляющих систем: VII междунар. конф. (Покровское, 4–6 марта 2006 г.): тр. М.: МАКС Пресс, 2006. — С. 272–277.
[3] Пережогин А. Л. Об автоморфизмах циклов в $n$-мерном булевом кубе // Дискрет. анализ и исслед. операций. Сер. 1. — 2007. — Т. 14, № 3. — С. 67–79.
[4] Потапов В. Н. О спектрах гамильтоновых циклов в булевом $n$-кубе // Мат. XVII междунар. школы-семинара «Синтез и сложность управляющих систем» им. академика О. Б. Лупанова (Новосибирск, 27 октября–1 ноября 2008 г.). — Новосибирск: Ин-т математики СО РАН, 2008. — С. 137–140.
[5] Bhat G. S., Savage C. D. Balanced Gray codes // Electron. J. Comb. — 1996. — Vol. 3, paper 25.
[6] Feder T., Subi C. Nearly tight bounds on the number of Hamiltonian circuits of the hypercube and generalizations // Inform. Process. Lett. — 2009. — Vol. 109, N 5. — P. 267–272.
[7] Fink J. Perfect matchings extend to Hamilton cycles in hypercubes // J. Comb. Theory, Ser. B. — 2007. — Vol. 97, N 6. — P. 1074–1076.
[8] Knuth D. E. The art of computer programming. Vol. 4. — New-Jersey: Addison–Wesley, 2009. — 944 p.
[9] Kreweras G. Matchings and Hamiltonian cycles on hypercubes // Bull. Inst. Comb. Appl. — 1996. — Vol. 16. — P. 87–91.
[10] Suparta I. N. A simple proof for the existence of exponentially balanced Gray codes // Electron. J. Comb. — 2005. — Vol. 12, note 19.
