Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v2(1-4)/munarini.pdf Дата изменения: Fri Nov 7 11:27:07 2008 Дата индексирования: Mon Oct 1 23:27:17 2012 Кодировка: Windows-1251

Структурные и перечислительные свойства кубов Фибоначчи
Эмануэль Мунарини, Норма Загаглиа Салви
Куб Фибоначчи представляет новую технологию межсоединений в мультикомпьютерных системах. Он является вложенным в единичный n-мерный куб двудольным графом. В работе доказано, что он может рассматриваться как полурешетка частного вида и определены его структурные свойства и характеристики такие как доли, центр, радиус и вершинное число независимости. Получено перечислительное свойство в виде нового соотношения для чисел Фибоначчи.

1 Введение
Понятие куба Фибоначчи было введено в работе [1] и в обобщенной форме в работе [2] как новая топология межсоединений в мультикомпьютерных системах. Куб Фибоначчи является двудольным графом, который как подграф может быть вложен в единичный n-мерный куб. Он обладает интересными топологическими и перечислительными свойствами, подобными свойствам гиперкуба [3], но характерными именно для куба Фибоначчи. Напомним, что числа Фибоначчи образуют последовательность положительных целых чисел Fn , где F0 = 1 , F1 = 2 и каждое следующее число удовлетворяет рекуррентному соотношению Fn+2 = Fn+1 + Fn . Известно, что всякое натуральное число единственным образом можно представить в виде суммы чисел Фибоначчи (по теореме Зекендорфа). Пусть i есть положительное целое такое, что i Fn-1 - 1 . Обозначим F (i) := [bn-1 , . . . , b1 , b0 ] строку Фибоначчи порядка n для числа i , где
n-1

i=
j =0

bj Fj

265


и bj равно 0 или 1 , для 0 j n - 1 , при условии, что bj bj +1 = 0 . Например, число i = F4 - 1 = 7 , можно представить в виде строки Фибоначчи 1010 . Будем обозначать строку, получающуюся конкатенацией строк и . В обобщенном виде, если S есть множество строк, то S = { : S } . Последовательности нулей i в строке 1 12 1 . . . 1r , называются максимальными. Пусть Cn есть множество строк Фибоначчи порядка n , то есть множество двоичных строк, не содержащих двух соседних единиц. Мы имеем Cn+2 = 0Cn+1 10Cn и |Cn | = Fn для каждого n N . Напомним, что расстоянием Хемминга между двумя двоичными строками и называется число H (, ) позиций, в которых они различаются.

Определение 1 . Кубом Фибоначчи n порядка n называется граф
(V , E ) , где V = {0, 1, . . . , Fn - 1} и (i, j ) E , если H (F (i), F (j )) = 1 .
В работе [1] доказано, что граф n+2 может быть разложен на два не пересекающихся и соединенных точно Fn ребрами подграфа n+1 и n . На Рис.1,а,б,в,г,д показаны кубы Фибоначчи для начальных значений n = 1, 2, 3, 4, 5

0
r

r

1

r

r



r

2

r

r r

3
r r

r

r r r

4
r r r

r r

а)

б)

в)
Рис. 1

г)

д)

В настоящей работе предлагается новый способ представления кубов Фибоначчи и описываются некоторые их структурные свойства и характеристики, такие как доли, центр, радиус и число независимости графа n . Получены также некоторые перечислительные свойства, из которых следуют новая формула для чисел Фибоначчи, и простое выражение для числа независимости графа n . Мы полагаем, что представление о рассматриваемых свойствах может быть использовано при проектировании вычислительных систем, устойчивых к неисправностям. Определение центра графа n полезно при организации операций рассылки информации из одного узла вычислительной сети всем остальным 266


или операции накопления информации от всех узлов в одном из них. Пересылка из центра любому другому узлу как и обратная пересылка могут быть осуществлены максимум за n шагов. По аналогичным 2 соображениям полезно знание вершинного числа независимости.

2 Структурные свойства
2.1 Полурешетки Фибоначчи
На множестве Cn двоичных строк длины n , не содержащих соседних единиц, определим отношение частичного порядка, полагая для каждых = [a1 , . . . , an ] и = [b1 , . . . , bn ] в Cn ,





ai bi ,

i = 1, 2, . . . , n .

Упорядоченное множество Fn = Cn , является нижней полурешеткой, то есть замкнуто относительно операции инфимума = [min(a1 , b1 ), . . . , min(an , bn )] и ее нижняя универсальная граница 0 = 00 ћ ћ ћ 0 . Если супремум существует, то = [max(a1 , b1 ), . . . , max(an , bn )] . Ясно, что для строки , содержащей k единиц, имеется точно k атомов 1 , . . . , k таких, что = 1 . . .k . Таким образом, упорядоченное множество Fn является атомарной полурешеткой. Обозначим Vk множество строк, содержащих k единиц. Максимальное число единиц в сроках из Cn определяется как n ; 2 соответствующая строка образуется конкатенацией максимальное число раз строки 10 с добавленением 1 при нечетном n . Таким образом, Vk = для всех k > n . На диаграмме Хассе полурешетки Fn две 2 строки соединяются ребром, если одна из нх покрывает другую, то есть если расстояние Хемминга между ними равно 1 . Так граф, заданный диаграммой Хассе полурешетки Fn изоморфен графу n . Например, для n = 3, 4 получаем диаграммы, представленные на Рис. 2 ,а,б.
r d d r r dr d d dr r r r d d d r r r r d d dr

F
а)

3

F
б)
Рис. 2 267

4


Очевидно, что никакие две строки с одинаковой четностью единиц на диаграмме Хассе не соединяются. Отсюда следует, что множества En , On строк с четным и нечетным числом единиц соответственно образуют доли двудольного графа n . Заметим, что перестановка вершин графа n , заключающаяся в замене каждой строки инверсной (отличающейся обратным порядком размещения двоичных символов) является инволюцией. Следовательно, декомпозиция графа n+2 на n+1 и n не единственна. В качестве примера приведем граф 4 = 3 +2 , где 3 и 2 образуются вершинами, в которых первый бит есть 0 или 1 соответственно. С другой стороны, 3 и 2 могут быть образованы вершинами, имеющими последний бит 0 или 1 соответственно.

2.2 Некоторые структурные свойства кубов Фибоначчи
В работе [4] эксцентриситет вершины v связного графа G определен как число e(v ) := max d(u, v ) .
uV (G)

Радиус графа G при этом определяется как

rad(G) := min e(v ) .
v V (G)

Вершина v является центральной вершиной если e(v ) = rad(G) . Центр Z (G) графа G образуется множеством всех его центральных вершин.

Утверждение 1 . rad(n ) =

n 2

.
n 2

. Максимально удалены от вершины 0 вершины с максимальным числом единиц, получаемые конкатенацией строки 10 максимальное число раз с добавлением 1 при нечетном n . Пусть теперь v является строкой, имеющей k > 0 единиц. Мы докажем, что e(v ) n . Строка v , наиболее удаленная от v , мо2 жет быть получена заменой в ней всех нулей единицами и последующим удалением минимального числа единиц так, чтобы получилась строка Фибоначчи. Если h является максимальной последовательностью нулей в строке v , то в строке v этой последовательности соответствует h h единиц. Тогда расстояние d(v , v ) = k + , где суммирова2 2 ние осуществляется по всем максимальным последовательностям нулей 268

Доказательство . Замети прежде всего, что e(0) =


в строке v . Поскольку

h 2
мы получаем

h n-k = 2 2

,

d(v , v ) k +

n n-k . 2 2

Пусть Un обозначает множество строк, имеющих только одну 1 и максимальную последовательность нулей четной длины. Так , например, мы имеем 00100 U5 но 01000 U5 .

Утверждение 2 . Для каждого n N , имеет место
Z (n ) = {0} {0} U
для четных n для нечетных n

n

Доказательство . Из доказательства утверждения 1, 0 Z (G) . Пусть

v является центральной вершиной, имеющей k единиц. Обозначим h1 длину последовательности нулей перед первой единицей, h2 длину последовательности нулей между первой и второй единицами и так далее до hk+1 . Пусть v строка, рассмотренная в доказательстве предыдущего утверждения. Тогда каждая максимальная последовательность нулей длины hi в v соответствует в v подстроке с hi единиц. 2 hi Следовательно d(v , v ) = k + . Необходимо различить два случая. 2
1) Все hi четны. Тогда
hi 2

=

hi 2

и

d(v , v ) = k +
Это значение совпадает с
n 2

hi n-k n+k =k+ = . 2 2 2
только при k = 1 и нечетном n .

2) Имеется по крайней мере одна максимальная последовательность нулей нечетной длины hi . Тогда

d(v , v ) k +

1 2

hi + 1 = k +
n 2

n-k+1 n+k+1 = . 2 2

Это значение не равно

ни при каких значениях k и n . 269


Назовем вершину графа n симметричной, если она соответствует симметричной строке.

для каждого n 2 .

Утверждение 3 . Число симметричных строк в n равно F
Доказательство . Если

n 2

-(-1)

n

n = 2m + 2 , то симметричная строка Фибоначчи длины n имеет вид 00 , где произвольная строка Фибоначчи длины m и строка, полученная инверсией строки . Имеется ровно Fm таких строк. Если n = 2m + 3 , то симметричная строка Фибоначчи длины n имеет либо форму 0 , где произвольная строка длины m + 1 , или форму 010 , где является произвольной строкой Фибоначчи длины m . Таким образом имеется ровно Fm + Fm+1 = Fm+2 таких строк. Эти наблюдения влекут справедливость утверждения.
Обозначим en и on число строк в множествах En , On соответственно. Напомним, что числом независимости (G) графа G называется максимальная мощность независимого множества вершин графа G .

Теорема 1 . (n ) = max(en , on ) .
Доказательство . Не ограничивая общности, можно допустить, что

en on . Докажем, что en является максимальным числом независимых вершин графа n . Допустим противное, что имеется подмножество A множества En которое можно заменить подмножеством B множества On , таким, что |B | > |A| и вершины множества B и En \ A являются независимыми. Отсюда следует, что вершины множества B смежны только вершинам множества A . В работе [1] доказано, что n всегда содержит цикл C , который включает либо все вершины множества n , либо все вершины, кроме одной. Замети, что поскольку граф n двудольный, в цикле C вершины множеств En и On чередуются. Пусть C является гамильтоновым циклом и v1 , v2 , . . . , vs вершины множества B перечисленные в порядке, определяемом циклом C . Обозначим w1 , w2 , . . . , ws вершины множества A , предшествующие вершинам vi и ws+1 вершину, следующую за вершиной vs в C . Вершины wj должны быть различными, тогда |A| > |B | , что противоречит допущению. В случае, когда C содержит все вершины, кроме одной, мы можем допустить, что C содержит

270


только s - 1 вершин множества B . По тем же соображениям A содержит не менее s вершин; следовательно, |A| |B | , противоречие.

3 Перечислительные свойства
В работах [5] и [6] доказаны многие перечислительные свойства чисел Фибоначчи. Одно из них состоит в том, что

|V n | =
k0

n-k+1 . k

При этом

en =
k0

n - 2k + 1 2k

on =
k0

n - 2k . 2k + 1

Утверждение 4 . Числа en и on удовлетворяют следующей системе
рекуррентных отношений

en+2 = en+1 + on on+2 = on+1 + en
с начальными условиями

(1)

e0 = 1 ,

e1 = 1 ,

o0 = 0 ,

o1 = 1 .

Fn+2 , соответствующая всем строкам, в которых первым символом является 0 , изоморфна полурешетке Fn+1 , в то же время подполурешетка, соответствующая строкам с первым символом 1 , изоморфна полурешетке Fn . В этой декомпозиции строка 10 ћ ћ ћ 0 является минимумом подполурешетки, изоморфной полурешетке Fn , так что ее элементы имеют четность, противоположную четности соответствующих элементов полурешетки Fn+2 , откуда следует доказываемое утверждение.
Первое уравнение системы (1) влечет следующее тождество

Доказательство . Мы знаем, что подполурешетка полурешетки

k0

n - 2k + 1 2k

=
k0

n - 2k + 2k
271

k0

n - 2k - 2 . 2k + 1


По теореме 1, интересно определить, какое из двух чисел en , on больше другого. Пусть hn их разность, а именно hn = en - on . Из (1) имеем hn+2 = en+1 - on+1 - (en - on ) или

h

n+2

=h

n+1

- hn .

Первые значения этой последовательности следующие

n

01

2 1 2

3 2 3

45

6

7

8

9

10

11

en 1 1 on 0 1 h
n

4 7 11 17 27 4 6 10 17 28 1 = -h 0

44 72 117 45 72 116 0 1

1 0 -1 -1 0 1 h

-1 -1

и легко видеть, что
n+3 n

и что

H ( x) =
n0

h n xn =

1-x . 1 - x + x2

Из системы (1) мы получаем уравнения

e

n+2 n+2

=e

n+1 n+1

+ en - h

n n

o
и производящие функции

=o

+ on + h

n0

n0

1 - x + x4 (1 - x + x2 )(1 - x - x2 ) x o n xn = . 2 )(1 - x - x2 ) (1 - x + x e n xn =

Окончательно, с учетом отношения

en + on = Fn en - on = hn
мы имеем

en =

Fn + hn , 2
272

on =

Fn - h 2

n


или

Fn = 2
k 0

n - 2k + 1 - hn = 2 2k

k0

n - 2k + hn , 2k + 1

новое отношение для чисел Фибоначчи.

Список литературы
[1] W. - J. Hsu, Fibonacci Cubes A New Interconnection Topology, IEEE Trans. on Parallel and Distributed Systems, 4, 1993, 3 - 12. [2] J. Liu, W. - J. Hsu, M. J. Chung, Generalized Fibonacci Cubes Are Mostly Hamiltonian, Journal of Graph Theory, 18, 1994, 817 - 829. [3] Y. Yaad, M. H. Schultz, Topological properties of the hypercubes, IEEE Trans. Comput., vol. 37, no. 7, 1988, 867 - 872. [4] G. Chartrand, L. Lesniak, Graphs and Digraphs. Wadsworth and Brooks, 1986. [5] R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1989. [6] D. E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley, Reading, MA, 1973.

273