RUS  ENG
Полная версия
ЖУРНАЛЫ // Автоматика и телемеханика // Архив

Автомат. и телемех., 2001, выпуск 6, страницы 136–150 (Mi at1807)

Эта публикация цитируется в 7 статьях

Техническая диагностика

Классификация гамильтоновых циклов в двоичных гиперкубах

П. П. Пархоменко

Институт проблем управления им. В. А. Трапезникова РАН, г. Москва

Аннотация: В отличие от общепринятого представления гамильтоновых циклов в гиперкубах в виде кольцевых последовательностей номеров вершин в статье предложено представление в виде кольцевых последовательностей весов ребер, соединяющих пары смежных вершин цикла. Вес ребра равен разности номеров инцидентных ему вершин. На основе представления гамильтоновых циклов последовательностями весов ребер предложено разбиение множества циклов на классы, определяемые распределениями чисел различных весов ребер, и на виды, принадлежащие классам и определяемые распределениями весов ребер.
Показано, что по известной последовательности весов ребер, представляющей некоторый гамильтонов цикл в $n$-мерном кубе, операциями сдвига и перестановки весов ребер можно получить не менее $n!-1$ других гамильтоновых циклов того же класса и вида.
Показано, как по классу и виду гамильтоновых циклов для $n$-мерного куба перейти к “аналогичному” классу и виду гамильтоновых циклов для $(n+1)$-мерного куба.

УДК: 681.324-192

Статья представлена к публикации членом редколлегии: П. Ю. Чеботарев

Поступила в редакцию: 15.01.2001


 Англоязычная версия: Automation and Remote Control, 2001, 62:6, 978–991

Реферативные базы данных:


© МИАН, 2024