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

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

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

Определение

Кубы Фибоначчи (нарисованные красным цветом) как подграфы гиперкубов

Куб Фибоначчи порядка 6

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

Литература

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья.
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга Упражнение 3.23a, страница 157
• Шаблон:Статья.
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья