Википедия

Куб Фибоначчи

Ку́бы Фибона́ччи, или фибона́ччиевы се́ти, — это семейство неориентированных графов с богатыми рекурсивными свойствами, возникшее в теории чисел. Математически эти кубы похожи на графы гиперкуба, но с числом вершин, равным числу Фибоначчи. Кубы Фибоначчи впервые явно определил в своей статье Сюй[1] в контексте взаимосвязей топологий для связи систем параллельных вычислений или распределённых систем. Они применяются также в химической теории графов.

Куб Фибоначчи можно определить в терминах кодов Фибоначчи и расстояния Хэмминга, независимых множеств вершин в путях, или через дистрибутивные решётки[англ.].

Определение

править
 
Кубы Фибоначчи (нарисованные красным цветом) как подграфы гиперкубов
 
Куб Фибоначчи порядка 6

Подобно графу гиперкуба, вершины куба Фибоначчи порядка n можно пометить битовыми строками длины n таким образом, что две вершины смежны, если их метки отличаются одним битом. Однако в кубе Фибоначчи разрешены только метки, которые (как битовые строки) не имеют двух единиц подряд. Имеется   возможных меток, где Fn обозначает n-е число Фибоначчи, а потому имеется   вершин в кубе Фибоначчи порядка n.

Узлам таких сетей могут быть назначены последовательные целые числа от 0 до  . Битовые строки, соответствующие этим числам, задаются их представлениями Цекендорфа[2].

Алгебраическая структура

править

Куб Фибоначчи порядка n является симплектическим графом[англ.] дополнения графа пути с n вершинами[3]. То есть, каждая вершина куба Фибоначчи представляет клику в дополнении пути или, эквивалентно, в независимом множестве в самом пути. Две вершины куба Фибоначчи смежны, если клики или независимые множества, которые они представляют, отличаются удалением или добавлением одного элемента. Поэтому, подобно другим симплексным графам, кубы Фибоначчи являются медианными графами и, более обще, частичными кубами[4][5]. Медиана любых трёх вершин куба Фибоначчи может быть найдена путём вычисления побитовой мажоритарной функции трёх меток. Если каждая их трёх меток не имеет двух последовательных битов 1, то это верно и для их мажоритарного значения.

Куб Фибоначчи является также графом дистрибутивной решётки[англ.], которая может быть получена через теорему Биркгофа[англ.] из «забора[англ.]», частично упорядоченного множества, определённого чередующейся последовательностью отношений  [6]. Имеется также альтернативное описание на языке тории графов той же решётки: независимые множества любого двудольного графа могут быть даны в определённом порядке, в котором одно независимое множество меньше другого, если они получаются путём удаления элементов из одной доли и добавления элементов в другую долю. С этим порядком независимые множества образуют дистрибутивную решётку[7], а применение данного построения к графу-пути приводит к ассоциации решётки с кубом Фибоначчи.

Свойства и алгоритмы

править

Куб Фибоначчи порядка n можно разбить на куб Фибоначчи порядка   (разметка узлов начинается с бита, имеющего значение 0) и куб Фибоначчи порядка   (узлы начинаются с бита значением 1)[8].

Любой куб Фибоначчи имеет гамильтонов путь. Конкретнее, существует путь, который обходит разбиение, описанное выше — он посещает узлы сначала с 0, а потом с 1 в двух непрерывных подпоследовательностях. В этих двух подпоследовательностях путь может быть построен рекурсивно по тому же правилу, соединяя две подпоследовательности концами, на которых второй бит имеет значение 0. Тогда, например, в кубе Фибоначчи порядка 4 последовательностью, построенной таким образом, будет (0100—0101—0001—0000—0010)—(1010—1000—1001), где скобки показывают подпоследовательности двух подграфов. Кубы Фибоначчи с чётным числом узлов, большим двух, имеют гамильтонов цикл[9].

Мунарини и Сальви[10] изучали радиус и число независимости кубов Фибоначчи. Поскольку эти графы двудольные и имеют гамильтоновы пути, их максимальные независимые множества имеют число вершин, которое равно половине вершин всего графа, округлённое до ближайшего целого[11]. Диаметр куба Фибоначчи порядка n равен n, а его радиус равен n/2 (снова, округлённый до ближайшего целого)[12].

Тараненко и Весель[13] показали, что можно проверить, является ли граф кубом Фибоначчи за время, близкое к его размеру.

Приложения

править

Сюй[1], а также Сюй, Пейдж и Лью[14] предложили использовать кубы Фибоначчи в качестве сетевой топологии в системах параллельных вычислений. Как коммуникационная сеть куб Фибоначчи имеет полезные свойства, подобные свойствам гиперкуба — число инцидентных рёбер на одну вершину не более n/2, и диаметр сети не превосходит n, оба значения пропорциональны логарифму числа вершин, а возможность разбить сеть на меньшие подсети того же типа позволяет расщепить многие задачи параллельных вычислений[9]. Кубы Фибоначчи поддерживают также эффективные протоколы для маршрутизации и широковещания в системах распределённых вычислений[1][15].

Клавжар и Жигерт применили кубы Фибоначчи в химической теории графов как описание семейства совершенных паросочетаний некоторых молекулярных графов[16]. Для молекулярной структуры, описываемой планарным графом G резонансным графом (или графом Z-преобразований) графа G является граф, вершины которого описывают совершенные паросочетания графа G, а рёбра которого соединяют пары совершенных паросочетаний, симметрическая разность которых является внутренней гранью графа G. Полициклические ароматические углеводороды могут быть описаны как подграфы шестиугольной мозаики плоскости, а резонансные графы описывают возможные структуры с двойными связями этих молекул. Как показали Клавжар и Жигерт[16], углеводороды, образованные цепочками шестиугольников, соединённых ребро к ребру без трёх смежных шестиугольников на прямой, имеют резонансные графы, которые в точности являются графами Фибоначчи. Более обще, Чжан, Оу и Яо описали класс планарных двудольных графов, которые имеют кубы Фибоначчи в качестве графов резонанса[17][3].

Связанные графы

править

Обобщённые кубы Фибоначчи предложили Сюй и Чжан[18], базируясь на числах Фибоначчи k-го порядка, которые позднее Сюй, Чжан и Дас, основываясь на более общих видах линейных рекурсий, расширили на класс сетей, названных линейными рекурсивными сетями[19]. Ву модифицировал кубы Фибоначчи второго порядка, основываясь на иных начальных условиях[20]. Другой связанный граф — куб Люка, с количеством вершин, равным числу Люка, определённый из куба Фибоначчи путём запрещения бита значением 1 как в первой, так и последней позициях каждой битовой строки. Дедо, Торри и Салви использовали свойства раскраски как кубов Фибоначчи, так и кубов Люка[21].

Примечания

править
  1. ↑ 1 2 3 Hsu, 1993.
  2. ↑ Klavžar, 2011, с. 3—4.
  3. ↑ 1 2 Klavžar, 2011, с. 3.
  4. ↑ Klavžar, 2005.
  5. ↑ Klavžar, 2011, с. Theorem 5.1.
  6. ↑ Ганснер (Gansner 1982) говорит как о «хорошо известном факте», что эта решётка имеет число элементов, равное числу Фибоначчи, а Стэнли (Stanley 1986) переносит этот факт в упражнения. См. также Höft & Höft, 1985, Beck, 1990 и Salvi & Salvi, 2008.
  7. ↑ Propp, 1997.
  8. ↑ Klavžar, 2011, с. 4—5.
  9. ↑ 1 2 Cong, Zheng, Sharma, 1993.
  10. ↑ Munarini, Salvi, 2002.
  11. ↑ Klavžar, 2011, с. 6.
  12. ↑ Klavžar, 2011, с. 9.
  13. ↑ Taranenko, Vesel, 2007.
  14. ↑ Hsu, Page, Liu, 1993.
  15. ↑ Stojmenovic, 1998.
  16. ↑ 1 2 Klavžar, Žigert, 2005.
  17. ↑ Zhang, Ou, Yao, 2009.
  18. ↑ Hsu, Chung, 1993.
  19. ↑ Hsu, Chung, Das, 1997.
  20. ↑ Wu, 1997.
  21. ↑ Dedó, Torri, Salvi, 2002.

Литература

править
  • István Beck. Partial orders and the Fibonacci numbers // Fibonacci Quarterly. — 1990. — Т. 28, вып. 2. — С. 172–174.
  • Cong B., Zheng S. Q., Sharma S. On simulations of linear arrays, rings and 2D meshes on Fibonacci cube networks // Proc. 7th Int. Parallel Processing Symposium. — 1993. — С. 748–751. — doi:10.1109/IPPS.1993.262788.
  • Ernesto Dedó, Damiano Torri, Norma Zagaglia Salvi. The observability of the Fibonacci and the Lucas cubes // Discrete Mathematics. — 2002. — Т. 255, вып. 1–3. — С. 55–63. — doi:10.1016/S0012-365X(01)00387-9.
  • Emden R. Gansner. On the lattice of order ideals of an up-down poset // Discrete Mathematics. — 1982. — Т. 39, вып. 2. — С. 113–122. — doi:10.1016/0012-365X(82)90134-0.
  • Hartmut Höft, Margret Höft. A Fibonacci sequence of distributive lattices // Fibonacci Quarterly. — 1985. — Т. 23, вып. 3. — С. 232–237.
  • Hsu W.-J. Fibonacci cubes: a new interconnection topology // IEEE Transactions on Parallel and Distributed Systems. — 1993. — Т. 4, вып. 1. — С. 3–12. — doi:10.1109/71.205649.
  • Hsu W.-J., Chung M. J. Generalized Fibonacci cubes // 1993 International Conference on Parallel Processing - ICPP'93. — 1993. — Т. 1. — С. 299–302. — doi:10.1109/ICPP.1993.95.
  • Hsu W.-J., Page C. V., Liu J.-S. Fibonacci cubes: a class of self-similar graphs // Fibonacci Quarterly. — 1993. — Т. 31, вып. 1. — С. 65–72.
  • Hsu W.-J., Chung M. J., Das A. Linear recursive networks and their applications in distributed systems // IEEE Transactions on Parallel and Distributed Systems. — 1997. — Т. 8, вып. 7. — С. 673–680. — doi:10.1109/71.598343.
  • Sandi Klavžar. On median nature and enumerative properties of Fibonacci-like cubes // Discrete Mathematics. — 2005. — Т. 299, вып. 1–3. — С. 145–153. — doi:10.1016/j.disc.2004.02.023.
  • Sandi Klavžar. Structure of Fibonacci cubes: a survey // IMFM Preprint Series. — Ljubljana, Slovenia: Institute of Mathematics, Physics and Mechanics, 2011. — Т. 49, вып. 1150.
  • Sandi Klavžar, Petra Žigert. Fibonacci cubes are the resonance graphs of Fibonaccenes // Fibonacci Quarterly. — 2005. — Т. 43, вып. 3. — С. 269–276. Архивировано 8 февраля 2007 года..
  • Emanuele Munarini, Norma Zagaglia Salvi. Structural and enumerative properties of the Fibonacci cubes // Discrete Mathematics. — 2002. — Т. 255, вып. 1–3. — С. 317–324. — doi:10.1016/S0012-365X(01)00407-1.
  • James Propp. Generating random elements of finite distributive lattices // Electronic Journal of Combinatorics. — 1997. — Т. 4, вып. 2. — С. R15. — arXiv:math.CO/9801066.
  • Rodolfo Salvi, Norma Zagaglia Salvi. Alternating unimodal sequences of Whitney numbers // Ars Combinatoria. — 2008. — Т. 87. — С. 105–117.
  • Richard P. Stanley. Enumerative Combinatorics. — Wadsworth, Inc., 1986. Упражнение 3.23a, страница 157
  • Ivan Stojmenovic. Optimal deadlock-free routing and broadcasting on Fibonacci cube networks // Utilitas Mathematica. — 1998. — Т. 53. — С. 159–166. Архивировано 25 июля 2011 года..
  • Taranenko A., Vesel A. Fast recognition of Fibonacci cubes // Algorithmica. — 2007. — Т. 49, вып. 2. — С. 81–93. — doi:10.1007/s00453-007-9026-5.
  • Jie Wu. Extended Fibonacci cubes // IEEE Transactions on Parallel and Distributed Systems. — 1997. — Т. 8, вып. 12. — С. 1203–1210. — doi:10.1109/71.640012.
  • Heping Zhang, Lifeng Ou, Haiyuan Yao. Fibonacci-like cubes as Z-transformation graphs // Discrete Mathematics. — 2009. — Т. 309, вып. 6. — С. 1284–1293. — doi:10.1016/j.disc.2008.01.053.
Источник — https://ru.wiki.x.io/w/index.php?title=Куб_Фибоначчи&oldid=135599752