Войти
Кубы Фибоначчи или Сети Фибоначчи представляют собой семейство неориентированных графов с богатыми рекурсивными свойствами, вытекающими из теории чисел. Математически они похожи на графы гиперкуба, но с числом Фибоначчи вершин. Кубы Фибоначчи были впервые явно определены в Hsu (1993) в контексте топологий соединения для соединения параллельных или распределенных систем. Они также применялись в теории химических графов.
Куб Фибоначчи может быть определен в терминах кодов Фибоначчи и расстояния Хэмминга, независимых множеств вершин в графах путей или через дистрибутивные решетки.
Подобно графу гиперкуба, вершины куба Фибоначчи порядка n могут быть помечены цепочками битов длины n, таким образом, что две вершины являются смежными, если их метки отличаются одним битом. Однако в кубе Фибоначчи разрешены только метки, в которых нет двух последовательных 1 битов. Возможны F n + 2 меток, где F n обозначает n-е число Фибоначчи, и, следовательно, существует F n + 2 вершин в кубе Фибоначчи заказ n.
Кубы Фибоначчи (нарисованные красным) как подграфы гиперкубов Узлам такой сети могут быть присвоены последовательные целые числа от 0 до F n + 2 - 1; цепочки битов, соответствующие этим числам, задаются их представлениями Цекендорфа.
Кубом Фибоначчи порядка 6 Кубом Фибоначчи порядка n является симплекс-граф дополнительного графа графа путей с n вершинами. То есть каждая вершина в кубе Фибоначчи представляет собой клику в графе дополнения пути или, что эквивалентно, независимый набор в самом пути; две вершины куба Фибоначчи являются смежными, если клики или независимые множества, которые они представляют, отличаются добавлением или удалением одного элемента. Следовательно, как и другие симплексные графы, кубы Фибоначчи являются медианными графами и в более общем смысле частичными кубами. Медиана любых трех вершин в кубе Фибоначчи может быть найдена путем вычисления побитовой функции большинства трех меток; если каждая из трех меток не имеет двух последовательных 1 битов, то же самое верно и для их большинства.
Куб Фибоначчи также является графиком распределительной решетки, который может быть получен с помощью теоремы представления Биркгофа из зигзагообразного набора, a частично упорядоченное множество, определяемое чередующейся последовательностью отношений порядка a < b>c < d>e < f>... Существует также альтернативное теоретико-графическое описание той же решетки: независимые множества любого двудольного графа может быть задан частичный порядок, в котором один независимый набор меньше другого, если они отличаются удалением элементов с одной стороны двудольного деления и добавлением элементов к другой стороне двудольного раздела; при таком порядке независимые множества образуют распределительную решетку, и применение этой конструкции к графу путей приводит к решетке, связанной с кубом Фибоначчи.
Куб Фибоначчи порядка n может быть разделен на куб Фибоначчи порядка n - 1 (узлы с метками, начинающимися с 0 бита) и куб Фибоначчи порядка n - 2 (узлы с метками, начинающимися с 1 бита).
Каждый куб Фибоначчи имеет гамильтонов путь. Более конкретно, существует путь, который подчиняется описанному выше разделу: он посещает узлы с первым битом 0 и узлы с первым битом 1 в двух смежных подпоследовательностях. Внутри этих двух подпоследовательностей путь может быть построен рекурсивно по одному и тому же правилу, связывая две подпоследовательности на концах подпоследовательностей, у которых второй бит равен 0. Таким образом, например, в кубе Фибоначчи порядка 4 последовательность, построенная в таким образом (0100-0101-0001-0000-0010) - (1010-1000-1001), где круглые скобки разграничивают подпоследовательности в двух подграфах раздела. Кубы Фибоначчи с четным числом узлов больше двух имеют гамильтонов цикл.
Мунарини и Салви (2002) исследуют радиус и число независимости кубов Фибоначчи. Поскольку эти графы двудольные и имеют гамильтоновы пути, их максимальные независимые множества имеют число вершин, равное половине числа вершин во всем графе, округленное до ближайшего целого числа. Диаметр куба Фибоначчи порядка n равен n, а его радиус равен n / 2 (снова с округлением до ближайшего целого числа).
Тараненко и Весел (2007) показали, что можно проверить, можно ли проверить граф - это куб Фибоначчи, почти линейный по времени по размеру.
Hsu (1993) и Hsu, Page Liu (1993) предложили использовать кубы Фибоначчи в качестве топологии сети в параллельные вычисления. Как сеть связи куб Фибоначчи имеет полезные свойства, аналогичные свойствам гиперкуба: количество инцидентных ребер на вершину не превышает n / 2, а диаметр сети не превышает n, что пропорционально логарифму числа. вершин, а возможность разделения сети на более мелкие сети одного и того же типа позволяет разделять ее между несколькими параллельными вычислительными задачами. Кубы Фибоначчи также поддерживают эффективные протоколы для маршрутизации и широковещательной передачи в распределенных вычислениях.
Klavžar igert (2005) применяют кубы Фибоначчи в химической теории графов как описание семейства точных совпадений определенных молекулярных графов. Для молекулярной структуры, описываемой плоским графом G, резонансным графом или (графом Z-преобразований) G является граф, вершины которого описывают идеальное согласование G, а ребра соединяют пары идеальных совпадений, симметричная разность которых является внутренней стороной G. Полициклические ароматические углеводороды могут быть описаны как подграфы гексагональной мозаики плоскости, а график резонанса описывает возможные двойные связи структуры этих молекул. Как показывают Klavžar igert (2005), углеводороды, образованные цепочками шестиугольников, соединенных ребром к краю без трех смежных шестиугольников на линии, имеют резонансные графы, которые в точности соответствуют графам Фибоначчи. В более общем плане Zhang, Ou Yao (2009) описал класс плоских двудольных графов, у которых кубы Фибоначчи являются их резонансными графами.
Обобщенные кубы Фибоначчи были представлены Hsu Chung (1993) на основе чисел Фибоначчи k-го порядка, которые позже были расширены на более широкий класс сетей, названных Linear Recursive Networks Hsu, Chung Das ( 1997) на основе более общих форм линейных рекурсий. Ву (1997) модифицировал кубы Фибоначчи второго порядка на основе различных начальных условий. Другой связанный граф - это граф с числом Люка вершин, определенных из куба Фибоначчи путем запрета 1 бита как в первой, так и в последней позициях каждой строки битов; Дедо, Торри и Салви (2002) исследовали свойства окраски как кубов Фибоначчи, так и кубов Лукаса.
