В теории графов известен класс графов Qn , называемых кубами размерности n, или гиперкубами. Это семейство описывается формулами Qn = K2 ´ Qn – 1 , Q 1 = 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) b 1 = b2 и a1 смежна a2 ;
Гиперкуб Q 1 = 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=2n then return(OK)
else beginпусть l - наибольший номер, такой, что 2l|k;
out (token, k+1) through канал l