В математической области теории графов кубы Фибоначчи или сети Фибоначчи представляют собой семейство неориентированных графов с богатыми рекурсивными свойствами, полученными из его происхождения в теории чисел . Математически они похожи на графы гиперкубов , но с числом вершин Фибоначчи . Кубы Фибоначчи были впервые явно определены в Hsu (1993) в контексте топологий взаимосвязей для соединения параллельных или распределенных систем. Они также применялись в химической теории графов .
Куб Фибоначчи может быть определен в терминах кодов Фибоначчи и расстояния Хэмминга , независимых наборов вершин в графах путей или через распределительные решетки .
Подобно графу гиперкуба, вершины куба Фибоначчи порядка n могут быть помечены битовыми строками длины n таким образом, что две вершины являются смежными, когда их метки отличаются в одном бите. Однако в кубе Фибоначчи единственными допустимыми метками являются битовые строки без двух последовательных битов 1. Если метки гиперкуба интерпретировать как двоичные числа , метки в кубе Фибоначчи являются подмножеством, фиббинарными числами . Возможны F n + 2 меток, где F n обозначает n -ое число Фибоначчи, и, следовательно, в кубе Фибоначчи порядка n имеется F n + 2 вершин .
Узлам такой сети могут быть назначены последовательные целые числа от 0 до F n + 2 − 1; битовые строки, соответствующие этим числам, задаются их представлениями Цекендорфа . [1]
Куб Фибоначчи порядка 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) исследовали свойства раскраски как кубов Фибоначчи, так и кубов Лукаса.