Fibonacci kub

Inom det matematiska området grafteori är Fibonacci -kuberna eller Fibonacci-nätverken en familj av oriktade grafer med rika rekursiva egenskaper som härrör från dess ursprung i talteorin . Matematiskt liknar de hyperkubgraferna , men med ett Fibonacci- antal hörn . Fibonacci-kuber definierades först uttryckligen i Hsu (1993) i samband med sammankopplingstopologier för att ansluta parallella eller distribuerade system. De har också tillämpats i kemisk grafteori .

Fibonacci-kuben kan definieras i termer av Fibonacci-koder och Hamming-avstånd , oberoende uppsättningar av hörn i väggrafer , eller via distributiva gitter .

Definition

Liksom hyperkubgrafen kan topparna i Fibonacci-kuben av ordning n vara märkta med bitsträngar av längden n , på ett sådant sätt att två hörn är intill varandra när deras etiketter skiljer sig åt i en enda bit. Men i en Fibonacci-kub är de enda etiketter som är tillåtna bitsträngar utan två på varandra följande 1-bitar. Om etiketterna för hyperkuben tolkas som binära tal , är etiketterna i Fibonacci-kuben en delmängd, de fibbinära talen . Det finns F _{n + 2} etiketter möjliga, där F _n betecknar det n :te Fibonacci-talet, och därför finns det F _{n + 2} hörn i Fibonacci-kuben av ordningen n .

Fibonacci-kuber (ritade i rött) som subgrafer av hyperkuber

Noderna i ett sådant nätverk kan tilldelas konsekutiva heltal från 0 till Fn _{; + 2} − 1 bitsträngarna som motsvarar dessa nummer ges av deras Zeckendorf-representationer .

Fibonacci-kuben av ordning 6

Algebraisk struktur

Fibonacci-kuben av ordning n är simplexgrafen för komplementgrafen för en n -vertex-banagraf. Det vill säga att varje vertex i Fibonacci-kuben representerar en klick i vägkomplementgrafen, eller motsvarande en oberoende uppsättning i själva vägen; två Fibonacci-kubhörn ligger intill om klicken eller oberoende uppsättningar som de representerar skiljer sig åt genom tillägg eller borttagning av ett enda element. Därför, precis som andra simplexgrafer, är Fibonacci-kuber mediangrafer och mer allmänt partiella kuber . Medianen för alla tre hörn i en Fibonacci-kub kan hittas genom att beräkna den bitvisa majoritetsfunktionen för de tre etiketterna; om var och en av de tre etiketterna inte har två på varandra följande 1-bitar, gäller detsamma för deras majoritet.

Fibonacci-kuben är också grafen för ett distributivt gitter som kan erhållas via Birkhoffs representationssats från en sicksackposet , en delvis ordnad mängd definierad av en alternerande sekvens av ordningsrelationer a < b > c < d > e < f > .. Det finns också en alternativ grafteoretisk beskrivning av samma gitter: de oberoende uppsättningarna av en tvådelad graf kan ges en partiell ordning där en oberoende uppsättning är mindre än en annan om de skiljer sig åt genom att ta bort element från en sida av den tvådelade grafen och lägga till element till den andra sidan av bipartitionen; med denna ordning bildar de oberoende uppsättningarna ett distributivt gitter, och applicering av denna konstruktion på en väggraf resulterar i det gitter som är associerat med Fibonacci-kuben.

Egenskaper och algoritmer

Fibonacci-kuben av ordningen n kan delas upp i en Fibonacci-kub av ordningen n − 1 (noderna med etiketter som börjar med en 0-bit) och en Fibonacci-kub av ordningen n − 2 (noderna med etiketter som börjar med en 1-bit).

Varje Fibonacci-kub har en Hamiltonsk väg . Mer specifikt finns det en väg som följer partitionen som beskrivs ovan: den besöker noderna med första bit 0 och noderna med första bit 1 i två sammanhängande delsekvenser. Inom dessa två delsekvenser kan vägen konstrueras rekursivt av samma regel, och länka de två delsekvenserna i ändarna av delsekvenserna där den andra biten är 0. Således, t.ex. i Fibonacci-kuben av ordning 4, sekvensen konstruerad i detta sätt är (0100-0101-0001-0000-0010)-(1010-1000-1001), där parenteserna markerar undersekvenserna inom partitionens två subgrafer. Fibonacci-kuber med ett jämnt antal noder större än två har en Hamiltonsk cykel .

Munarini & Salvi (2002) undersöker radien och antalet oberoende Fibonacci-kuber. Eftersom dessa grafer är tvådelade och har Hamiltonska banor, har deras maximala oberoende uppsättningar ett antal hörn som är lika med hälften av antalet hörn i hela grafen, avrundat uppåt till närmaste heltal. Diametern på en Fibonacci-kub av ordningen n är n och dess radie är n /2 (återigen, avrundat uppåt till närmaste heltal).

Taranenko & Vesel (2007) visade att det är möjligt att testa om en graf är en Fibonacci-kub i tid nästan linjär i sin storlek.

Ansökningar

Hsu (1993) och Hsu, Page & Liu (1993) föreslog att Fibonacci-kuber skulle användas som nätverkstopologi vid parallell beräkning . Som ett kommunikationsnätverk har Fibonacci-kuben fördelaktiga egenskaper som liknar hyperkubens: antalet infallande kanter per vertex är som mest n /2 och nätverkets diameter är som mest n , båda proportionella mot talets logaritm av hörn, och nätverkets förmåga att delas upp i mindre nätverk av samma typ gör att det kan delas upp mellan flera parallella beräkningsuppgifter. Fibonacci-kuber stöder också effektiva protokoll för routing och sändning i distribuerade beräkningar.

Klavžar & Žigert (2005) tillämpar Fibonacci-kuber i kemisk grafteori som en beskrivning av familjen perfekta matchningar av vissa molekylära grafer. För en molekylstruktur som beskrivs av en plan graf G , är resonansgrafen eller ( Z -transformationsgrafen) för G en graf vars hörn beskriver perfekt matchning av G och vars kanter förbinder par av perfekta matchningar vars symmetriska skillnad är en inre yta av G . Polycykliska aromatiska kolväten kan beskrivas som subgrafer av en hexagonal beläggning av planet, och resonansgrafen beskriver möjliga dubbelbindningsstrukturer för dessa molekyler. Som Klavžar & Žigert (2005) visar, har kolväten som bildas av kedjor av hexagoner, länkade kant-till-kant utan tre intilliggande hexagoner på en linje, resonansgrafer som är exakt Fibonacci-graferna. Mer allmänt Zhang, Ou & Yao (2009) klassen av plana tvådelade grafer som har Fibonacci-kuber som sina resonansgrafer.

Relaterade grafer

Generaliserade Fibonacci-kuber presenterades av Hsu & Chung (1993) baserade på k-te ordningens Fibonacci-tal, som senare utökades ytterligare till en större klass av nätverk kallade Linear Recursive Networks av Hsu, Chung & Das (1997) baserat på mer allmänna former av linjära rekursioner. Wu (1997) modifierade andra ordningens Fibonacci-kuber baserat på olika initiala förhållanden. En annan relaterad graf är Lucas-kuben, en graf med ett Lucas antal hörn definierade från Fibonacci-kuben genom att förbjuda en 1 bit i både den första och sista positionen av varje bitsträng; Dedó, Torri & Salvi (2002) undersökte färgegenskaperna hos både Fibonacci-kuber och Lucas-kuber.

Anteckningar

•   Beck, István (1990), "Partial orders and the Fibonacci numbers", Fibonacci Quarterly , 28 (2): 172–174, MR 1051291 .
•   Cong, B.; Zheng, SQ; Sharma, S. (1993), "Om simuleringar av linjära arrayer, ringar och 2D-maskor på Fibonacci-kubnätverk", Proc. 7:e Int. Parallel Processing Symposium , s. 748–751, doi : 10.1109/IPPS.1993.262788 , S2CID 621063 .
• Dedó, Ernesto; Torri, Damiano; Salvi, Norma Zagaglia (2002), "The observability of the Fibonacci and the Lucas cubes", Discrete Mathematics , 255 (1–3): 55–63, doi : 10.1016/S0012-365X(01)00387-9 .
•   Gansner, Emden R. (1982), "On the lattice of order ideals of an up-down poset", Discrete Mathematics , 39 (2): 113–122, doi : 10.1016/0012-365X(82)90134-0 , MR 0675856 .
•   Höft, Hartmut; Höft, Margret (1985), "A Fibonacci sequence of distributive lattices", Fibonacci Quarterly , 23 (3): 232–237, MR 0806293 .
• Hsu, W.-J. (1993), "Fibonacci-kuber: en ny sammankopplingstopologi", IEEE Transactions on Parallel and Distributed Systems , 4 (1): 3–12, doi : 10.1109/71.205649 .
•   Hsu, W.-J.; Chung, MJ (1993), "Generaliserade Fibonacci-kuber", 1993 International Conference on Parallel Processing - ICPP'93 , vol. 1, s. 299–302, doi : 10.1109/ICPP.1993.95 , S2CID 15982621 .
• Hsu, W.-J.; Sida, CV; Liu, J.-S. (1993), "Fibonacci cubes: a class of self-similar graphs", Fibonacci Quarterly , 31 (1): 65–72 .
• Hsu, W.-J.; Chung, MJ; Das, A. (1997), "Linjära rekursiva nätverk och deras tillämpningar i distribuerade system", IEEE Transactions on Parallel and Distributed Systems , 8 (7): 673–680, doi : 10.1109/71.598343 .
• Klavžar, Sandi (2005), "On median nature and enumerative properties of Fibonacci-like cubes", Discrete Mathematics , 299 (1–3): 145–153, doi : 10.1016/j.disc.2004.02.023 .
• Klavžar, Sandi (2011), "Structure of Fibonacci cubes: a survey" (PDF) , IMFM Preprint Series , Ljubljana, Slovenien: Institute of Mathematics, Physics and Mechanics, 49 (1150) .
• Klavžar, Sandi; Žigert, Petra (2005), "Fibonacci cubes are the resonance graphs of Fibonaccenes" , Fibonacci Quarterly , 43 (3): 269–276, arkiverad från originalet 2007-02-08 .
• Munarini, Emanuele; Salvi, Norma Zagaglia (2002), "Strukturella och uppräknade egenskaper hos Fibonacci-kuberna", Diskret matematik , 255 (1–3): 317–324, doi : 10.1016/S0012-365X(01) 00407-1 .
•   Propp, James (1997), "Generating random elements of finite distributive lattices", Electronic Journal of Combinatorics , 4 (2): R15, arXiv : math.CO/9801066 , doi : 10.37236/1330 , S2CID 8 1331 .
•   Salvi, Rodolfo; Salvi, Norma Zagaglia (2008), "Alternating unimodal sequences of Whitney numbers", Ars Combinatoria , 87 : 105-117, MR 2414008 .
• Stanley, Richard P. (1986), Enumerative Combinatorics , Wadsworth, Inc. Övning 3.23a, sid 157.
• Stojmenovic, Ivan (1998), "Optimal dödlägesfri routing och sändning på Fibonacci-kubnätverk" (PDF) , Utilitas Mathematica , 53 : 159–166, arkiverad från originalet (PDF) 2011-07-25 .
•   Taranenko, A.; Vesel, A. (2007), "Fast recognition of Fibonacci cubes", Algorithmica , 49 (2): 81–93, doi : 10.1007/s00453-007-9026-5 , S2CID 993779 .
• Wu, Jie (1997), "Extended Fibonacci-kuber", IEEE Transactions on Parallel and Distributed Systems , 8 (12): 1203–1210, doi : 10.1109/71.640012 .
•   Zhang, Heping; Ou, Lifeng; Yao, Haiyuan (2009), "Fibonacci-liknande kuber som Z -transformationsgrafer", Discrete Mathematics , 309 (6): 1284–1293, doi : 10.1016/j.disc.2008.01.053 , MR 251053 .