Fibonacciho kostka

Fibonacciho kostky nebo Fibonacciho sítě jsou rodinou neorientovaných grafů s bohatými rekurzivními vlastnostmi, které vznikly v teorii čísel . Matematicky jsou tyto krychle podobné grafům hyperkrychle , ale mají stejný počet vrcholů jako Fibonacciho číslo . Fibonacciho kostky poprvé explicitně definoval ve svém článku Xu [1] v kontextu propojení topologií pro propojení paralelních výpočetních systémů nebo distribuovaných systémů. Používají se také v chemické teorii grafů .

Fibonacciho kostku lze definovat pomocí Fibonacciho kódů a Hammingových vzdáleností , nezávislých množin vrcholů v cestách nebo pomocí distributivních svazů .

Definice

Podobně jako graf hyperkrychle mohou být vrcholy Fibonacciho krychle řádu n označeny bitovými řetězci délky n tak, že dva vrcholy sousedí, pokud se jejich označení liší o jeden bit. Ve Fibonacciho krychli jsou však povoleny pouze štítky, které (jako bitové řetězce) nemají dvě jedničky za sebou. Existují možná označení, kde F n označuje n-té Fibonacciho číslo, a proto ve Fibonacciho krychli existují vrcholy řádu n .

Uzlům takových sítí lze přiřadit po sobě jdoucí celá čísla od 0 do . Bitové řetězce odpovídající těmto číslům jsou dány jejich Zeckendorfovými reprezentacemi [2] .

Algebraická struktura

Fibonacciho krychle řádu n je symplektický graf doplňku grafu cesty s n vrcholy [3] . To znamená, že každý vrchol Fibonacciho krychle představuje kliku v doplňku cesty nebo ekvivalentně v nezávislé množině v cestě samotné. Dva vrcholy Fibonacciho krychle sousedí, pokud se kliky nebo nezávislé množiny, které reprezentují, liší v odstranění nebo přidání jednoho prvku. Proto, stejně jako ostatní simplexní grafy, jsou Fibonacciho kostky mediánovými grafy a obecněji dílčími krychlemi [4] [5] . Medián libovolných tří vrcholů Fibonacciho krychle lze nalézt výpočtem bitové většinové funkce tří štítků. Pokud každý ze tří štítků nemá dva po sobě jdoucí bity 1, pak totéž platí pro jejich většinovou hodnotu.

Fibonacciho kostka je také graf distributivní mřížky , který lze získat pomocí Birkhoffovy věty z " plotu ", částečně uspořádané množiny definované střídající se sekvencí relací [6] . Existuje také alternativní popis v torii grafů stejné mřížky: nezávislé množiny libovolného bipartitního grafu mohou být uvedeny v určitém pořadí, ve kterém je jedna nezávislá množina menší než druhá, pokud jsou získány odstraněním prvků z jednoho grafu. díl a přidání prvků do jiného dílu. S tímto řádem tvoří nezávislé množiny distributivní mřížku [7] a aplikace této konstrukce na dráhový graf vede k asociaci mřížky s Fibonacciho krychlí.

Vlastnosti a algoritmy

Fibonacciho kostku řádu n lze rozdělit na Fibonacciho kostku řádu (označení uzlů začíná hodnotou bitu 0) a Fibonacciho kostku řádu (uzly začínají hodnotou bitu 1) [8] .

Každá Fibonacciho kostka má hamiltonovskou cestu . Přesněji řečeno, existuje cesta, která obchází výše popsaný oddíl – navštěvuje uzly nejprve s 0 a poté s 1 ve dvou sousedních dílčích sekvencích. V těchto dvou podsekvencích lze cestu sestavit rekurzivně podle stejného pravidla, přičemž obě podsekvence propojíme s konci, na kterých má druhý bit hodnotu 0. Pak např. ve Fibonacciho kostce řádu 4 se sekvence konstruovaná v takto bude (0100-0101-0001- 0000-0010)-(1010-1000-1001), kde závorky označují podsekvence dvou podgrafů. Fibonacciho krychle se sudým počtem uzlů větším než dva mají hamiltonovský cyklus [9] .

Munarini a Salvi [10] studovali poloměr a počet nezávislosti Fibonacciho kostek. Protože jsou tyto grafy bipartitní a mají hamiltonovské cesty, jejich maximální nezávislé množiny mají počet vrcholů, který se rovná polovině vrcholů celého grafu, zaokrouhlený nahoru na nejbližší celé číslo [11] . Průměr Fibonacciho krychle řádu n je n a její poloměr je n /2 (opět zaokrouhleno na nejbližší celé číslo) [12] .

Taranenko a Vesel [13] ukázali, že je možné ověřit, zda je graf Fibonacciho kostkou v čase blízkém jeho velikosti.

Aplikace

Xu [1] , stejně jako Xu, Page a Liu [14] , navrhli použití Fibonacciho kostek jako topologie sítě v paralelních počítačových systémech . Jako komunikační síť má Fibonacciho krychle užitečné vlastnosti podobné vlastnostem hyperkrychle – počet dopadajících hran na vrchol nepřesahuje n /2 a průměr sítě nepřesahuje n , obě hodnoty jsou úměrné logaritmus počtu vrcholů a schopnost rozdělit síť na menší podsítě stejného typu umožňuje rozdělit mnoho úloh paralelního počítání [9] . Fibonacciho kostky také podporují efektivní protokoly pro směrování a vysílání v distribuovaných počítačových systémech [1] [15] .

Klavzhar a Zhigert aplikovali Fibonacciho kostky v chemické teorii grafů jako popis rodiny dokonalých párování některých molekulárních grafů [16] . Pro molekulární strukturu popsanou rovinným grafem G je rezonanční graf (nebo graf Z -transformace) grafu G graf, jehož vrcholy popisují dokonalé shody grafu G a jehož hrany spojují dvojice dokonalých shod, jejichž symetrický rozdíl je vnitřek. plocha grafu G. Polycyklické aromatické uhlovodíky lze popsat jako podgrafy hexagonálního obkladu roviny a rezonanční grafy popisují možné struktury dvojných vazeb těchto molekul. Jak ukázali Klavzhar a Zhigert [16] , uhlovodíky tvořené řetězci šestiúhelníků od okraje k okraji bez tří sousedních šestiúhelníků na čáře mají grafy rezonance, které jsou přesně Fibonacciho grafy. Obecněji Zhang, Ou a Yao popsali třídu planárních bipartitních grafů, které mají Fibonacciho kostky jako rezonanční grafy [17] [3] .

Související grafy

Zobecněné Fibonacciho kostky navrhli Xu a Zhang [18] na základě Fibonacciho čísel k -tého řádu, které se později Xu, Zhang a Das na základě obecnějších typů lineárních rekurzí rozšířily na třídu sítí nazývanou lineární rekurzivní sítě [19 ] . Wu modifikoval Fibonacciho kostky druhého řádu na základě různých počátečních podmínek [20] . Dalším souvisejícím grafem je Lucasova kostka s počtem vrcholů rovným Lucasovu číslu , definovaná z Fibonacciho kostky inhibicí bitu s hodnotou 1 v první i poslední pozici každého bitového řetězce. Dedo, Torri a Salvi využili barvicích vlastností kostek Fibonacciho a Lucas [21] .

Poznámky

  1. ↑ 1 2 3 Hsu, 1993 .
  2. ↑ Klavžar, 2011 , str. 3-4.
  3. ↑ 1 2 Klavžar, 2011 , str. 3.
  4. ↑ Klavžar, 2005 .
  5. ↑ Klavžar, 2011 , str. Věta 5.1.
  6. ↑ Gansner ( 1982 ) o tom mluví jako o „známé skutečnosti“, že tato mřížka má stejný počet prvků jako Fibonacciho číslo a Stanley ( Stanley 1986 ) tuto skutečnost přenáší do cvičení. Viz také Höft & Höft 1985 , Beck 1990 a Salvi & Salvi 2008 .
  7. ↑ Propp, 1997 .
  8. ↑ Klavžar, 2011 , str. 4-5.
  9. ↑ 1 2 Cong, Zheng, Sharma, 1993 .
  10. ↑ Munarini, Salvi, 2002 .
  11. ↑ Klavžar, 2011 , str. 6.
  12. ↑ Klavžar, 2011 , str. 9.
  13. ↑ Taranenko, Vesel, 2007 .
  14. ↑ Hsu, Page, Liu, 1993 .
  15. ↑ Stojmenovic, 1998 .
  16. ↑ 1 2 Klavžar, Žigert, 2005 .
  17. ↑ Zhang, Ou, Yao, 2009 .
  18. ↑ Hsu, Chung, 1993 .
  19. ↑ Hsu, Chung, Das, 1997 .
  20. ↑ Wu, 1997 .
  21. ↑ Dedó, Torri, Salvi, 2002 .

Literatura