Куб Фибоначчи

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

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

Определение

Подобно графу гиперкуба, вершины куба Фибоначчи порядка n можно пометить битовыми строками длины n таким образом, что две вершины смежны, если их метки отличаются одним битом. Однако в кубе Фибоначчи разрешены только метки, которые (как битовые строки) не имеют двух единиц подряд. Имеется F n + 2 {displaystyle F_{n+2}} возможных меток, где Fn обозначает n-е число Фибоначчи, а потому имеется F n + 2 {displaystyle F_{n+2}} вершин в кубе Фибоначчи порядка n.

Узлам таких сетей могут быть назначены последовательные целые числа от 0 до F n + 2 − 1 {displaystyle F_{n+2}-1} . Битовые строки, соответствующие этим числам, задаются их представлениями Цекендорфа.

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

Куб Фибоначчи порядка n является симплектическим графом дополнения графа пути с n вершинами. То есть, каждая вершина куба Фибоначчи представляет клику в дополнении пути или, эквивалентно, в независимом множестве в самом пути. Две вершины куба Фибоначчи смежны, если клики или независимые множества, которые они представляют, отличаются удалением или добавлением одного элемента. Поэтому, подобно другим симплексным графам, кубы Фибоначчи являются медианными графами и, более обще, частичными кубами. Медиана любых трёх вершин куба Фибоначчи может быть найдена путём вычисления побитовой мажоритарной функции трёх меток. Если каждая их трёх меток не имеет двух последовательных битов 1, то это верно и для их мажоритарного значения.

Куб Фибоначчи является также графом дистрибутивной решётки, которая может быть получена через теорему Биркгофа из «забора», частично упорядоченного множества, определённого чередующейся последовательностью отношений a < b > c < d > e < f > … {displaystyle a<b>c<d>e<f>dots } . Имеется также альтернативное описание на языке тории графов той же решётки: независимые множества любого двудольного графа могут быть даны в определённом порядке, в котором одно независимое множество меньше другого, если они получаются путём удаления элементов из одной доли и добавления элементов в другую долю. С этим порядком независимые множества образуют дистрибутивную решётку, а применение данного построения к графу-пути приводит к ассоциации решётки с кубом Фибоначчи.

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

Куб Фибоначчи порядка n можно разбить на куб Фибоначчи порядка n − 1 {displaystyle n-1} (разметка узлов начинается с бита, имеющего значение 0) и куб Фибоначчи порядка n − 2 {displaystyle n-2} (узлы начинаются с бита значением 1).

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

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

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

Приложения

Сюй, а также Сюй, Пейдж и Лью предложили использовать кубы Фибоначчи в качестве сетевой топологии в системах параллельных вычислений. Как коммуникационная сеть куб Фибоначчи имеет полезные свойства, подобные свойствам гиперкуба — число инцидентных рёбер на одну вершину не более n/2, и диаметр сети не превосходит n, оба значения пропорциональны логарифму числа вершин, а возможность разбить сеть на меньшие подсети того же типа позволяет расщепить многие задачи параллельных вычислений. Кубы Фибоначчи поддерживают также эффективные протоколы для маршрутизации и широковещания в системах распределённых вычислений.

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

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

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