Apolloniska nätverk

Ett apolloniskt nätverk
Goldner –Harary-grafen , ett icke-hamiltonskt apollonskt nätverk

I kombinatorisk matematik är ett Apolloniskt nätverk en oriktad graf som bildas av en process där en triangel rekursivt delas in i tre mindre trianglar. Apolloniska nätverk kan på motsvarande sätt definieras som de plana 3-träden , de maximala plana kordalgraferna, de unikt 4-färgbara plana graferna och graferna för staplade polytoper . De är uppkallade efter Apollonius av Perga , som studerade en relaterad cirkel-packande konstruktion.

Definition

Ett apolloniskt nätverk kan bildas, utgående från en enda triangel inbäddad i det euklidiska planet , genom att upprepade gånger välja en triangulär yta av inbäddningen, lägga till en ny vertex inuti ytan och ansluta den nya vertexen till varje vertex av ytan som innehåller den. På så sätt delas triangeln som innehåller det nya hörnet in i tre mindre trianglar, som i sin tur kan delas upp på samma sätt.

Exempel

De fullständiga graferna på tre och fyra hörn, K 3 och K 4 , är båda apolloniska nätverk. K 3 bildas genom att börja med en triangel och inte utföra några indelningar, medan K 4 bildas genom att göra en enda indelning innan man stoppar.

Goldner -Harary-grafen är ett apolloniskt nätverk som bildar den minsta icke-Hamiltonska maximala plana grafen. Ett annat mer komplicerat apolloniskt nätverk användes av Nishizeki (1980) för att tillhandahålla ett exempel på en 1-tuff icke-Hamiltonisk maximal planär graf.

Grafteoretiska karaktäriseringar

Förutom att de definieras av rekursiv indelning av trianglar, har de apolloniska nätverken flera andra likvärdiga matematiska karaktäriseringar. De är de ackordala maximala plana graferna, de ackordala polyedriska graferna och de plana 3-träden . De är de unikt 4-färgbara plana graferna och de plana graferna med en unik Schnyder- tränedbrytning i tre träd. De är de maximala plana graferna med trädbredd tre, en klass av grafer som kan karakteriseras av deras förbjudna mindreåriga eller av deras reducerbarhet under Y-Δ-transformer . De är de maximala plana graferna med degeneration tre. De är också de plana graferna på 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 bitar efter nedbrytning genom att separera trianglar.

Kordalitet

Apolloniska nätverk är exempel på maximala plana grafer , grafer till vilka inga ytterligare kanter kan läggas till utan att förstöra planariteten, eller motsvarande grafer som kan ritas i planet så att varje yta (inklusive den yttre ytan) är en triangel. De är också ackordsgrafer , grafer där varje cykel med fyra eller fler hörn har en diagonal kant som förbinder två icke på varandra följande kretsar, och ordningen i vilken hörn läggs till i underindelningsprocessen som bildar ett apolloniskt nätverk är en elimineringsordning som en ackordsgraf. Detta bildar en alternativ karaktärisering av de apolloniska nätverken: de är exakt de ackordala maximala plana graferna eller ekvivalent de ackordala polyedriska graferna .

I ett Apolloniskt nätverk är varje maximal klick en komplett graf på fyra hörn, bildad genom att välja vilken vertex som helst och dess tre tidigare grannar. Varje minimal klickseparator (en klick som delar upp grafen i två frånkopplade subgrafer) är en av de uppdelade trianglarna. En ackordsgraf där alla maximala klick och alla minimala klickseparatorer har samma storlek är ett k - träd och Apolloniska nätverk är exempel på 3-träd. Inte alla 3-träd är plana, men de plana 3-träden är exakt de apolloniska nätverken.

Unik färgbarhet

Varje Apolloniskt nätverk är också en unik 4-färgbar graf . Eftersom det är en plan graf, fyrfärgssatsen att den har en graffärgning med endast fyra färger, men när de tre färgerna i den initiala triangeln väl har valts finns det bara ett möjligt val för färgen på varje på varandra följande vertex, så upp till permutation av färguppsättningen har den exakt en 4-färgning. Det är svårare att bevisa, men också sant, att varje unikt 4-färgbar plan graf är ett apolloniskt nätverk. Därför kan Apolloniska nätverk också karakteriseras som de unikt 4-färgbara plana graferna. Apolloniska nätverk ger också exempel på plana grafer som har så få k -färgningar som möjligt för k > 4 .

De Apolloniska nätverken är också exakt de maximala plana graferna som (när en yttre yta väl är fixerad) har ett unikt Schnyder-trä , en uppdelning av grafens kanter i tre sammanflätade träd rotade vid de tre hörnen på den yttre ytan.

Trädbredd

De apolloniska nätverken bildar inte en familj av grafer som är stängda under driften av att ta grafer underordnade , eftersom att ta bort kanter men inte hörn från ett apolloniskt nätverk producerar en graf som inte är ett apolloniskt nätverk. De plana partiella 3-träden , subgrafer av Apolloniska nätverk, är dock mindre stängda. Därför, enligt Robertson-Seymour-satsen , kan de karakteriseras av ett ändligt antal förbjudna minderåriga . De minimala förbjudna minorerna för de plana partiella 3-träden är de fyra minimala graferna bland de förbjudna minorerna för de plana graferna och de partiella 3-träden: den fullständiga grafen K 5 , den fullständiga tvådelade grafen K 3,3 , grafen för oktaeder och grafen för det femkantiga prismat . De Apolloniska graferna är de maximala graferna som inte har någon av dessa fyra grafer som en mindre.

En Y-Δ-transform , en operation som ersätter en grad-tre vertex i en graf med en triangel som förbinder dess grannar, är tillräcklig (tillsammans med borttagandet av parallella kanter) för att reducera alla apolloniska nätverk till en enda triangel, och mer generellt Plana grafer som kan reduceras till en enda kant genom Y-Δ-transformationer, borttagning av parallella kanter, borttagning av grad-1-hörn och komprimering av grad-två-hörn är exakt de plana partiella 3-träden. De dubbla graferna för de plana partiella 3-träden bildar en annan mindre sluten graffamilj och är exakt de plana graferna som kan reduceras till en enda kant genom Δ-Y-transformeringar, avlägsnande av parallella kanter, avlägsnande av grad-1-hörn, och komprimering av grad-två hörn.

Degeneration

I varje subgraf av ett apolloniskt nätverk har det senast tillagda vertexet grad som högst tre, så apollonska nätverk har degeneration tre. Ordningen i vilken hörnen läggs till för att skapa nätverket är därför en degenerationsordning, och de apolloniska nätverken sammanfaller med de 3-degenererade maximala plana graferna.

Extremitet

En annan karaktärisering av de apolloniska nätverken handlar om deras anslutningsmöjligheter . Vilken maximal plan graf som helst kan delas upp i 4-vertex-anslutna maximala plana subgrafer genom att dela den längs dess separerande trianglar (trianglar som inte är ytor på grafen): givet en icke-ansiktstriangel: man kan bilda två mindre maximala plana grafer, den ena består av delen innanför triangeln och den andra består av delen utanför triangeln. De maximala plana graferna utan separerande trianglar som kan bildas av upprepade splittringar av denna typ kallas ibland för block, även om det namnet också har använts för de tvåkopplade komponenterna i en graf som i sig inte är dubbelkopplad. Ett apolloniskt nätverk är en maximal plan graf där alla blocken är isomorfa till hela grafen K 4 .

I extremal grafteori är Apolloniska nätverk också exakt de n -vertex plana graferna där antalet block når sitt maximum, n − 3 , och de plana graferna där antalet trianglar når sitt maximum, 3 n − 8 . Eftersom varje K 4- undergraf i en plan graf måste vara ett block, är dessa också de plana graferna där antalet K 4 -undergrafer når sitt maximum, n − 3 , och de grafer där antalet klick av vilken typ som helst uppnår sitt maximalt 8 n − 16 .

Geometriska realiseringar

Konstruktion från cirkelpackningar

Ett exempel på en Apollonsk packning
Konstruktion av ett Apolloniskt nätverk från en cirkelpackning

Apolloniska nätverk är uppkallade efter Apollonius av Perga , som studerade problemet med Apollonius att konstruera en cirkel som tangerar tre andra cirklar. En metod för att konstruera apolloniska nätverk är att börja med tre ömsesidigt tangerande cirklar och sedan upprepade gånger inskriva en annan cirkel i gapet som bildas av tre tidigare ritade cirklar. Den fraktala samlingen av cirklar som produceras på detta sätt kallas en Apollonsk packning .

Om processen att producera en apollonsk packning stoppas tidigt, med endast en ändlig uppsättning cirklar, så är grafen som har en vertex för varje cirkel och en kant för varje par tangentcirklar ett apolloniskt nätverk. Förekomsten av en uppsättning tangentcirklar vars tangenser representerar ett givet apolloniskt nätverk utgör ett enkelt exempel på Koebe–Andreev–Thurstons cirkelpackningssats , som säger att vilken plan graf som helst kan representeras av tangentcirklar på samma sätt.

Polyedra

Triakis -tetraedern , en polyedrisk realisering av ett apolloniskt nätverk med 8 vertex

Apolloniska nätverk är plana 3-anslutna grafer och kan därför, enligt Steinitzs sats , alltid representeras som graferna för konvexa polyedrar . Den konvexa polyedern som representerar ett Apolloniskt nätverk är en 3-dimensionell staplad polytop . En sådan polytop kan erhållas från en tetraeder genom att upprepade gånger limma ytterligare tetraedrar en i taget på dess triangulära ytor. Därför kan Apolloniska nätverk också definieras som graferna för staplade 3d-polytoper. Det är möjligt att hitta en representation av vilket apolloniskt nätverk som helst som konvex 3d-polyeder där alla koordinater är heltal av polynomstorlek, bättre än vad som är känt för andra plana grafer.

Triangelnät

Den rekursiva uppdelningen av trianglar i tre mindre trianglar undersöktes som en bildsegmenteringsteknik i datorseende av Elcock, Gargantini & Walsh (1987) ; i detta sammanhang kallade de det den ternära skalan triangelupplösningen . De observerade att, genom att placera varje ny vertex vid tyngdpunkten för dess omslutande triangel, kunde trianguleringen väljas på ett sådant sätt att alla trianglar har lika stora arealer, även om de inte alla har samma form. Mer allmänt kan apolloniska nätverk ritas i planet med vilket som helst föreskrivet område i varje yta; om områdena är rationella tal , så är alla vertexkoordinaterna.

Det är också möjligt att utföra processen att dela upp en triangel för att bilda ett apolloniskt nätverk på ett sådant sätt att kantlängderna vid varje steg är rationella tal; Det är ett öppet problem om varje plan graf har en ritning med denna egenskap. Det är möjligt i polynomtid att hitta en ritning av ett plant 3-träd med heltalskoordinater som minimerar arean av ritningens begränsningslåda, och att testa om ett givet plant 3-träd kan ritas med sina hörn på en given mängd poäng.

Egenskaper och applikationer

Matchningsfria grafer

Plummer (1992) använde Apolloniska nätverk för att konstruera en oändlig familj av maximala plana grafer med ett jämnt antal hörn men utan perfekt matchning . Plummers grafer bildas i två steg. I det första steget, med utgångspunkt från en triangel abc , delar man upprepade gånger in den triangulära ytan av underavdelningen som innehåller kant bc : resultatet är en graf som består av en väg från a till den slutliga indelningspunkten tillsammans med en kant från varje banas vertex till var och en av b och c . I det andra steget delas var och en av de triangulära ytorna i den resulterande plana grafen upp en gång till. Om vägen från a till den sista indelningspunkten för det första steget har jämn längd, är antalet hörn i den övergripande grafen också jämnt. Emellertid är ungefär 2/3 av hörnen de som är insatta i det andra steget; dessa bildar en oberoende uppsättning , och kan inte matchas med varandra, och det finns inte heller tillräckligt med hörn utanför den oberoende uppsättningen för att hitta matchningar för dem alla.

Även om Apollonska nätverk i sig kanske inte har perfekta matchningar, är de plana dubbla graferna för Apollonska nätverk 3-regelbundna grafer utan avskurna kanter , så enligt en teorem från Petersen (1891) är de garanterade att ha minst en perfekt matchning. Men i det här fallet är mer känt: dualerna av Apolloniska nätverk har alltid ett exponentiellt antal perfekta matchningar. László Lovász och Michael D. Plummer gissade att en liknande exponentiell nedre gräns gäller mer generellt för varje 3-regelbunden graf utan avskurna kanter, ett resultat som senare bevisades.

Maktlagsgrafer

Andrade et al. (2005) studerade maktlagar i gradsekvenserna i ett specialfall av nätverk av denna typ, bildade genom att dela upp alla trianglar lika många gånger. De använde dessa nätverk för att modellera packningar av rymd av partiklar av varierande storlek. Baserat på sitt arbete introducerade andra författare slumpmässiga apollonska nätverk, bildade genom att upprepade gånger välja ett slumpmässigt ansikte att dela upp, och de visade att dessa också lyder maktlagar i sin gradfördelning och har små medelavstånd. Alan M. Frieze och Charalampos E. Tsourakakis analyserade de högsta graderna och egenvärdena för slumpmässiga apollonska nätverk. Andrade et al. observerade också att deras nätverk uppfyller den lilla världseffekten , att alla hörn är inom ett litet avstånd från varandra. Baserat på numeriska bevis uppskattade de att det genomsnittliga avståndet mellan slumpmässigt utvalda hörnpar i ett n -vertexnätverk av denna typ var proportionellt mot (log n ) 3/4 , men senare forskare visade att det genomsnittliga avståndet faktiskt är proportionellt mot log n .

Vinkelfördelning

Butler & Graham (2010) observerade att om varje ny vertex placeras i mitten av sin triangel, så att kanterna till den nya vertexen halverar triangelns vinklar , då uppsättningen av triangelvinklar av trianglar i underavdelningen, när omtolkad som trippel av barycentriska koordinater av pekar i en liksidig triangel , konvergerar i form till Sierpinski-triangeln när antalet nivåer av indelning växer.

Hamiltonicitet

Takeo (1960) hävdade felaktigt att alla Apollonska nätverk har Hamiltonska cykler ; Goldner –Harary-grafen ger dock ett motexempel. Om ett apolloniskt nätverk har en seghet som är större än en (vilket innebär att om man tar bort valfri uppsättning hörn från grafen lämnas ett mindre antal anslutna komponenter än antalet borttagna hörn) så har det nödvändigtvis en Hamiltonsk cykel, men det finns icke-hamiltonska apollonska nätverk vars seghet är lika med en.

Uppräkning

Det kombinatoriska uppräkningsproblemet med att räkna apollonska trianguleringar studerades av Takeo (1960) , som visade att de har den enkla genererande funktionen f ( x ) som beskrivs av ekvationen f ( x ) = 1 + x ( f ( x )) 3 . I denna genererande funktion räknar termen grad n antalet apolloniska nätverk med en fast yttre triangel och n + 3 hörn. Således är antalet apolloniska nätverk (med en fast yttre triangel) på 3, 4, 5, ... hörn:

1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, ... (sekvens A001764 i OEIS ),

en sekvens som även räknar ternära träd och dissektioner av konvexa polygoner till udda polygoner. Till exempel finns det 12 6-vertex apolloniska nätverk: tre bildas genom att dela upp den yttre triangeln en gång och sedan dela upp två av de resulterande trianglarna, och nio som bildas genom att dela upp den yttre triangeln en gång, dela upp en av dess trianglar och sedan dela upp en av de resulterande mindre trianglarna.

Historia

Birkhoff (1930) är en tidig uppsats som använder en dubbel form av apolloniska nätverk, de plana kartorna som bildas genom att upprepade gånger placera nya regioner i hörnen på enklare kartor, som en klass av exempel på plana kartor med få färger.

Geometriska strukturer som är nära besläktade med apolloniska nätverk har studerats inom polyedrisk kombinatorik åtminstone sedan början av 1960-talet, då de användes av Grünbaum (1963) för att beskriva grafer som kan realiseras som grafen för en polytop på endast ett sätt, utan dimensionella eller kombinatoriska tvetydigheter, och av Moon & Moser (1963) för att hitta enkla polytoper utan långa vägar. Inom grafteorin går det nära sambandet mellan planhet och trädbredd tillbaka till Robertson & Seymour (1984), som visade att varje mindre sluten familj av grafer antingen har en begränsad trädbredd eller innehåller alla plana grafer. Plana 3-träd, som en klass av grafer, övervägdes uttryckligen av Hakimi & Schmeichel (1979) , Alon & Caro (1984) , Patil (1986) och många författare sedan dem.

Namnet "Apolloniskt nätverk" gavs av Andrade et al. (2005) till de nätverk de studerade där nivån på trianglarnas indelning är enhetlig över nätverket; dessa nätverk motsvarar geometriskt en typ av staplade polyeder som kallas en Kleetope . Andra författare tillämpade samma namn mer brett på plana 3-träd i sitt arbete med att generalisera modellen av Andrade et al. till slumpmässiga apollonska nätverk. Trianguleringarna som genereras på detta sätt har också fått namnet "staplade trianguleringar" eller "stack-trianguleringar".

Se även

Anteckningar

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Apollonian_network&oldid=1128419673 "