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

В теории графов известен класс графов Q_n, называемых кубами размерности n, или гиперкубами. Это семейство описывается формулами Q_n = K ₂ ´ Q_{n – 1}, Q ₁ = K ₂. Здесь K ₂ – полный граф с двумя вершинами, т.е. две вершины, соединенные одним ребром. Операция «´» - перемножение графов.

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

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

Множество ребер E (C) графа C порождается множествами ребер E (A) и E (B). Пусть вершина v ₁ Î V (C) соответствует паре вершин (a ₁, b ₁), a ₁ Î V (A), b ₁ Î V (B), а вершина v ₂ Î V (C) соответствует паре вершин (a ₂, b ₂), a ₂ Î V (A), b ₂ Î V (B), тогда v ₁ смежна v ₂ (между ними имеется ребро), если выполняется одно из двух условий:

1) a ₁ = a ₂ и b ₁ смежна b ₂;

2) b ₁ = b ₂ и a ₁ смежна a ₂;

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

В общем случае гиперкуб Q_n содержит 2 ⁿ вершин степени 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 if k=2ⁿ then return(OK)

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

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

End

End

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

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