Apollonian síť - Apollonian network

Apollonská síť
The Goldner – Hararyův graf, ne-hamiltonovská apollonská síť

v kombinatorická matematika, an Apollonian síť je neorientovaný graf vytvořený procesem rekurzivního rozdělení trojúhelníku na tři menší trojúhelníky. Apollonské sítě lze ekvivalentně definovat jako rovinný 3-stromy maximální rovinné chordální grafy, jedinečně 4barevné rovinné grafy a grafy skládané polytopy. Jsou pojmenovány po Apollonius z Pergy, který studoval související konstrukci balení kruhu.

Definice

Může být vytvořena apollonská síť vycházející z jediného trojúhelníku vložený v Euklidovské letadlo opakovaným výběrem trojúhelníkové plochy vložení, přidáním nového vrcholu dovnitř plochy a připojením nového vrcholu ke každému vrcholu plochy, která jej obsahuje. Tímto způsobem je trojúhelník obsahující nový vrchol rozdělen na tři menší trojúhelníky, které mohou být dále rozděleny stejným způsobem.

Příklady

The kompletní grafy na třech a čtyřech vrcholech, K.3 a K.4, jsou obě apollonské sítě. K.3 je tvořen tím, že začíná trojúhelníkem a neprovádí žádné dělení, zatímco K.4 je tvořen provedením jediného dělení před zastavením.

The Goldner – Hararyův graf je Apollonian síť, která tvoří nejmenší non-Hamiltonian maximální rovinný graf.[1] Další komplikovanější Apollonian síť byla použita Nishizeki (1980) poskytnout příklad a 1 těžké nehamiltonovský maximální rovinný graf.

Graficko-teoretické charakterizace

Kromě toho, že jsou definovány rekurzivním rozdělením trojúhelníků, mají apollonské sítě několik dalších ekvivalentních matematických charakterizací. Jsou to akordický maximální rovinné grafy, chordální polyedrické grafy a rovinné 3-stromy. Jsou to jedinečně 4barevné rovinné grafy a rovinné grafy s jedinečným Schnyderovo dřevo rozklad na tři stromy. Jsou to maximální planární grafy se šířkou stromu tři, třída grafů, kterou lze charakterizovat zakázané nezletilé nebo podle jejich redukovatelnosti pod Y-Δ transformuje. Jsou to maximální rovinné grafy s zvrhlost tři. Jsou to také rovinné grafy na daném počtu vrcholů, které mají největší možný počet trojúhelníků, největší možný počet čtyřboká podgrafů, největší možný počet klik a největší možný počet kusů po rozložení oddělením trojúhelníků.

Chordalita

Apollonské sítě jsou příklady maximální rovinné grafy, grafy, ke kterým nelze přidat žádné další hrany, aniž by došlo ke zničení rovinnosti, nebo ekvivalenty grafů, které lze nakreslit v rovině tak, že každá plocha (včetně vnější plochy) je trojúhelník. Jsou taky chordální grafy, grafy, ve kterých má každý cyklus čtyř nebo více vrcholů diagonální hranu spojující dva po sobě jdoucí vrcholy cyklu, a pořadí, ve kterém jsou vrcholy přidávány v dělícím procesu, který tvoří apollonskou síť, je uspořádání eliminace jako chordální graf. Toto tvoří alternativní charakterizaci apollonských sítí: jsou to přesně chordální maximální rovinné grafy nebo ekvivalentní chordální sítě polyedrické grafy.[2]

V apollonské síti každý maximální klika je kompletní graf na čtyřech vrcholech, vytvořený výběrem libovolného vrcholu a jeho tří dřívějších sousedů. Každý minimální oddělovač klik (klika, která rozděluje graf na dva odpojené podgrafy) je jedním z rozdělených trojúhelníků. Chordální graf, ve kterém mají všechny maximální kliky a všechny minimální oddělovače klik stejnou velikost, je a k-strom a Apollonské sítě jsou příklady tří stromů. Ne každý 3-strom je rovinný, ale rovinné 3-stromy jsou přesně apollonské sítě.

Jedinečná barevnost

Každá Apollonian síť je také jedinečně 4barevný graf. Protože se jedná o rovinný graf, čtyřbarevná věta znamená, že má zbarvení grafu pouze se čtyřmi barvami, ale jakmile jsou vybrány tři barvy počátečního trojúhelníku, existuje pouze jedna možná volba pro barvu každého následujícího vrcholu, takže až do permutace sady barev má přesně jedno 4 zbarvení. Je těžší dokázat, ale také je pravda, že každý jednoznačně 4barevný rovinný graf je síť Apollonianů. Apollónské sítě lze proto také charakterizovat jako jedinečně 4barevné barevné plany.[3] Apollonské sítě také poskytují příklady rovinných grafů, které mají co nejméně k-barvy, jak je to možné pro k > 4.[4]

Apollonské sítě jsou také přesně maximálními planárními grafy, které (jakmile je vnější povrch fixován) mají jedinečný Schnyderovo dřevo, rozdělení okrajů grafu do tří prokládaných stromů zakořeněných na třech vrcholech vnějšího obličeje.[5]

Šířka stromu

Apollónské sítě netvoří rodinu grafů, která je uzavřena při operaci braní nezletilí v grafu, protože odstranění hran, ale ne vrcholů z apollonské sítě, vytvoří graf, který není apollonskou sítí. Rovinný částečné 3-stromy, podgrafy apollonských sítí, jsou méně uzavřené. Proto podle Věta Robertson – Seymour, lze je charakterizovat konečným počtem zakázané nezletilé. Minimální zakázané nezletilé pro rovinné dílčí 3-stromy jsou čtyři minimální grafy mezi zakázanými nezletilými pro rovinné grafy a dílčí 3-stromy: kompletní graf K.5, kompletní bipartitní graf K.3,3, graf osmistěn a graf pětiúhelníkový hranol. Apollónské grafy jsou maximální grafy, které nemají žádný z těchto čtyř grafů jako vedlejší.[6]

A Transformace Y-Δ, operace, která nahradí vrchol stupně tři v grafu trojúhelníkem spojujícím jeho sousedy, je dostatečná (společně s odstraněním paralelních hran) k redukci jakékoli Apollonianské sítě na jediný trojúhelník a obecněji rovinné grafy, které mohou být redukované na jednu hranu transformacemi Y-Δ, odstranění rovnoběžných hran, odstranění vrcholů stupně jedna a komprese vrcholů stupně dva jsou přesně rovinné dílčí 3 stromy. Duální grafy rovinných dílčích 3 stromů tvoří další rodinu méně uzavřených grafů a jsou přesně rovinnými grafy, které lze redukovat na jednu hranu transformacemi Δ-Y, odstraněním rovnoběžných hran, odstraněním vrcholů prvního stupně a komprese vrcholů druhého stupně.[7]

Degenerace

V každém podgrafu apollonské sítě má naposledy přidaný vrchol stupeň nanejvýš tři, což Apollonianské sítě mají zvrhlost tři. Pořadí, ve kterém jsou vrcholy přidány k vytvoření sítě, je tedy pořadí degenerace a apollonské sítě se shodují s 3-degenerovanými maximálními rovinnými grafy.

Extrémnost

Další charakteristika apollonských sítí zahrnuje jejich připojení. Libovolný maximální rovinný graf lze rozložit na maximální rovinné podgrafy spojené se 4 vrcholy jeho rozdělením podél jeho oddělovacích trojúhelníků (trojúhelníků, které nejsou plochami grafu): vzhledem k libovolnému mimofaciálnímu trojúhelníku: lze vytvořit dva menší maximální rovinné grafy, jeden sestávající z části uvnitř trojúhelníku a druhý sestávající z části mimo trojúhelník. Maximální rovinné grafy bez oddělovacích trojúhelníků, které mohou být vytvořeny opakovaným rozdělením tohoto typu, se někdy nazývají bloky, ačkoli tento název byl také použit pro vzájemně propojené komponenty grafu, který sám o sobě není propojen. Apollonská síť je maximální rovinný graf, ve kterém jsou všechny bloky izomorfní do celého grafuK.4.

v teorie extrémních grafů „Apollonské sítě jsou také přesně ty n-vertexové planární grafy, ve kterých počet bloků dosahuje svého maxima, n − 3a rovinné grafy, ve kterých počet trojúhelníků dosahuje svého maxima, 3n − 8. Protože každý K.4 podgraf rovinného grafu musí být blok, jedná se také o rovinné grafy, ve kterých je počet K.4 subgraphs dosahuje svého maxima, n − 3a grafy, ve kterých je počet kliky jakéhokoli typu dosáhne svého maxima, 8n − 16.[8]

Geometrické realizace

Konstrukce z kruhových ucpávek

Příklad Apollonian těsnění
Výstavba apollonské sítě z kruhového obalu

Apollonské sítě jsou pojmenovány po Apollonius z Pergy, který studoval Problém Apollónia konstrukce tečny kružnice ke třem dalším kružnicím. Jednou z metod konstrukce apollonských sítí je začít se třemi vzájemně tečnými kruhy a poté opakovaně vpisovat další kruh do mezery tvořené třemi dříve nakreslenými kruhy. Takto vytvořená fraktální sbírka kruhů se nazývá an Apollonian těsnění.

Pokud je proces výroby apollonského těsnění zastaven dříve, pouze s konečnou sadou kruhů, pak graf, který má jeden vrchol pro každý kruh a jeden okraj pro každou dvojici tečných kruhů, je síť Apollonian.[9] Existence sady tečných kruhů, jejichž tečnosti představují danou apollonskou síť, tvoří jednoduchou instanci Koebe – Andreev – Thurstonova věta o zalomení kruhu, který uvádí, že jakýkoli rovinný graf může být reprezentován tečnými kružnicemi stejným způsobem.[10]

Mnohostěn

The triakis čtyřstěn, polyedrická realizace 8-vrcholné apollonské sítě

Apollonské sítě jsou rovinné 3 spojené grafy a tedy tím, že Steinitzova věta, lze vždy vyjádřit jako konvexní grafy mnohostěn. Konvexní mnohostěn představující apollonskou síť je trojrozměrný skládaný mnohostěn. Takový polytop lze získat ze čtyřstěnu opakovaným lepením dalších čtyřstěnů po jednom na jeho trojúhelníkové plochy. Apollónské sítě lze proto definovat také jako grafy skládaných 3d polytopů.[11] Je možné najít reprezentaci libovolné apollonské sítě jako konvexního 3d mnohostěnu, ve kterém jsou všechny souřadnice celými čísly polynomiální velikosti, lepší než to, co je známé pro jiné rovinné grafy.[12]

Trojúhelníková oka

Rekurzivní dělení trojúhelníků na tři menší trojúhelníky bylo zkoumáno jako segmentace obrazu technika v počítačové vidění podle Elcock, Gargantini & Walsh (1987); v této souvislosti to nazvali ternární rozklad scalenového trojúhelníku. Poznamenali, že umístěním každého nového vrcholu na těžiště jeho obklopujícího trojúhelníku by triangulace mohla být zvolena takovým způsobem, že všechny trojúhelníky mají stejné oblasti, i když ne všechny mají stejný tvar. Obecněji lze Apollonianské sítě kreslit v rovině s jakoukoli předepsanou oblastí v každé ploše; pokud jsou oblasti racionální čísla, tak jsou všechny souřadnice vrcholů.[13]

Je také možné provést proces rozdělení trojúhelníku, aby se vytvořila apollonská síť, a to tak, že v každém kroku budou délky hran racionální čísla; je otevřeným problémem, zda má každý rovinný graf výkres s touto vlastností.[14] Je to možné v polynomiální čas najít výkres rovinného 3-stromu s celočíselnými souřadnicemi minimalizujícími plochu ohraničující rámeček výkresu a otestovat, zda lze daný rovinný 3-strom nakreslit jeho vrcholy na danou sadu bodů.[15]

Vlastnosti a aplikace

Odpovídající grafy

Plummer (1992) použil apollonské sítě ke konstrukci nekonečné rodiny maximálních rovinných grafů se sudým počtem vrcholů, ale bez perfektní shoda. Plummerovy grafy jsou tvořeny ve dvou fázích. V první fázi počínaje trojúhelníkem abc, jeden opakovaně rozdělí trojúhelníkovou plochu dělení, která obsahuje hranu před naším letopočtem: výsledkem je graf skládající se z cesty z A do konečného dělícího vrcholu spolu s hranou z každého vrcholu cesty do každého z b a C. Ve druhé fázi je každá z trojúhelníkových ploch výsledného rovinného grafu rozdělena ještě jednou. Pokud je cesta z A do konečného dělení vrchol prvního stupně má sudou délku, pak je počet vrcholů v celkovém grafu také sudý. Přibližně 2/3 vrcholů jsou však ty vložené do druhého stupně; tyto tvoří nezávislá sada, a nelze je vzájemně porovnat, ani není dostatek vrcholů mimo nezávislou množinu, aby bylo možné najít shody pro všechny z nich.

Ačkoli Apollonian sítě samy o sobě nemusí mít dokonalé shody, planární duální grafy apollonských sítí jsou 3 pravidelné grafy bez č řezané hrany, tedy teorémem Petersen (1891) je zaručeno, že mají alespoň jednu dokonalou shodu. V tomto případě je však známo více: duály apollonských sítí mají vždy exponenciální počet dokonalých shody.[16] László Lovász a Michael D. Plummer domníval se, že podobná exponenciální dolní mez platí obecněji pro každý 3 pravidelný graf bez oříznutých hran, což byl výsledek, který byl později prokázán.

Grafy mocenského zákona

Andrade a kol. (2005) studoval mocenské zákony v stupně zvláštního případu sítí tohoto typu, vytvořeného rozdělením všech trojúhelníků stejným počtem opakování. Tyto sítě využili k modelování obalů vesmíru částicemi různých velikostí. Na základě své práce představili další autoři náhodné apollonské sítě, vytvořené opakovaným výběrem náhodné tváře k rozdělení, a ukázali, že se také řídí rozdělovacím zákonem [17] a mají malé průměrné vzdálenosti.[18] Alan M. Frieze a Charalampos E. Tsourakakis analyzovali nejvyšší stupně a vlastní hodnoty náhodných Apollonianských sítí.[19] Andrade a kol. také poznamenal, že jejich sítě uspokojují efekt malého světa, že všechny vrcholy jsou v malé vzdálenosti od sebe. Na základě numerických důkazů odhadli průměrnou vzdálenost mezi náhodně vybranými páry vrcholů v n-vertexová síť tohoto typu, aby byla úměrná (log n)3/4, ale později vědci prokázali, že průměrná vzdálenost je ve skutečnosti úměrná log n.[20]

Rozložení úhlu

Butler & Graham (2010) zjistil, že pokud je každý nový vrchol umístěn na stimulant jeho trojúhelníku, takže hrany k novému vrcholu rozdělit úhly trojúhelníku, pak množina trojic úhlů trojúhelníků v dělení, když je znovu interpretována jako trojice barycentrické souřadnice bodů v an rovnostranný trojúhelník, konverguje ve tvaru do Sierpinského trojúhelník s rostoucím počtem úrovní dělení.

Hamiltonicita

Takeo (1960) mylně tvrdil, že všechny Apollonian sítě mají Hamiltonovské cykly; nicméně Goldner – Hararyův graf poskytuje protiklad. Pokud má Apollonian síť houževnatost větší než jeden (což znamená, že odstranění libovolné sady vrcholů z grafu ponechá menší počet připojených komponent než počet odstraněných vrcholů), pak to nutně má hamiltonovský cyklus, ale existují nehamiltonovské apollonské sítě, jejichž houževnatost se rovná jedné .[21]

Výčet

The kombinatorický výčet problém počítání apollonských triangulací studoval Takeo (1960), kteří ukázali, že mají jednoduché generující funkce F(X) popsáno rovnicí F(X) = 1 + X(F(X))3.V této generující funkci je termín stupně n spočítá počet Apollonských sítí s pevným vnějším trojúhelníkem a n + 3 Počty apollonských sítí (s pevným vnějším trojúhelníkem) na 3, 4, 5, ... vrcholech jsou tedy:

1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, ... (sekvence A001764 v OEIS ),

posloupnost, která se také počítá ternární stromy a pitvy konvexních polygonů do lichých polygonů. Například existuje 12 6-vrcholných apollonských sítí: tři vytvořené rozdělením vnějšího trojúhelníku jednou a poté rozdělením dvou z výsledných trojúhelníků a devět vytvořené rozdělením vnějšího trojúhelníku jednou, rozdělit jeden z jeho trojúhelníků a poté rozdělit jeden z výsledných menších trojúhelníků.

Dějiny

Birkhoff (1930) je raný článek, který používá duální formu apollonských sítí, planární mapy vytvořené opakovaným umístěním nových oblastí na vrcholy jednodušších map, jako třída příkladů planárních map s několika barvami.

Geometrické struktury úzce související s Apollonian sítí byly studovány v polyedrická kombinatorika přinejmenším od počátku šedesátých let, kdy byly používány Grünbaum (1963) popsat grafy, které lze realizovat jako graf polytopu pouze jedním způsobem, bez rozměrových nebo kombinatorických dvojznačností, a Moon & Moser (1963) najít jednoduché polytopy bez dlouhých cest. v teorie grafů, úzké spojení mezi rovinností a šířkou stromu sahá do Robertson & Seymour (1984), který ukázal, že každá menší uzavřená rodina grafů má buď omezenou šířku stromu, nebo obsahuje všechny rovinné grafy. Rovinné 3-stromy, jako třída grafů, byly výslovně brány v úvahu Hakimi & Schmeichel (1979), Alon & Caro (1984), Patil (1986) a mnoho autorů od nich.

Název „Apollonian network“ dal Andrade a kol. (2005) do sítí, které studovali, ve kterých je úroveň rozdělení trojúhelníků v celé síti stejnoměrná; tyto sítě odpovídají geometricky typu skládaného mnohostěnu zvaného a Kleetope.[22] Jiní autoři aplikovali stejný název v širším smyslu na rovinné 3-stromy ve své práci zobecňující model Andrade et al. do náhodných Apollonian sítí.[18] Takto generované triangulace byly také pojmenovány „skládané triangulace“[23] nebo „stack-triangulace“.[24]

Viz také

Poznámky

  1. ^ Tento graf je pojmenován po práci Goldner & Harary (1975); nicméně v literatuře se objevuje dříve, například v Grünbaum (1967), str. 357.
  2. ^ Ekvivalence rovinných 3-stromů a chordálních maximálních rovinných grafů byla uvedena bez důkazu Patil (1986). Důkaz viz Markenzon, Justel & Paciornik (2006). Obecnější charakterizaci chordálních planárních grafů a efektivní algoritmus rozpoznávání těchto grafů najdete v části Kumar a Madhavan (1989). Pozorování, že každý chordální polyedrický graf je maximální rovinný, bylo výslovně uvedeno Gerlach (2004).
  3. ^ Fowler (1998).
  4. ^ Skutečnost, že Apollonianské sítě minimalizují počet zabarvení více než čtyřmi barvami, byla ukázána v duální formě pro barvení map Birkhoff (1930).
  5. ^ Felsner & Zickfeld (2008); Bernardi & Bonichon (2009).
  6. ^ Dva zakázané nezletilé pro planární grafy jsou dány Wagnerova věta. Pro zakázané nezletilé pro dílčí 3-stromy (které zahrnují i ​​neplanární Wagnerův graf ) viz Arnborg, Proskurowski a Corniel (1986) a Bodlaender (1998). Pro přímé důkazy, že oktaedrický graf a pětiúhelníkový hranolový graf jsou jedinými dvěma planárními zakázanými nezletilými, viz Dai & Sato (1990) a El-Mallah & Colbourn (1990).
  7. ^ Politof (1983) představil Δ-Y redukovatelné rovinné grafy a charakterizoval je z hlediska zakázaných homeomorfních podgrafů. Dualita mezi redukovatelnými grafy Δ-Y a Y-Δ, zakázané vedlejší charakterizace obou tříd a připojení k rovinným dílčím 3 stromům pocházejí z El-Mallah & Colbourn (1990).
  8. ^ Charakterizaci z hlediska maximálního počtu trojúhelníků v rovinném grafu viz Hakimi & Schmeichel (1979). Alon & Caro (1984) uveďte tento výsledek a uveďte charakteristiku z hlediska tříd izomorfismu bloků a počtu bloků. Vazba na celkový počet klik snadno vyplývá z hranic trojúhelníků a K.4 podgrafy a je také výslovně uvedeno v Dřevo (2007), který jako příklad uvádí síť Apollonian, která ukazuje, že tato vazba je těsná. Zevšeobecnění těchto hranic na neplanární povrchy viz Dujmović a kol. (2009).
  9. ^ Andrade a kol. (2005).
  10. ^ Thurston (1978–1981).
  11. ^ Viz např. Níže, De Loera a Richter-Gebert (2000).
  12. ^ Demaine & Schulz (2011).
  13. ^ Biedl & Ruiz Velázquez (2010).
  14. ^ Chcete-li rozdělit trojúhelník s racionálními délkami stran, takže menší trojúhelníky mají také racionální délky stran, viz Almering (1963). Pokrok v obecném problému hledání rovinných výkresů s racionální délkou hran viz Geelen, Guo a McKinnon (2008).
  15. ^ Výkresy s celočíselnými souřadnicemi viz Mondal a kol. (2010), a výkresy na dané sadě vrcholů viz Nishat, Mondal & Rahman (2011).
  16. ^ Jiménez & Kiwi (2010).
  17. ^ Tsourakakis (2011)
  18. ^ A b Zhou a kol. (2004); Zhou, Yan & Wang (2005).
  19. ^ Frieze & Tsourakakis (2011)
  20. ^ Albenque & Marckert (2008);Zhang a kol. (2008).
  21. ^ Vidět Nishizeki (1980) pro 1-tvrdý ne-hamiltonovský příklad, Böhme, Harant & Tkáč (1999) za důkaz, že Apollonianské sítě s větší houževnatostí jsou Hamiltonian a Gerlach (2004) pro rozšíření tohoto výsledku na širší třídu rovinných grafů.
  22. ^ Grünbaum (1963); Grünbaum (1967).
  23. ^ Alon & Caro (1984); Zickfeld & Ziegler (2006); Badent a kol. (2007); Felsner & Zickfeld (2008).
  24. ^ Albenque & Marckert (2008); Bernardi & Bonichon (2009); Jiménez & Kiwi (2010).

Reference

externí odkazy