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

Многие из Вас слышали о задаче про кроликов, а значит, и про числа Фибоначчи. Но сегодняшний пост будет посвящен не просто этим числам, а Кубам Фибоначчи.

Итак, давайте посмотрим, что же это такое?)

В математической области теории графов кубы Фибоначчи или сети Фибоначчи представляют собой семейство неориентированных графов с богатыми рекурсивными свойствами. Математически они похожи на графики гиперкубов, но с числом Фибоначчи вершин.

Кубы Фибоначчи впервые были явно определены в Hsu (1993) в контексте топологий межсоединений для соединения параллельных или распределенных систем. Они также применялись в химической теории графов.

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

Узлам таких сетей могут быть назначены последовательные целые числа от 0 до ?(?+2)-1. Битовые строки, соответствующие этим числам, задаются их представлениями Цекендорфа.

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

Куб Фибоначчи является также графом дистрибутивной решётки, которая может быть получена через теорему Биркгофа из «забора», частично упорядоченного множества, определённого чередующейся последовательностью отношений ???. Имеется также альтернативное описание на языке тории графов той же решётки: независимые множества любого двудольного графа могут быть даны в определённом порядке, в котором одно независимое множество меньше другого, если они получаются путём удаления элементов из одной доли и добавления элементов в другую долю. С этим порядком независимые множества образуют дистрибутивную решётку, а применение данного построения к графу-пути приводит к ассоциации решётки с кубом Фибоначчи.

Источник: vk.com

Комментарии: