Куб Фибоначчи
Семейство графиков, основанных на последовательности Фибоначчи

В математической области теории графов кубы Фибоначчи или сети Фибоначчи представляют собой семейство неориентированных графов с богатыми рекурсивными свойствами, полученными из его происхождения в теории чисел . Математически они похожи на графы гиперкубов , но с числом вершин Фибоначчи . Кубы Фибоначчи были впервые явно определены в Hsu (1993) в контексте топологий взаимосвязей для соединения параллельных или распределенных систем. Они также применялись в химической теории графов .

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

Определение

Подобно графу гиперкуба, вершины куба Фибоначчи порядка n могут быть помечены битовыми строками длины n таким образом, что две вершины являются смежными, когда их метки отличаются в одном бите. Однако в кубе Фибоначчи единственными допустимыми метками являются битовые строки без двух последовательных битов 1. Если метки гиперкуба интерпретировать как двоичные числа , метки в кубе Фибоначчи являются подмножеством, фиббинарными числами . Возможны F n  + 2 меток, где F n обозначает n -ое число Фибоначчи, и, следовательно, в кубе Фибоначчи порядка n имеется F n  + 2 вершин .

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

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

Куб Фибоначчи 6-го порядка

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

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

Куб Фибоначчи также является графом дистрибутивной решетки , которая может быть получена с помощью теоремы Биркгофа о представлении из зигзагообразного частично упорядоченного множества , частично упорядоченного множества , определяемого чередующейся последовательностью отношений порядка a < b > c < d > e < f > ... [4] Существует также альтернативное теоретико-графовое описание той же решетки: независимым множествам любого двудольного графа можно задать частичный порядок, в котором одно независимое множество меньше другого, если они отличаются удалением элементов с одной стороны двудольного графа и добавлением элементов с другой стороны двудольного графа; при таком порядке независимые множества образуют дистрибутивную решетку, [5] и применение этой конструкции к графу путей приводит к решетке, связанной с кубом Фибоначчи.

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

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

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

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

Тараненко и Весел (2007) показали, что можно проверить, является ли график кубом Фибоначчи, за время, близкое к линейному по его размеру.

Приложения

Hsu (1993) и Hsu, Page & Liu (1993) предложили использовать кубы Фибоначчи в качестве сетевой топологии в параллельных вычислениях . Как коммуникационная сеть, куб Фибоначчи имеет полезные свойства, похожие на свойства гиперкуба: количество инцидентных ребер на вершину не превышает n /2, а диаметр сети не превышает n , оба пропорциональны логарифму количества вершин, а способность сети разделяться на меньшие сети того же типа позволяет разделить ее между несколькими параллельными вычислительными задачами. [7] Кубы Фибоначчи также поддерживают эффективные протоколы для маршрутизации и трансляции в распределенных вычислениях. [10]

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

Обобщенные кубы Фибоначчи были представлены Сю и Чангом (1993) на основе чисел Фибоначчи k-го порядка, которые позже были расширены до более крупного класса сетей, названных линейными рекурсивными сетями Сю, Чангом и Дасом (1997) на основе более общих форм линейных рекурсий. Ву (1997) модифицировал кубы Фибоначчи второго порядка на основе различных начальных условий. Другой связанный граф — куб Лукаса, граф с числом вершин Лукаса, определяемым из куба Фибоначчи путем запрета бита 1 как в первой, так и в последней позиции каждой битовой строки; Дедо, Торри и Сальви (2002) исследовали свойства раскраски как кубов Фибоначчи, так и кубов Лукаса.

Примечания

  1. ^ Клавжар (2011), стр. 3–4.
  2. ^ ab Klavžar (2011), стр.3.
  3. ^ Клавжар (2005); Клавжар (2011), Теорема 5.1, стр.10.
  4. ^ Ганснер (1982) называет тот факт, что эта решетка имеет число Фибоначчи элементов, «хорошо известным фактом», в то время как Стэнли (1986) просит описать его в упражнении. См. также Höft & Höft (1985), Beck (1990) и Salvi & Salvi (2008).
  5. ^ Пропп (1997).
  6. ^ Клавжар (2011), стр. 4–5.
  7. ^ Аб Конг, Чжэн и Шарма (1993).
  8. ^ Клавжар (2011), стр.6.
  9. ^ Клавжар (2011), стр.9.
  10. ^ Хсу (1993); Стойменович 1998.

Ссылки

  • Бек, Иштван (1990), «Частичные порядки и числа Фибоначчи», Fibonacci Quarterly , 28 (2): 172–174, MR  1051291.
  • Cong, B.; Zheng, SQ; Sharma, S. (1993), «О моделировании линейных массивов, колец и двумерных сеток в сетях кубов Фибоначчи», Proc. 7th Int. Parallel Processing Symposium , стр. 748–751, doi :10.1109/IPPS.1993.262788, ISBN 0-8186-3442-1, S2CID  621063.
  • Дедо, Эрнесто; Торри, Дамиано; Сальви, Норма Загалья (2002), «Наблюдаемость кубов Фибоначчи и Лукаса», Дискретная математика , 255 (1–3): 55–63, doi : 10.1016/S0012-365X(01)00387-9.
  • Ганснер, Эмден Р. (1982), «О решетке идеалов порядка частично упорядоченного множества вверх-вниз», Дискретная математика , 39 (2): 113–122, doi : 10.1016/0012-365X(82)90134-0 , MR  0675856.
  • Хёфт, Хартмут; Хёфт, Маргрет (1985), «Последовательность Фибоначчи распределительных решеток», Fibonacci Quarterly , 23 (3): 232–237, MR  0806293.
  • Hsu, W.-J. (1993), «Кубы Фибоначчи: новая топология взаимосвязей», IEEE Transactions on Parallel and Distributed Systems , 4 (1): 3–12, doi :10.1109/71.205649.
  • Hsu, W.-J.; Chung, MJ (1993), "Обобщенные кубы Фибоначчи", Международная конференция по параллельной обработке 1993 г. - ICPP'93 , т. 1, стр. 299–302, doi :10.1109/ICPP.1993.95, ISBN 0-8493-8983-6, S2CID  15982621.
  • Сюй, В.-Дж.; Пейдж, К.В.; Лю, Дж.-С. (1993), «Кубы Фибоначчи: класс самоподобных графиков», Fibonacci Quarterly , 31 (1): 65–72.
  • Hsu, W.-J.; Chung, MJ; Das, A. (1997), «Линейные рекурсивные сети и их применение в распределенных системах», IEEE Transactions on Parallel and Distributed Systems , 8 (7): 673–680, doi :10.1109/71.598343.
  • Клавжар, Санди (2005), «О медианной природе и перечислительных свойствах кубов, подобных числам Фибоначчи», Дискретная математика , 299 (1–3): 145–153, doi : 10.1016/j.disc.2004.02.023.
  • Клавжар, Санди (2011), «Структура кубов Фибоначчи: обзор» (PDF) , Серия препринтов IMFM , 49 (1150), Любляна, Словения: Институт математики, физики и механики.
  • Клавжар, Санди; Жигерт, Петра (2005), «Кубы Фибоначчи — это резонансные графики Фибоначчи», Fibonacci Quarterly , 43 (3): 269–276, архивировано из оригинала 2007-02-08.
  • Мунарини, Эмануэле; Сальви, Норма Загалья (2002), «Структурные и перечислимые свойства кубов Фибоначчи», Дискретная математика , 255 (1–3): 317–324, doi : 10.1016/S0012-365X(01)00407-1.
  • Пропп, Джеймс (1997), «Генерация случайных элементов конечных дистрибутивных решеток», Электронный журнал комбинаторики , 4 (2): R15, arXiv : math.CO/9801066 , doi : 10.37236/1330, S2CID  13313188.
  • Сальви, Родольфо; Сальви, Норма Загалья (2008), «Чередующие унимодальные последовательности чисел Уитни», Ars Combinatoria , 87 : 105–117, MR  2414008.
  • Стэнли, Ричард П. (1986), Перечислительная комбинаторика , Wadsworth, Inc.Упражнение 3.23а, стр. 157.
  • Стойменович, Иван (1998), «Оптимальная маршрутизация без тупиков и широковещательная передача в сетях кубов Фибоначчи» (PDF) , Utilitas Mathematica , 53 : 159–166, архивировано из оригинала (PDF) 25 июля 2011 г..
  • Тараненко, А.; Весел, А. (2007), «Быстрое распознавание кубов Фибоначчи», Algorithmica , 49 (2): 81–93, doi :10.1007/s00453-007-9026-5, S2CID  993779.
  • У, Цзе (1997), «Расширенные кубы Фибоначчи», Труды IEEE по параллельным и распределенным системам , 8 (12): 1203–1210, doi :10.1109/71.640012.
  • Чжан, Хэпин; Оу, Лифенг; Яо, Хайюань (2009), «Кубы, подобные числам Фибоначчи, как графики Z -преобразований», Дискретная математика , 309 (6): 1284–1293, doi : 10.1016/j.disc.2008.01.053 , MR  2510538.
Взято с "https://en.wikipedia.org/w/index.php?title=Fibonacci_cube&oldid=1241888499"