Метод построения эйлерового обхода двоичного куба
Двоичным п - мерным кубом называется ориентированный граф, вершинами которого являются двоичные наборы порядка п ; из вершины а этого куба существует дуга в вершину b тогда и только тогда, когда расстояние Хемминга между этими вершинами равно 1. Следовательно, таких дуг две : (a, b) и (b, a).
Под расстоянием Хемминга понимается число координат, в которых различаются двоичные наборы.
Эйлеровым обходом двоичного п - мерного куба называется такой обход, при котором по каждой из возможных дуг нужно пройти ровно по одному разу.
В двоичном
кубе таких дуг может быть
Строится
матрица переходов размерностью
.
Построение обхода Эйлера может начинаться с любой вершины и ведется по правилам :
а) если текущая вершина четная, то производится переход в максимально возможную вершину, а если нечетная, то в минимально возможную;
б) номер следующей вершины определяется номером строки;
в) после выполнения перехода он помечается как использованный – единица заменяется на ноль.
Данные операции
продолжаются до тех пор, пока все элементы
матрицы не станут нулевыми, или не будет
совершено ровно
переходов.
Пример. □ Рассмотрим построение эйлерового обхода для двоичного куба размерности п = 3. Сначала построим матрицу всех возможных переходов двоичного куба. Пусть она имеет вид, показанный в таблице 1.
Число единиц в матрице равно , а в каждом столбце (строке) может быть только п единиц. По диагонали эта матрица содержит нулевые элементы, так как переход из вершины в себя невозможен. Смысл элементов заключается в том, чтобы хранить информацию об использовании перехода, т.е. это двоичная переменная, которая может принимать значения 1 или 0. По вертикали записываются дуги, входящие в вершины, а по горизонтали – исходящие.
По этой матрице можно осуществлять переходы, продвигаясь по контуру Эйлера. Выберем в качестве исходной нулевую вершину, Так как 0 – число четное, то осуществляем переход в максимально возможную вершину, в данном случае это вершина 4. Из четвертой вершины также по максимально возможному переходу попадаем в вершину 6. Из шестой вершины снова по максимально возможному переходу попадаем в 7-ю вершину. Седьмая вершина – нечетная, поэтому переходим в минимально возможную вершину, в данном случае в третью. Число 3 тоже нечетное, поэтому переходим опять в минимально возможную – первую вершину.
Таблица 1
№ вершин |
0 (000) |
1 (001) |
2 (010) |
3 (011) |
4 (100) |
5 (101) |
6 (110) |
7 (111) |
0 (000) |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 (001) |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
2 (010) |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
3 (011) |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
4 (100) |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
5 (101) |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
6 (110) |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
7 (111) |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
Рис. 5.2
После завершения перехода получим следующий контур :
.
Граф данного обхода показан на рис. 5.2, а в таблице 1 показана смена битов. ■