В кубы Фибоначчи или сети Фибоначчи представляют собой семейство неориентированных графов с богатыми рекурсивных свойствами , полученными от его происхождения в теории чисел . Математически они похожи на графы гиперкубов , но с числом вершин Фибоначчи . Кубы Фибоначчи были впервые явно определены в Hsu (1993) в контексте топологий взаимосвязи для соединения параллельных или распределенных систем. Они также применялись в химической теории графов .
Куб Фибоначчи может быть определен в терминах кодов Фибоначчи и расстояния Хэмминга , независимых наборов вершин в графах путей или с помощью распределительных решеток .
Определение
Подобно графу гиперкуба, вершины куба Фибоначчи порядка n могут быть помечены цепочками битов длины n таким образом, чтобы две вершины были смежными, если их метки отличаются одним битом. Однако в кубе Фибоначчи разрешены только метки, в которых нет двух последовательных 1 битов. Возможны F n + 2 меток, где F n обозначает n- е число Фибоначчи, и, следовательно, в кубе Фибоначчи порядка n имеется F n + 2 вершин .
Узлам такой сети могут быть присвоены последовательные целые числа от 0 до F n + 2 - 1; цепочки битов, соответствующие этим числам, задаются их представлениями Цекендорфа . [1]
Алгебраическая структура
Куб Фибоначчи порядка п является симплекс граф в дополнение графа из с п графа пути -vertex. [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) показали, что можно проверить, является ли график кубом Фибоначчи во времени, почти линейным по размеру.
Приложения
Хсу (1993) и Хсу, Пейдж и Лю (1993) предложили использовать кубы Фибоначчи в качестве сетевой топологии в параллельных вычислениях . В качестве сети связи куб Фибоначчи имеет полезные свойства, аналогичные свойствам гиперкуба: количество инцидентных ребер на вершину не превышает n / 2, а диаметр сети не превышает n , что пропорционально логарифму числа. вершин, а возможность разделения сети на более мелкие сети одного и того же типа позволяет разделять ее между несколькими параллельными вычислительными задачами. [7] Кубы Фибоначчи также поддерживают эффективные протоколы маршрутизации и широковещательной передачи в распределенных вычислениях. [10]
Клавжар и Жигерт (2005) применяют кубы Фибоначчи в химической теории графов как описание семейства идеальных совпадений определенных молекулярных графов. Для молекулярной структуры, описываемой плоским графом G , резонансный граф или ( граф Z- преобразования) графа G - это граф, вершины которого описывают совершенные паросочетания G, а ребра соединяют пары совершенных паросочетаний, симметричная разность которых является внутренней гранью G . Полициклические ароматические углеводороды могут быть описаны как подграфы гексагональной мозаики плоскости, а резонансный график описывает возможные структуры с двойными связями этих молекул. Как показывают Клавжар и Жигерт (2005) , углеводороды, образованные цепочками шестиугольников, соединенных ребром к краю без трех смежных шестиугольников на линии, имеют резонансные графы, которые в точности соответствуют графам Фибоначчи. В более общем плане Чжан, Оу и Яо (Zhang, Ou & Yao, 2009) описали класс плоских двудольных графов, в которых кубы Фибоначчи являются их резонансными графами. [2]
Связанные графики
Обобщенные кубы Фибоначчи были представлены Hsu & Chung (1993) на основе чисел Фибоначчи k-го порядка, которые позже были расширены на более широкий класс сетей, названный Linear Recursive Networks by Hsu, Chung & Das (1997) на основе более общие формы линейных рекурсий. Ву (1997) модифицировал кубы Фибоначчи второго порядка на основе различных начальных условий. Другой связанный граф - это куб Люка , граф с числом вершин Люка, определенным из куба Фибоначчи путем запрета 1 бита как в первой, так и в последней позициях каждой строки битов; Дедо, Торри и Салви (2002) исследовали свойства окраски как кубов Фибоначчи, так и кубов Лукаса.
Заметки
- ^ Klavžar (2011) , стр. 3-4.
- ^ а б Клавжар (2011) , стр.3.
- ^ Klavžar (2005) ; Клавжар (2011) , теорема 5.1, стр.10.
- ^ Ганснер (1982) называет тот факт, что эта решетка имеет число элементов Фибоначчи, «хорошо известным фактом», в то время как Стэнли (1986) просит его описание в упражнении. См. Также Höft & Höft (1985) , Beck (1990) и Salvi & Salvi (2008) .
- Перейти ↑ Propp (1997) .
- ^ Klavžar (2011) , стр. 4-5.
- ^ a b Конг, Чжэн и Шарма (1993) .
- ^ Klavžar (2011) , с.6.
- ^ Klavžar (2011) , стр.9.
- ^ Сюй (1993) ; Стойменович 1998 .
Рекомендации
- Бек, Иштван (1990), «Частичные порядки и числа Фибоначчи», Fibonacci Quarterly , 28 (2): 172–174, MR 1051291.
- Cong, B .; Чжэн, SQ; Шарма, С. (1993), "О моделировании линейных массивов, колец и двумерных сеток на сетях кубов Фибоначчи", Proc. 7-й Int. Параллельная обработка Симпозиума ., Стр 748-751, DOI : 10,1109 / IPPS.1993.262788.
- Дедо, Эрнесто; Торри, Дамиано; Салви, Норма Загалья (2002), «Наблюдаемость кубов Фибоначчи и Лукаса», Дискретная математика , 255 (1–3): 55–63, DOI : 10.1016 / S0012-365X (01) 00387-9.
- Gansner, Эмден R. (1982), "О решетке порядка идеалов вверх-вниз посета", Дискретная математика , 39 (2): 113-122, DOI : 10.1016 / 0012-365X (82) 90134-0 , MR 0675856.
- Хёфт, Хартмут; Хёфт, Маргрет (1985), «Последовательность Фибоначчи распределительных решеток», Fibonacci Quarterly , 23 (3): 232–237, MR 0806293.
- Сюй, W.-J. (1993), "Кубики Фибоначчи: новая топология взаимосвязи", IEEE Transactions по параллельным и распределенным системам , 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.
- Hsu, W.-J .; Страница, CV; Лю, Ж.-С. (1993), "Кубы Фибоначчи: класс самоподобных графов", Fibonacci Quarterly , 31 (1): 65–72.
- Hsu, W.-J .; Чанг, MJ; Дас, А. (1997), «Линейные рекурсивные сети и их приложения в распределенных системах», IEEE Transactions on Parallel and Distributed Systems , 8 (7): 673–680, doi : 10.1109 / 71.598343.
- Klavžar, Санди (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.
- Мунарини, Эмануэле; Salvi, Norma Zagaglia (2002), "Структурные и перечислительные свойства кубов Фибоначчи", Дискретная математика , 255 (1-3): 317-324, DOI : 10.1016 / S0012-365X (01) 00407-1.
- Пропп, Джеймс (1997), "Генерация случайных элементов конечных распределительных решеток", Электронный журнал комбинаторики , 4 (2): R15, arXiv : math.CO/9801066.
- Сальви, Родольфо; Салви, Норма Загалья (2008), «Чередующиеся унимодальные последовательности чисел Уитни», Ars Combinatoria , 87 : 105–117, MR 2414008.
- Стэнли, Ричард П. (1986), Enumerative Combinatorics , 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.
- Ву, Джи (1997), "Расширенные кубы Фибоначчи", IEEE Transactions по параллельным и распределенным системам , 8 (12): 1203-1210, DOI : 10,1109 / 71,640012.
- Чжан, Хэпин; Оу, Лифенг; Яо, Haiyuan (2009), "Фибоначчи-подобные кубикам , как Z - преобразование графов", дискретная математика , 309 (6): 1284-1293, DOI : 10.1016 / j.disc.2008.01.053 , МР 2510538.