Том 23, номер 1, 2016 г., Стр. 51-64

УДК 519.95
Быков И. С.
О локально равномерных кодах Грея

Аннотация:
Рассматриваются локально равномерные коды Грея. Код Грея назовём локально равномерным, если в каждом подслове переходной последовательности «небольшой» длины содержатся все буквы алфавита {1, 2, … , n}. Наименьшую такую длину назовём шириной окна кода. Показано, что для каждого n ≥ 3 существует код Грея такой, что ширина окна не превосходит $n + 3 \lfloor\log n\rfloor$.
Табл. 2, библиогр. 10.

Ключевые слова: код Грея, гамильтонов цикл, n-мерный куб, ширина окна кода.

DOI: 10.17377/daio.2016.23.497

Быков Игорь Сергеевич ¹
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: patrick.no10@gmail.com

Статья поступила 9 июня 2015 г.
Исправленный вариант — 17 августа 2015 г.

Литература

[1] Годовых О. П. Исследование равномерных кодов Грея // Мат. 50 междунар. науч. студ. конф. «Студент и научно-технический прогресс» (Новосибирск, 13–19 апреля 2012 г.). Новосибирск: Новосиб. гос. ун-т, 2012. С. 133.

[2] Евдокимов А. А. О нумерации подмножеств конечного множества // Методы дискретного анализа в решении комбинаторных задач. 1980. Вып. 34. С. 8–26.

[3] Короленко Л. А. Нахождение сильно равномерных кодов Грея // Мат. 48 междунар. науч. студ. конф. «Студент и научно-технический прогресс» (Новосибирск, 10–14 апреля 2010 г.). Новосибирск: Новосиб. гос. ун-т, 2010. С. 162.

[4] Aguilo F., Miralles A. On the Frobenius’ problem of three numbers // Proc. 2005 Eur. Conf. Comb., Graph Theory Appl. (Berlin, Germany, Sept. 5–9, 2005). Nancy: DMTCS, 2005. P. 317–322.

[5] Chebiryak Yu., Kroening D. Towards a classification of Hamiltonian cycles in the 6-cube // J. Satisf., Boolean Model. Comput. 2008. Vol. 4, No. 1. P. 57–74.

[6] Dejter I. J., Delgado A. A. Classes of Hamilton cycles in the 5-cube // J. Comb. Math. Comb. Comput. 2007. Vol. 61. P. 81–95.

[7] Feder T., Subi C. Nearly tight bounds on the number of Hamiltonian circuits of the hypercube and generalizations // Inf. Process. Lett. 2009. Vol. 109, No. 5. P. 267–272.

[8] Goddyn L., Gvozdjak P. Binary Gray codes with long bit runs // The Electron. J. Comb. 2003. Vol. 10, No. R27. P. 1–10.

[9] Haanpää H., Östergård P. R. J. Counting Hamiltonian cycles in bipartite graphs // Math. Comput. 2014. Vol. 83, No. 286. P. 979–995.

[10] Savage C. A survey of combinatorial Gray codes // SIAM Rev. 1997. Vol. 39, No. 4. P. 605–629.