Куб Фибоначчи - Fibonacci cube

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

Примечания

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

использованная литература

  • Бек, Иштван (1990), «Частичные порядки и числа Фибоначчи», Ежеквартальный отчет Фибоначчи, 28 (2): 172–174, Г-Н  1051291.
  • Cong, B .; Zheng, S. Q .; Шарма, С. (1993), "О моделировании линейных массивов, колец и двумерных сеток на сетях кубов Фибоначчи", Proc. 7-й Int. Симпозиум по параллельной обработке, стр. 748–751, Дои:10.1109 / IPPS.1993.262788.
  • Дедо, Эрнесто; Торри, Дамиано; Салви, Норма Загалья (2002), "Наблюдаемость кубов Фибоначчи и Лукаса", Дискретная математика, 255 (1–3): 55–63, Дои:10.1016 / S0012-365X (01) 00387-9.
  • Ганснер, Эмден Р. (1982), "О решетке идеалов порядка перевернутого позета", Дискретная математика, 39 (2): 113–122, Дои:10.1016 / 0012-365X (82) 90134-0, Г-Н  0675856.
  • Хёфт, Хартмут; Хёфт, Маргрет (1985), "Последовательность Фибоначчи дистрибутивных решеток", Ежеквартальный отчет Фибоначчи, 23 (3): 232–237, Г-Н  0806293.
  • Hsu, W.-J. (1993), «Кубы Фибоначчи: новая топология взаимосвязей», Транзакции IEEE в параллельных и распределенных системах, 4 (1): 3–12, Дои:10.1109/71.205649.
  • Hsu, W.-J .; Чанг, М. Дж. (1993), "Обобщенные кубы Фибоначчи", 1993 Международная конференция по параллельной обработке - ICPP'93, 1, стр. 299–302, Дои:10.1109 / ICPP.1993.95.
  • Hsu, W.-J .; Page, C. V .; Лю, Ж.-С. (1993), «Кубы Фибоначчи: класс самоподобных графов», Ежеквартальный отчет Фибоначчи, 31 (1): 65–72.
  • Hsu, W.-J .; Chung, M. J .; Дас, А. (1997), "Линейные рекурсивные сети и их приложения в распределенных системах", Транзакции IEEE в параллельных и распределенных системах, 8 (7): 673–680, Дои:10.1109/71.598343.
  • Клавжар, Санди (2005), "О медианной природе и перечислительных свойствах кубов, подобных Фибоначчи", Дискретная математика, 299 (1–3): 145–153, Дои:10.1016 / j.disc.2004.02.023.
  • Клавжар, Санди (2011), «Структура кубов Фибоначчи: обзор» (PDF), Серия препринтов IMFM, Любляна, Словения: Институт математики, физики и механики, 49 (1150).
  • Клавжар, Санди; Чигерт, Петра (2005), «Кубы Фибоначчи - это резонансные графики Фибоначчи», Ежеквартальный отчет Фибоначчи, 43 (3): 269–276, архивировано с оригинал на 2007-02-08.
  • Мунарини, Эмануэле; Салви, Норма Загалья (2002), "Структурные и перечислительные свойства кубов Фибоначчи", Дискретная математика, 255 (1–3): 317–324, Дои:10.1016 / S0012-365X (01) 00407-1.
  • Пропп, Джеймс (1997), "Создание случайных элементов конечных распределительных решеток", Электронный журнал комбинаторики, 4 (2): R15, arXiv:math.CO/9801066.
  • Сальви, Родольфо; Салви, Норма Загалья (2008), «Чередующиеся унимодальные последовательности чисел Уитни», Ars Combinatoria, 87: 105–117, Г-Н  2414008.
  • Стэнли, Ричард П. (1986), Перечислительная комбинаторика, Wadsworth, Inc. Упражнение 3.23а, стр. 157.
  • Стойменович, Иван (1998), «Оптимальная маршрутизация и трансляция без тупиков в сетях куба Фибоначчи» (PDF), Utilitas Mathematica, 53: 159–166, архивировано с оригинал (PDF) на 2011-07-25.
  • Тараненко, А .; Весел, А. (2007), "Быстрое распознавание кубов Фибоначчи", Алгоритмика, 49 (2): 81–93, Дои:10.1007 / s00453-007-9026-5.
  • Ву, Цзе (1997), «Расширенные кубы Фибоначчи», Транзакции IEEE в параллельных и распределенных системах, 8 (12): 1203–1210, Дои:10.1109/71.640012.
  • Чжан, Хэпин; Оу, Лифенг; Яо, Хайюань (2009), «Кубики, подобные Фибоначчи, как Z-графы преобразований », Дискретная математика, 309 (6): 1284–1293, Дои:10.1016 / j.disc.2008.01.053, Г-Н  2510538.