Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
В теории графов известен класс графов Qn, называемых кубами размерности n, или гиперкубами. Это семейство описывается формулами Qn = K 2 ´ Qn – 1, Q 1 = K 2. Здесь K 2 – полный граф с двумя вершинами, т.е. две вершины, соединенные одним ребром. Операция «´» - перемножение графов.
Эта операция для графов A и B определяется следующим образом.
Результатом операции является граф C = A ´ B, множество вершин которого состоит во взаимнооднозначном отношении с декартовым произведением множеств вершин графов A и B, V (C) = V (A) ´ V (B).
Множество ребер E (C) графа C порождается множествами ребер E (A) и E (B). Пусть вершина v 1 Î V (C) соответствует паре вершин (a 1, b 1), a 1 Î V (A), b 1 Î V (B), а вершина v 2 Î V (C) соответствует паре вершин (a 2, b 2), a 2 Î V (A), b 2 Î V (B), тогда v 1 смежна v 2 (между ними имеется ребро), если выполняется одно из двух условий:
1) a 1 = a 2 и b 1 смежна b 2;
2) b 1 = b 2 и a 1 смежна a 2;
Гиперкуб Q 1 = K 2, т.е. представляет собой «отрезок» с точки зрения изображения геометрических фигур. Он содержит 2 вершины. Степень каждой из них равна единице. Гиперкуб Q 2 с точки зрения теории графов представляет собой цикл из четырех вершин, в геометрическом представлении – квадрат. Степень каждой вершины равна 2. Гиперкуб Q 3 может быть представлен вершинами и ребрами геометрической фигуры – куба. Этот гиперкуб содержит 8 вершин степени 3.
В общем случае гиперкуб Qn содержит 2 n вершин степени 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=2n then return(OK)
else begin пусть l - наибольший номер, такой, что 2 l |k;
out (token, k+1) through канал l
End
End
Из алгоритма видно, что решение принимается после 2 n пересылок маркера. Пусть p 0 – инициатор, а pk – процесс, который получает маркер (token, k). Для любого k < 2 n, обозначения pk и pk +1 отличаются на 1 бит, индекс которого обозначим как l (k), удовлетворяющий следующему условию:
Т.к. для любого i < n существует равное количество k Î {0,..., 2 n } с l (k) = i, то p 0 = p 2 n и решение принимается в инициаторе. Можно показать, что из pa = pb следует, что 2 n |(b – a), откуда следует, что все p 0,..., p 2 n -1 различны.
Дата публикования: 2014-11-18; Прочитано: 639 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!