Лекция: Алгоритм обхода гиперкуба

В теории графов известен класс графов Qn, называемых кубами размерности n, или гиперкубами. Это семейство описывается формулами Qn = K2 ´ Qn– 1, Q1 = K2. Здесь K2 – полный граф с двумя вершинами, т.е. две вершины, соединенные одним ребром. Операция «´» — перемножение графов.

Эта операция для графов A и B определяется следующим образом.

Результатом операции является граф C = A ´ B, множество вершин которого состоит во взаимнооднозначном отношении с декартовым произведением множеств вершин графов A и B, V(C) = V(A) ´ V(B).

Множество ребер E(C) графа C порождается множествами ребер E(A) и E(B). Пусть вершина v1 ÎV(C) соответствует паре вершин (a1, b1), a1 ÎV(A), b1 ÎV(B), а вершина v2 ÎV(C) соответствует паре вершин (a2, b2), a2 ÎV(A), b2 ÎV(B), тогда v1 смежна v2 (между ними имеется ребро), если выполняется одно из двух условий:

1) a1 = a2 и b1 смежна b2 ;

2) b1 = b2 и a1 смежна a2 ;

Гиперкуб Q1 = K2, т.е. представляет собой «отрезок» с точки зрения изображения геометрических фигур. Он содержит 2 вершины. Степень каждой из них равна единице. Гиперкуб Q2 с точки зрения теории графов представляет собой цикл из четырех вершин, в геометрическом представлении – квадрат. Степень каждой вершины равна 2. Гиперкуб Q3 может быть представлен вершинами и ребрами геометрической фигуры – куба. Этот гиперкуб содержит 8 вершин степени 3.

В общем случае гиперкуб Qn содержит 2n вершин степени n. В связи с этим удобно кодировать вершины строками из n бит – двоичной формой номеров вершин: от 000…0 до 111…1. Левый разряд числа (символ строки) будем называть нулевым разрядом, правый – (n – 1)-м. Тогда две вершины смежны в гиперкубе, если их коды отличаются в точности одним битом. Например, смежными с вершиной с кодом 010 будут вершины с кодами 110, 000, 011.

В каждом узле u инцидентные ему ребра можно перенумеровать числами от 0 до n – 1 так, что ребро номер 0 будет соединять узел u с таким узлом гиперкуба, код которого отличается от кода u в нулевом разряде. Соответственно, ребро номер 1 идет к вершине с отличием в коде в первом разряде и т.д.

Действия в алгоритме для гиперкуба.

Для инициатора (выполняется один раз):

out (token, 1) through канал n – 1

Для каждого процесса при получении маркера (token, k):

begin ifk=2nthen return(OK)

else beginпусть l — наибольший номер, такой, что 2l|k;

out (token, k+1) through канал l

End

End

Из алгоритма видно, что решение принимается после 2n пересылок маркера. Пусть p0– инициатор, а pk – процесс, который получает маркер (token, k). Для любого k < 2n, обозначения pk и pk+1 отличаются на 1 бит, индекс которого обозначим как l(k), удовлетворяющий следующему условию:

Т.к. для любого i < n существует равное количество k Î {0, ..., 2n} с l(k) = i, то p0= p2n и решение принимается в инициаторе. Можно показать, что из pa = pb следует, что 2n|(b – a), откуда следует, что все p0, ..., p2n-1 различны.