В математической области теории графов кубы Фибоначчи или сети Фибоначчи представляют собой семейство неориентированных графов с богатыми рекурсивными свойствами, возникшими из теории чисел . Математически они подобны графам гиперкуба , но с числом вершин Фибоначчи . Кубы Фибоначчи были впервые явно определены в Сюй (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) показали, что можно проверить, является ли граф кубом Фибоначчи во времени, почти линейном по его размеру.
Сюй (1993) и Сюй, Пейдж и Лю (1993) предложили использовать кубы Фибоначчи в качестве топологии сети в параллельных вычислениях . В качестве коммуникационной сети куб Фибоначчи обладает полезными свойствами, аналогичными свойствам гиперкуба: число ребер, инцидентных каждой вершине, не превышает n /2, а диаметр сети не превышает n , оба пропорциональны логарифму числа вершин, а способность сети разделяться на более мелкие сети одного и того же типа позволяет разделить ее между несколькими параллельными вычислительными задачами. [7] Кубы Фибоначчи также поддерживают эффективные протоколы маршрутизации и широковещательной передачи в распределенных вычислениях. [10]
Клавжар и Жигерт (2005) применяют кубы Фибоначчи в химической теории графов как описание семейства идеальных паросочетаний определенных молекулярных графов. Для молекулярной структуры, описываемой плоским графом G , резонансный граф или ( граф Z -преобразований) графа G — это граф, вершины которого описывают совершенные паросочетания G , а ребра соединяют пары совершенных паросочетаний, симметричная разность которых является внутренней гранью G. . Полициклические ароматические углеводороды можно описать как подграфы гексагональной мозаики плоскости, а резонансный граф описывает возможные структуры двойной связи этих молекул. Как показывают Клавжар и Жигерт (2005), углеводороды, образованные цепочками шестиугольников, соединенных ребром к ребру без трех соседних шестиугольников в линию, имеют резонансные графики, которые в точности являются графиками Фибоначчи. В более общем плане Чжан, Оу и Яо (2009) описали класс плоских двудольных графов, резонансными графами которых являются кубы Фибоначчи. [2]
Обобщенные кубы Фибоначчи были представлены Сюй и Чунг (1993) на основе чисел Фибоначчи k-го порядка, которые позже были расширены до более широкого класса сетей, названных Сюй, Чунг и Дас (1997) на основе более крупных сетей, называемых линейными рекурсивными сетями. общие формы линейных рекурсий. Ву (1997) модифицировал кубы Фибоначчи второго порядка на основе различных начальных условий. Другой родственный граф - это куб Лукаса, граф с числом вершин Люка, определенным из куба Фибоначчи путем запрета использования 1 бита как в первой, так и в последней позициях каждой цепочки битов; Дедо, Торри и Сальви (2002) исследовали свойства окраски как кубов Фибоначчи, так и кубов Лукаса.