Метод построения эйлерового обхода двоичного куба

Двоичным п - мерным кубом называется ориентированный граф, вершинами которого являются двоичные наборы порядка п ; из вершины а этого куба существует дуга в вершину b тогда и только тогда, когда расстояние Хемминга между этими вершинами равно 1. Следовательно, таких дуг две : (a, b) и (b, a).

Под расстоянием Хемминга понимается число координат, в которых различаются двоичные наборы.

Эйлеровым обходом двоичного п - мерного куба называется такой обход, при котором по каждой из возможных дуг нужно пройти ровно по одному разу.

В двоичном кубе таких дуг может быть

Строится матрица переходов размерностью .

Построение обхода Эйлера может начинаться с любой вершины и ведется по правилам :

а) если текущая вершина четная, то производится переход в максимально возможную вершину, а если нечетная, то в минимально возможную;

б) номер следующей вершины определяется номером строки;

в) после выполнения перехода он помечается как использованный – единица заменяется на ноль.

Данные операции продолжаются до тех пор, пока все элементы матрицы не станут нулевыми, или не будет совершено ровно переходов.

Пример. □ Рассмотрим построение эйлерового обхода для двоичного куба размерности п = 3. Сначала построим матрицу всех возможных переходов двоичного куба. Пусть она имеет вид, показанный в таблице 1.

Число единиц в матрице равно , а в каждом столбце (строке) может быть только п единиц. По диагонали эта матрица содержит нулевые элементы, так как переход из вершины в себя невозможен. Смысл элементов заключается в том, чтобы хранить информацию об использовании перехода, т.е. это двоичная переменная, которая может принимать значения 1 или 0. По вертикали записываются дуги, входящие в вершины, а по горизонтали – исходящие.

По этой матрице можно осуществлять переходы, продвигаясь по контуру Эйлера. Выберем в качестве исходной нулевую вершину, Так как 0 – число четное, то осуществляем переход в максимально возможную вершину, в данном случае это вершина 4. Из четвертой вершины также по максимально возможному переходу попадаем в вершину 6. Из шестой вершины снова по максимально возможному переходу попадаем в 7-ю вершину. Седьмая вершина – нечетная, поэтому переходим в минимально возможную вершину, в данном случае в третью. Число 3 тоже нечетное, поэтому переходим опять в минимально возможную – первую вершину.

Таблица 1

Рис. 5.2

После завершения перехода получим следующий контур :

.

Граф данного обхода показан на рис. 5.2, а в таблице 1 показана смена битов. ■