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

Куби Фібоначчі, або мережі Фібоначчі, — це сімейство неорієнтованих графів з багатими рекурсивними властивостями, що виникло в теорії чисел. Математично ці куби схожі на графи гіперкуба, але з числом вершин, рівним числу Фібоначчі. Куби Фібоначчі вперше явно визначив у своїй статті СюйШаблон:Sfn в контексті взаємозв'язків топологій для зв'язку систем паралельних обчислень або розподілених систем. Вони застосовуються також в хімічній теорії графів.

Куб Фібоначчі можна визначити в термінах кодів Фібоначчі та відстані Геммінга, незалежних множин вершин у шляхах, або через дистрибутивні ґратки.

Визначення

Куби Фібоначчі (намальовані червоним кольором) як підграфи гіперкубів

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

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

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

Куб Фібоначчі порядку $n$ є Шаблон:Нп доповнення графа шляху з $n$ вершинамиШаблон:Sfn. Тобто, кожна вершина куба Фібоначчі представляє кліку в доповненні шляху або, що еквівалентно, в незалежній множині в самому шляху. Дві вершини куба Фібоначчі суміжні, якщо кліки або незалежні множини, які вони представляють, відрізняються видаленням або додаванням одного елемента. Тому, подібно до інших симплексних графів, куби Фібоначчі є Шаблон:Нп і, більш загально, частковими кубами Шаблон:Sfn Шаблон:Sfn. Медіана будь-яких трьох вершин куба Фібоначчі може бути знайдена шляхом обчислення побітової мажоритарної функції трьох міток. Якщо кожна із трьох міток не має двох послідовних бітів 1, то це виконується і для їх мажоритарного значення.

Куб Фібоначчі є також графом дистрибутивної ґратки, яка може бути отримана через Шаблон:Нп з «Шаблон:Нп», частково впорядкованої множини, визначеної почерговою послідовністю відношень $a < b > c < d > e < f > \dots$ ^[1]. Є також альтернативний опис мовою теорії графів тієї ж ґратки: незалежні множини будь-якого двочасткового графа можуть бути дані в певному порядку, в якому одна незалежна множина менша від іншої, якщо вони отримані шляхом видалення елементів з однієї частини і додавання елементів в іншу частину. З цим порядком незалежні множини утворюють дистрибутивну ґраткуШаблон: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.

Примітки

Шаблон:Примітки

Література

↑ Ганснер Шаблон:Harvard citation каже як про «добре відомий факт», що ця ґратка має число елементів, рівне числу Фібоначчі, а Стенлі Шаблон:Harvard citation переносить цей факт у вправи. Див. також Шаблон:Harvnb, Шаблон:Harvnb і Шаблон:Harvnb.

[1] Ганснер Шаблон:Harvard citation каже як про «добре відомий факт», що ця ґратка має число елементів, рівне числу Фібоначчі, а Стенлі Шаблон:Harvard citation переносить цей факт у вправи. Див. також Шаблон:Harvnb, Шаблон:Harvnb і Шаблон:Harvnb.

[1]

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

Зміст

Визначення

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

Властивості й алгоритми

Застосування

Пов'язані графи

Примітки

Література

Навігаційне меню

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

Визначення

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

Властивості й алгоритми

Застосування

Пов'язані графи

Примітки

Література

Навігаційне меню

Пошук