Fibonacci terning

Fibonacci-terninger eller Fibonacci-netværk er en familie af urettede grafer med rige rekursive egenskaber, der stammer fra talteori . Matematisk ligner disse terninger hyperkubegrafer , men med det samme antal hjørner som Fibonacci-tallet . Fibonacci-kuber blev først eksplicit defineret i hans artikel af Xu [1] i forbindelse med sammenkoblinger af topologier til sammenkobling af parallelle computersystemer eller distribuerede systemer. De anvendes også i kemisk grafteori .

Fibonacci-terningen kan defineres i form af Fibonacci-koder og Hamming-afstande , uafhængige sæt af hjørner i stier , eller i form af distributive gitter .

Definition

Ligesom en hyperkubegraf kan hjørnerne af en Fibonacci-terning af orden n mærkes med bitstrenge af længden n , således at to hjørner er tilstødende, hvis deres etiketter adskiller sig med en bit. Men i Fibonacci-terningen er kun etiketter tilladt, der (som bitstrenge) ikke har to 1'ere i træk. Der er mulige mærker, hvor F n betegner det n'te Fibonacci-tal, og derfor er der hjørner i Fibonacci-terningen af ​​orden n .

Noderne i sådanne netværk kan tildeles konsekutive heltal fra 0 til . Bitstrengene, der svarer til disse tal, er givet ved deres Zeckendorf-repræsentationer [2] .

Algebraisk struktur

Fibonacci-terningen af ​​orden n er den symbolske graf af stigrafens komplement med n toppunkter [3] . Det vil sige, at hvert hjørne af Fibonacci-terningen repræsenterer en klike i komplementet til stien eller tilsvarende i et uafhængigt sæt i selve stien. To hjørner af en Fibonacci-terning er tilstødende, hvis de kliker eller uafhængige sæt, de repræsenterer, er forskellige med hensyn til fjernelse eller tilføjelse af et element. Derfor, ligesom andre simpleksgrafer, er Fibonacci-terninger mediangrafer og mere generelt partielle terninger [4] [5] . Medianen af ​​alle tre hjørner af en Fibonacci-terning kan findes ved at beregne den bitvise majoritetsfunktion af de tre etiketter. Hvis hver af de tre etiketter ikke har to på hinanden følgende 1 bit, så gælder det samme for deres majoritetsværdi.

Fibonacci-terningen er også en graf over et distributivt gitter , som kan fås via Birkhoffs sætning fra et " hegn ", et delvist ordnet sæt defineret af en vekslende sekvens af relationer [6] . Der er også en alternativ beskrivelse i torii af grafer af samme gitter: de uafhængige sæt af enhver todelt graf kan gives i en bestemt rækkefølge, hvor det ene uafhængige sæt er mindre end det andet, hvis de opnås ved at fjerne elementer fra en del og tilføjelse af elementer til en anden del. Med denne rækkefølge danner uafhængige mængder et distributivt gitter [7] , og anvendelse af denne konstruktion på en stigraf fører til associeringen af ​​gitteret med Fibonacci-terningen.

Egenskaber og algoritmer

Fibonacci-terningen af ​​orden n kan opdeles i Fibonacci-terningen af ​​orden (nodemærkning starter med en bitværdi på 0) og Fibonacci-terningen af ​​orden (knuder starter med bitværdi 1) [8] .

Enhver Fibonacci-terning har en Hamilton-sti . Mere specifikt er der en sti, der omgår partitionen beskrevet ovenfor - den besøger først noder med 0 og derefter med 1 i to sammenhængende undersekvenser. I disse to delsekvenser kan stien bygges rekursivt efter samme regel, idet de to delsekvenser forbindes med ender, hvor den anden bit har værdien 0. Derefter f.eks. i Fibonacci-terningen af ​​orden 4, sekvensen konstrueret i denne måde vil være (0100-0101-0001- 0000-0010)-(1010-1000-1001), hvor parenteserne angiver underfølger af to undergrafer. Fibonacci-terninger med et lige antal noder større end to har en Hamilton-cyklus [9] .

Munarini og Salvi [10] studerede radius og uafhængighedsantallet af Fibonacci-terninger. Da disse grafer er todelte og har Hamiltonske stier, har deres maksimale uafhængige sæt et antal knudepunkter, der er lig med halvdelen af ​​spidserne af hele grafen, rundet op til det nærmeste heltal [11] . Diameteren af ​​en Fibonacci-terning af orden n er n og dens radius er n /2 (igen, afrundet til nærmeste heltal) [12] .

Taranenko og Vesel [13] viste, at det er muligt at kontrollere, om en graf er en Fibonacci-terning i tid tæt på dens størrelse.

Ansøgninger

Xu [1] såvel som Xu, Page og Liu [14] foreslog brugen af ​​Fibonacci-terninger som netværkstopologi i parallelle computersystemer . Som et kommunikationsnetværk har Fibonacci-terningen nyttige egenskaber, der ligner dem for en hyperkube - antallet af indfaldende kanter pr. vertex overstiger ikke n /2, og netværkets diameter overstiger ikke n , begge værdier er proportionale med logaritmen af ​​antallet af hjørner og evnen til at opdele netværket i mindre undernet af samme type tillader opdeling af mange opgaver med parallel databehandling [9] . Fibonacci-kuber understøtter også effektive protokoller til routing og udsendelse i distribuerede computersystemer [1] [15] .

Klavzhar og Zhigert anvendte Fibonacci-terninger i kemisk grafteori som en beskrivelse af en familie af perfekte matchninger af nogle molekylære grafer [16] . For en molekylær struktur beskrevet af en plan graf G er resonansgrafen (eller Z -transformgrafen) af grafen G en graf, hvis toppunkter beskriver perfekte matchninger af grafen G , og hvis kanter forbinder par af perfekte matchninger, hvis symmetriske forskel er et indre forside af graf G. Polycykliske aromatiske carbonhydrider kan beskrives som subgrafer af en hexagonal flisebelægning af planet, og resonansgrafer beskriver de mulige dobbeltbindingsstrukturer af disse molekyler. Som vist af Klavzhar og Zhigert [16] har kulbrinter dannet af kæder af kant-til-kant sekskanter uden tre tilstødende sekskanter på linjen resonansgrafer, der er nøjagtigt Fibonacci-graferne. Mere generelt beskrev Zhang, Ou og Yao en klasse af plane todelte grafer, der har Fibonacci-terninger som resonansgrafer [17] [3] .

Relaterede grafer

Generaliserede Fibonacci-terninger blev foreslået af Xu og Zhang [18] baseret på k -te ordens Fibonacci-tal, som senere Xu, Zhang og Das, baseret på mere generelle typer af lineære rekursioner, udvidede til en klasse af netværk kaldet lineære rekursive netværk [19 ] . Wu modificerede andenordens Fibonacci-terninger baseret på forskellige begyndelsesbetingelser [20] . En anden relateret graf er Lucas-terningen, med antallet af hjørner lig med Lucas-tallet , defineret ud fra Fibonacci-terningen ved at inhibere en bit med en værdi på 1 i både den første og sidste position af hver bitstreng. Dedo, Torri og Salvi brugte farveegenskaberne for både Fibonacci og Lucas terninger [21] .

Noter

  1. ↑ 1 2 3 Hsu, 1993 .
  2. ↑ Klavžar, 2011 , s. 3-4.
  3. ↑ 1 2 Klavžar, 2011 , s. 3.
  4. ↑ Klavžar, 2005 .
  5. ↑ Klavžar, 2011 , s. Sætning 5.1.
  6. ↑ Gansner ( 1982 ) taler om det som et "velkendt faktum", at dette gitter har det samme antal elementer som Fibonacci-tallet, og Stanley ( Stanley 1986 ) overfører dette faktum til øvelser. Se også Höft & Höft 1985 , Beck 1990 og Salvi & Salvi 2008 .
  7. ↑ Propp, 1997 .
  8. ↑ Klavžar, 2011 , s. 4-5.
  9. ↑ 1 2 Cong, Zheng, Sharma, 1993 .
  10. ↑ Munarini, Salvi, 2002 .
  11. ↑ Klavžar, 2011 , s. 6.
  12. ↑ Klavžar, 2011 , s. 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 .

Litteratur