Apollonius-grafen [1] är en oriktad graf som bildas av den rekursiva processen att dela en triangel i tre mindre trianglar. Apollonius-grafer kan definieras på samma sätt som plana 3-träd , som maximala plana kordalgrafer , som unikt 4-färgbara plana grafer eller som blockpolytopgrafer . Graferna är uppkallade efter Apollonius av Perga , som studerade relaterade cirkelpackningskonstruktioner.
Apollonius-grafen kan erhållas från en triangulär graf inbäddad i det euklidiska planet genom att upprepade gånger välja en triangulär häckande yta, lägga till en ny vertex till den triangulära ytan och koppla den nya vertexen till varje vertex inuti ansiktet. Som ett resultat är ansiktet uppdelat i tre mindre trianglar, som i sin tur kan delas på samma sätt.
Kompletta grafer med tre och fyra hörn, K 3 och K 4 , är Apollonius-grafer. K3 bildas av den initiala triangeln utan ytterligare indelningsoperationer, medan K4 bildas av en enda indelningsoperation.
Goldner-Harari-grafen är Apollonius-grafen och även den minsta icke-Hamiltoniska maximala plana grafen [2] . En annan mer komplex Apollonius-graf användes av Nishizeki [3] som ett exempel på en 1-rigid icke-Hamiltonisk maximal plan graf.
Eftersom Apollonius-grafer definieras av rekursiv uppdelning av trianglar, har de olika matematiska beskrivningar. Graferna är ackordala maximala plana grafer, ackordala polyedriska grafer och plana 3-träd . Graferna är unikt 4-färgbara plana grafer och plana grafer med en unik nedbrytning till en Schneider-skog bestående av tre träd. Grafer är maximala plana grafer med trädbredd tre, en klass av grafer som kan beskrivas med deras förbjudna grafer eller genom deras reduktion med Y-Δ-transformationer . Graferna är maximala plana grafer med degeneration tre. Grafer är också plana grafer med ett givet antal hörn som har största möjliga antal trianglar, största möjliga antal tetraedriska subgrafer, största möjliga antal klickar och största möjliga antal delar efter sönderdelning i enskilda trianglar.
Apollonius-grafer är exempel på maximala plana grafer till vilka en kant inte kan läggas till utan att bryta planariteten, eller på motsvarande sätt grafer som kan ritas i planet så att vilken yta (inklusive den yttre ytan) är en triangel. Grafer är också ackordsgrafer , där varje cykel med fyra eller fler hörn har en diagonal kant som förbinder två hörn av cykeln som inte är på varandra följande i cykeln, och ordningen i vilken hörn läggs till under konstruktionen av Apollonius-grafen är elimineringsordning i ackordsgrafen. Denna egenskap ger en alternativ beskrivning av Apollonius-grafer - de är exakt ackordala maximala plana grafer eller, ekvivalent, ackordala polyedriska grafer [4] .
I Apollonia-grafen är varje maximal klick en komplett graf med fyra hörn, bildad av valet av valfri vertex och tre närmaste grannar. Varje minimal klickseparator (en klick vars borttagning delar upp grafen i två frånkopplade grafer) är en av de delade trianglarna. En ackordsgraf där alla maximala klicker och alla minimiklickseparatorer har samma storlek är ett k -träd och Apollonius-grafer är exempel på 3 -träd. Alla 3-träd är inte plana, men plana 3-träd är exakt Apollonius-grafer.
Varje Apollonius-graf har en unik 4-färgsfärgning . Eftersom grafen är plan, antyder fyrfärgssatsen att grafen har en fyrfärgsfärgning , men eftersom färgerna i den initiala triangeln är fixerade, finns det bara ett val av färg för den nya vertexen, så upp till en permutation av färger kommer färgningen av grafen att vara unik. Det är svårare att visa, men det är också sant att varje plan graf med en enda färg är en Apollonius-graf. Således kan Apollonius-grafen karakteriseras som en plan graf med en unik 4-färgning [5] . Apollonius-grafer ger exempel på plana grafer som har det minsta antalet k -färgningar för k > 4 [6]
Dessutom är Apollonius-grafer exakt maximala plana grafer som (om den yttre ytan är fixerad) har en unik Schneider-skog , en uppdelning av grafens kanter i tre träd som är rotade vid hörnen på den yttre ytan [7] [8] .
Apollonius-grafer bildar inte en familj av grafer som är stängda med avseende på operationen att ta minor i grafen , eftersom när vi tar bort kanter, men inte hörn, får vi en graf som inte är en Apollonius-graf. Emellertid är familjen av plana partiella 3-träd , subgrafer av Apollonius-grafer, en mindre sluten familj. Således, enligt Robertson-Seymour-satsen , kan de karakteriseras av ett ändligt antal förbjudna minderåriga . De minimala förbjudna minorerna för plana partiella 3-träd är de fyra minimala graferna för plana grafer och partiella 3-träd: den fullständiga grafen K 5 , den fullständiga tvådelade grafen K 3,3 , den oktaedergrafen och den femkantiga prismagrafen . Apollonius-grafer är maximala grafer som inte innehåller dessa fyra grafer som underordnade [9]
En Y-Δ-transformation som ersätter en vertex av grad tre med en triangel som förbinder grannar är tillräcklig (tillsammans med operationen för borttagning av flera kant) för att reducera Apollonius-grafen till en enda triangel. Plana grafer som kan reduceras till en enda kant med en Y-Δ-transformation, ta bort flera kanter, ta bort hörn av grad 1 och ersätta en vertex av grad 2 med kanter med en enda kant, är exakt plana partiella 3-träd. De dubbla graferna av plana partiella 3-träd bildar en annan familj av grafer som är stängda med underåriga, vilket är exakt de grafer som kan reduceras till en enda kant med hjälp av Δ-Y-transformationen, ta bort flera kanter, ta bort hörn av grad 1, och bli av med hörn av grad 2 [10] .
I vilken subgraf som helst av en Apollonius-graf har den senast tillagda vertexen grad tre, så Apollonius-graferna har degeneration tre. Ordningen som hörn läggs till när man skapar en graf är alltså ordningen för degenerering, och Apollonius-grafer är samma som 3-degenererade maximala plana grafer.
En annan egenskap som kännetecknar Apollonius-grafer är anknytning . Alla maximala plana grafer kan delas upp i 4-vertex-anslutna maximala plana subgrafer genom att dela längs trianglar (inte grafytor) - om det finns en triangel som inte är en yta kan två mindre maximala plana grafer bildas, en bestående av del inuti triangeln , den andra består av en del utanför triangeln. Maximala plana grafer utan separerande trianglar, som genereras av flera partitioner av det här slaget, kallas ibland för block, även om samma namn också används för de tvåkopplade komponenterna i en graf som i sig inte är dubbelkopplad. Apollonius-grafen är en maximal plan graf där alla block är isomorfa till hela grafen K 4 .
I extremal grafteori är Apollonius-grafer exakt plana grafer med n hörn, där antalet block når maxvärdet n − 3 , och plana grafer, där antalet trianglar är maximalt och lika med 3 n − 8 . Eftersom varje K 4 subgraf i en plan graf måste vara ett block, når dessa grafer det maximala antalet K 4 subgrafer (detta antal är lika med n − 3 ). På samma grafer uppnås det maximala antalet klick av vilken typ som helst (antalet klick är 8 n − 16 ) [11]
Graferna är uppkallade efter Apollonius av Perga , som studerade problemet med att konstruera cirklar som tangerar tre andra cirklar. En metod för att konstruera Apollonius-grafer är att börja med tre ömsesidigt tangerande cirklar och upprepade gånger inskriva en annan cirkel i gapet som bildas av de tre cirklarna som byggdes tidigare. En fraktal som bildas på detta sätt kallas ett Apollonius-rutnät .
Om processen att konstruera Apollonius-rutnätet stoppas genom att bara rita ett ändligt antal cirklar, så är grafen som har en vertex för varje cirkel och en kant för två tangentcirklar Apollonius-grafen [12] . Förekomsten av en uppsättning tangentcirklar vars tangens representerar Apollonius-grafen bestäms av Koebe-Andreev-Thurston-satsen , som säger att vilken plan graf som helst kan representeras av tangentcirklar [13] .
Apollonius grafer är plana vertex 3-anslutna grafer , och därför, av Steinitz sats , kan alltid representeras som grafer av konvexa polyedrar . Den konvexa polytopen som representerar Apollonius-grafen är en 3-dimensionell blockpolytop . Sådana polyedrar kan erhållas från en tetraeder genom att upprepade gånger limma ytterligare tetraedrar (en åt gången) på polyederns triangulära ytor. Således kan Apollonius-grafer definieras som grafer av blockets 3-dimensionella polyedrar [14] . Det är möjligt att hitta en representation av vilken Apollonius-graf som helst som en konvex 3-dimensionell polyeder där alla koordinater är polynomiska heltal, vilket är bättre än för andra plana grafer [15] .
Den rekursiva uppdelningen av trianglar i tre mindre trianglar utforskades av Elcock, Gargantini och Walsh som en bildsegmenteringsteknik i datorseende [16] . I detta sammanhang hänvisar de till en sådan uppdelning som en trippel oliksidig triangelupplösning . De märkte att när varje ny vertex läggs till tyngdpunkten i en triangel, kommer trianguleringstrianglarna att ha samma area, även om de inte har samma form. Mer generellt kan Apollonius-grafer ritas i planet, med valfritt förutbestämt område av varje ansikte. Om områdena ges som rationella tal , så kommer koordinaterna för hörnen [17] .
Det är möjligt att utföra processen att dividera trianglar när man konstruerar Apollonius-grafen på ett sådant sätt att längden på kanterna vid varje steg kommer att vara rationella tal. Det är inte känt om någon plan graf med samma egenskaper kan ritas [18] . I polynomtid kan man hitta en ritning av ett plant 3-träd med heltalskoordinater med en minsta area av begränsningsrutan och kontrollera om ett givet plant 3-träd kan ritas med hörn vid en given uppsättning punkter [19 ]
Plummer [20] använde Apollonius-grafer för att konstruera en oändlig familj av maximala plana grafer med ett jämnt antal hörn som inte har en perfekt matchning . Plummer grafer byggs i två steg. I det första skedet, med början från triangeln abc , upprepas uppdelningen av den triangulära ytan som innehåller kanten bc många gånger . Den resulterande grafen innehåller en väg från a till den slutliga delningspunkten, och varje hörn på denna väg är ansluten med kanter till hörn b och c . I det andra steget delas varje (triangulär) yta av den resulterande plana grafen igen. Om vägen från a till det sista hörnet av partitionen i det första steget har en jämn längd, är det totala antalet hörn i grafen också jämnt. Men cirka 2/3 av de hörn som infogas i det andra steget bildar en oberoende uppsättning och kan inte matcha varandra, och de återstående hörnen räcker inte för att bilda en perfekt matchning.
Även om Apollonius-grafer i sig inte kan ha perfekt matchning, är grafer dubbla till Apollonius-grafer 3-regelbundna grafer utan skärkanter , så enligt Petersens sats [21] har de nödvändigtvis minst en perfekt matchning. För Apollonius-grafer är ännu mer känt - grafer som är dubbla till Apollonius-grafer har ett exponentiellt stort antal perfekta matchningar [22] . Laszlo Lovas och Michael D. Plummer förmodade att en liknande exponentiell nedre gräns borde finnas för alla 3-regelbundna grafer utan skärande kanter, vilket senare bekräftades.
J. Andrade, G. Herrmann, R. Andrade och L. de Silva [12] studerade maktlagarna för sekvenser av grader av speciella typer av grafer av denna typ som bildas genom att dela alla trianglar lika många gånger. De använde dessa grafer för att modellera fyllningen av rymden med delar av olika storlekar. Baserat på deras arbete föreslog andra författare slumpmässiga Apollonius-grafer som erhållits genom att slumpmässigt välja ett ansikte för division, och visade att dessa grafer följer en maktlag i fördelningen av grader av hörn [23] , och visade också att dessa grafer har små avstånd [ 23] 24] [25] . Freese och Tsourakakis analyserade de största graderna av hörn och egenvärden för slumpmässiga Apollonius-grafer [26] . J. Andrade, G. Herrmann, R. Andrade och L. de Silva märkte också att deras grafer uppfyller " lilla världen "-effekten (teorin om sex handslag), det vill säga att alla hörn är på nära avstånd från varandra . Baserat på numeriska experiment uppskattade de det genomsnittliga avståndet mellan slumpmässigt utvalda hörnpar i en n -vertexgraf som proportionell mot (log n ) 3/4 , men ytterligare forskning visade att det genomsnittliga avståndet faktiskt var proportionellt mot log n [27] [28] .
Butler och Graham [29] noterade att om varje ny vertex placeras i skärningspunkten för en triangels bisektrar, då uppsättningen triangelvinklar av trianglar i en underavdelning, om den tolkas som de barycentriska koordinaterna för punkter i en vanlig triangel , bildar en Sierpinski-triangel i gränsen när nivån på indelningen ökar.
Takeo [30] hävdade felaktigt att alla Apollonius-grafer har Hamiltonska cykler , men Goldner-Harari-grafen ger ett motexempel. Om en Apollonius-graf har en styvhet som är större än en (vilket innebär att om man tar bort valfritt antal hörn från grafen lämnas färre sammankopplade komponenter än antalet borttagna hörn), är det nödvändigtvis Hamiltonskt, men det finns icke-Hamiltonska Apollonius-grafer om styvheten är en [31]
Uppgiften av kombinatorik för att beräkna Apollonius triangulationer studerades av Takeo [30] . Han visade att för antalet trianguleringar finns en enkel genererande funktion f ( x ) som beskrivs av likheten f ( x ) = 1 + x ( f ( x )) 3 . I denna genererande funktion innehåller termen grad n antalet Apollonius-grafer med en yttre triangel och n + 3 hörn. Antal Apollonius-grafer (med yttre triangel) och 3, 4, 5, ... hörn:
1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, ... (sekvens A001764 i OEIS ).Samma sekvens specificerar antalet ternära träd och antalet partitioner av en konvex polygon i polygoner med ett udda antal sidor. Till exempel finns det 12 Apollonius-grafer med 6 hörn - tre bildas genom att dela den yttre triangeln, följt av att dela två av de resulterande trianglarna, och nio till bildas genom att dela den yttre triangeln och dela en av de resulterande trianglarna, följt av dela en av de små trianglarna.
Birkhoff [32] har en tidig uppsats som använder den dubbla formen av Apollonius-grafer, plana kartor som bildas genom att upprepade gånger placera nya områden på hörnen på enklare kartor, som ett exempel på en klass av plana grafer med få färger.
Geometriska strukturer som liknar Apollonius-grafer har studerats i kombinatorik av polyedrar sedan början av 1960-talet, då de användes av Grünbaum [33] för att beskriva grafer som kan realiseras i polyedrar på ett unikt sätt vad gäller dimension och ur synvinkel av kombinatorik. De användes också av Moon och Moser [34] för att söka efter enkla polyedrar utan långa vägar. Inom grafteorin kan det nära sambandet mellan planhet och trädbredd spåras tillbaka till en artikel från 1984 av Robertson och Seymour [35] , som visade att en familj av grafer som är slutna med mindreåriga antingen har en begränsad trädbredd eller innehåller alla plana grafer. Plana 3-träd som en klass av grafer betraktades av Hakimi och Schmeichel [36] , Alon och Caro [37] , Patil [38] och många andra författare efter dem.
Namnet "graf över Apollonia" föreslogs i artikeln av J. Andrade, G. Herrmann, R. Andrade och L. de Silva [12] för grafer där trianglarnas indelningsnivå är homogen. Geometriskt motsvarar dessa grafer blockpolytoper ( Klee polytopes ) [33] [39] . Andra författare har använt termen för en bredare klass av grafer, plana 3-träd, för att generalisera modellen till slumpmässiga Apollonius-grafer [24] [25] . Den sålunda erhållna triangulariseringen har också kallats "blocktriangularisering" [37] [40] [41] [7] [27] [8] [22] .