Apolloniův graf [1] je neorientovaný graf vytvořený rekurzivním procesem dělení trojúhelníku na tři menší trojúhelníky. Apolloniovy grafy mohou být ekvivalentně definovány jako rovinné 3-stromy , jako maximální rovinné chordální grafy , jako jednoznačně 4-barevné rovinné grafy nebo jako blokové polytopové grafy . Grafy jsou pojmenovány po Apolloniovi z Pergy , který studoval související konstrukce kruhových obalů.
Apolloniův graf lze získat z trojúhelníkového grafu vloženého do euklidovské roviny opakovaným výběrem trojúhelníkové vnořené plochy, přidáním nového vrcholu k této trojúhelníkové ploše a připojením nového vrcholu ke každému vrcholu uvnitř plochy. V důsledku toho je obličej rozdělen na tři menší trojúhelníky, které lze zase rozdělit stejným způsobem.
Kompletní grafy se třemi a čtyřmi vrcholy, K 3 a K 4 , jsou Apolloniovy grafy. K 3 je tvořen počátečním trojúhelníkem bez dalších operací dělení, zatímco K 4 je tvořen jedinou operací dělení.
Goldner-Harariho graf je Apolloniův graf a zároveň nejmenší nehamiltonovský maximální planární graf [2] . Další složitější Apolloniův graf použil Nishizeki [3] jako příklad 1-rigidního nehamiltonovského maximálního planárního grafu.
Protože jsou Apolloniovy grafy definovány rekurzivním dělením trojúhelníků, mají různé matematické popisy. Grafy jsou tětivové maximální rovinné grafy, tětivové polyedrické grafy a rovinné 3-stromy . Grafy jsou jednoznačně 4barevné rovinné grafy a rovinné grafy s unikátním rozkladem na Schneiderův les sestávající ze tří stromů. Grafy jsou maximální rovinné grafy se šířkou stromu tři, třída grafů, které lze popsat jejich zakázanými grafy nebo jejich redukcí pomocí Y-Δ transformací . Grafy jsou maximální rovinné grafy s degenerací tři. Grafy jsou také rovinné grafy s daným počtem vrcholů, které mají největší možný počet trojúhelníků, největší možný počet čtyřstěnných podgrafů, největší možný počet klik a největší možný počet částí po rozložení na jednotlivé trojúhelníky.
Apolloniovy grafy jsou příklady maximálních rovinných grafů, ke kterým nelze přidat hranu bez porušení rovinnosti, nebo ekvivalentně grafy, které lze nakreslit v rovině tak, že jakákoliv plocha (včetně vnější plochy) je trojúhelník. Grafy jsou také akordické grafy , ve kterých má každý cyklus čtyř nebo více vrcholů diagonální hranu spojující dva vrcholy cyklu, které v cyklu nejdou za sebou, a pořadí, ve kterém jsou vrcholy přidávány během konstrukce Apolloniova grafu, je pořadí eliminace v akordickém grafu. Tato vlastnost poskytuje alternativní popis Apolloniových grafů - jsou to přesně tětivové maximální rovinné grafy nebo ekvivalentně tětivové polyedrické grafy [4] .
V grafu Apollonia je jakýkoli maximální klik úplným grafem se čtyřmi vrcholy, vytvořený výběrem libovolného vrcholu a tří nejbližších sousedů. Jakýkoli oddělovač minimální kliky (kliknutí, jehož odstranění rozdělí graf na dva oddělené grafy) je jedním z rozdělených trojúhelníků. Akordický graf, ve kterém jsou všechny maximální kliky a všechny minimální oddělovače klik stejně velké, je k -strom a Apolloniovy grafy jsou příklady 3 -stromů. Ne všechny 3-stromy jsou rovinné, ale rovinné 3-stromy jsou přesně Apolloniovy grafy.
Jakýkoli graf Apollonius má jedinečné 4barevné zbarvení . Protože je graf rovinný, věta o čtyřech barvách znamená, že graf má čtyřbarevné zbarvení , ale protože barvy počátečního trojúhelníku jsou pevné, existuje pouze jedna volba barvy pro nový vrchol, takže až permutace barev, vybarvení grafu bude jedinečné. Je těžší to ukázat, ale také platí, že jakýkoli rovinný graf s jedním zabarvením je Apolloniův graf. Apolloniův graf lze tedy charakterizovat jako rovinný graf s jedinečným 4-zabarvením [5] . Apolloniovy grafy uvádějí příklady rovinných grafů s minimálním počtem k -zabarvení pro k > 4 [6]
Také Apolloniovy grafy jsou přesně maximální rovinné grafy, které (pokud je vnější plocha pevná) mají jedinečný Schneiderův les , rozdělení hran grafu do tří stromů zakořeněných ve vrcholech vnější plochy [7] [8] .
Apolloniovy grafy netvoří rodinu grafů, která by byla uzavřena vzhledem k operaci přebírání vedlejších prvků grafu , protože při odstranění hran, ale ne vrcholů, dostaneme graf, který není Apolloniovým grafem. Rodina rovinných částečných 3-stromů , podgrafů Apolloniových grafů, je však mírně uzavřená rodina. Tak, podle Robertson-Seymour teorém , oni mohou být charakterizováni konečným počtem zakázaných nezletilých . Minimální zakázané vedlejší pro rovinné parciální 3-stromy jsou čtyři minimální grafy pro rovinné grafy a parciální 3-stromy: úplný graf K 5 , úplný bipartitní graf K 3,3 , oktaedronový graf a graf pentagonálního hranolu . Apolloniovy grafy jsou maximální grafy, které neobsahují tyto čtyři grafy jako menší [9]
Transformace Y-Δ , která nahradí vrchol stupně tři trojúhelníkem spojujícím sousedy, je dostatečná (společně s operací odstranění více hran) ke zmenšení Apolloniova grafu na jediný trojúhelník. Rovinné grafy, které lze redukovat na jednu hranu pomocí Y-Δ transformace, smazat více hran, vymazat vrcholy stupně 1 a nahradit vrchol stupně 2 hranami jednou hranou, jsou přesně rovinné částečné 3-stromy. Duální grafy rovinných parciálních 3-stromů tvoří další rodinu grafů uzavřených v rámci nezletilých, což jsou přesně ty grafy, které lze redukovat na jednu hranu pomocí transformace Δ-Y, odstraněním více hran, odstraněním vrcholů stupně 1 a zbavení se vrcholů stupně 2 [10] .
V každém podgrafu Apolloniova grafu má poslední přidaný vrchol stupeň tři, takže Apolloniovy grafy mají degeneraci tři. Pořadí, ve kterém jsou při vytváření grafu přidávány vrcholy, je tedy pořadím degenerace a Apolloniovy grafy jsou stejné jako 3-degenerované maximální rovinné grafy.
Další vlastností, která charakterizuje Apolloniovy grafy, je spojitost . Jakýkoli maximální rovinný graf lze rozložit na 4 vrcholově spojené maximální rovinné podgrafy rozdělením podél trojúhelníků (nikoli ploch grafu) - pokud existuje trojúhelník, který není plochou, lze vytvořit dva menší maximální rovinné grafy, jeden se skládá z část uvnitř trojúhelníku , druhá se skládá z části vně trojúhelníku. Maximální rovinné grafy bez oddělovacích trojúhelníků, které jsou generovány vícenásobnými oddíly tohoto druhu, se někdy nazývají bloky, ačkoli stejný název se také používá pro bispojené komponenty grafu, který sám o sobě není biconnected. Apolloniův graf je maximální rovinný graf, ve kterém jsou všechny bloky izomorfní s úplným grafem K 4 .
V extremální teorii grafů jsou Apolloniovy grafy přesně rovinné grafy s n vrcholy, ve kterých počet bloků dosahuje maximální hodnoty n − 3 , a rovinné grafy, ve kterých je počet trojúhelníků maximální a roven 3 n − 8 . Protože každý K 4 podgraf rovinného grafu musí být blok, dosahují tyto grafy maximálního počtu K 4 podgrafů (toto číslo je rovno n − 3 ). Na stejných grafech je dosaženo maximálního počtu kliků libovolného typu (počet kliků je 8 n − 16 ) [11]
Grafy jsou pojmenovány po Apolloniovi z Pergy , který studoval problém konstrukce kružnic tečných ke třem dalším kružnicím. Jednou z metod konstrukce Apolloniových grafů je začít se třemi vzájemně tečnými kružnicemi a opakovaně vepisovat další kružnici do mezery tvořené třemi dříve vytvořenými kružnicemi. Takto vytvořený fraktál se nazývá Apolloniova mřížka .
Pokud je proces konstrukce Apolloniovy mřížky zastaven kreslením pouze konečného počtu kružnic, pak graf, který má vrchol pro každou kružnici a hranu pro libovolné dvě tečné kružnice, je Apolloniův graf [12] . Existenci množiny tečných kružnic, jejichž tečnost představuje Apolloniův graf, určuje Koebe-Andreev-Thurstonova věta , která říká, že libovolný rovinný graf lze znázornit tečnými kružnicemi [13] .
Apolloniovy grafy jsou rovinné vertexové 3-spojené grafy , a proto, podle Steinitzova teorému , mohou být vždy reprezentovány jako grafy konvexních polytopů . Konvexní polytop představující Apolloniův graf je trojrozměrný blokový polytop . Takové mnohostěny lze získat z čtyřstěnu opakovaným lepením dalších čtyřstěnů (po jednom) na trojúhelníkové plochy mnohostěnu. Apolloniovy grafy lze tedy definovat jako grafy blokových 3-rozměrných mnohostěnů [14] . Je možné nalézt reprezentaci jakéhokoli Apolloniova grafu jako konvexního 3-rozměrného mnohostěnu, ve kterém jsou všechny souřadnice polynomiálními celými čísly, což je lepší než u jiných rovinných grafů [15] .
Rekurzivní dělení trojúhelníků na tři menší trojúhelníky zkoumali Elcock, Gargantini a Walsh jako techniku segmentace obrazu v počítačovém vidění [16] . V této souvislosti označují takové dělení jako trojitý nerovnostranný trojúhelníkový rozklad . Všimli si, že když je každý nový vrchol přidán k těžišti v trojúhelníku, triangulační trojúhelníky budou mít stejnou plochu, i když nemají stejný tvar. Obecněji lze Apolloniovy grafy kreslit v rovině s jakoukoli předem určenou oblastí každé plochy. Pokud jsou oblasti zadány jako racionální čísla , budou i souřadnice vrcholů [17] .
Proces dělení trojúhelníků při konstrukci Apolloniova grafu je možné provést tak, že v každém kroku budou délky hran racionálními čísly. Není známo, zda lze nakreslit jakýkoli rovinný graf se stejnými vlastnostmi [18] . V polynomiálním čase lze najít kresbu rovinného 3-stromu s celočíselnými souřadnicemi s minimální plochou ohraničujícího rámečku a zkontrolovat, zda lze daný rovinný 3-strom nakreslit s vrcholy v dané sadě bodů [19 ]
Plummer [20] použil Apolloniovy grafy ke konstrukci nekonečné rodiny maximálních planárních grafů se sudým počtem vrcholů, které nemají dokonalou shodu . Plummerovy grafy jsou sestaveny ve dvou fázích. V první fázi, počínaje trojúhelníkem abc , se dělení trojúhelníkové plochy obsahující hranu bc mnohokrát opakuje . Výsledný graf obsahuje cestu od a ke konečnému vrcholu dělení a každý vrchol této cesty je připojen hranami k vrcholům b a c . Ve druhé fázi je každá (trojúhelníková) plocha výsledného rovinného grafu opět rozdělena. Má-li cesta od a ke konečnému vrcholu rozdělení prvního stupně sudou délku, je i celkový počet vrcholů v grafu sudý. Přibližně 2/3 vrcholů vložených ve druhém stupni však tvoří nezávislou množinu a nemohou se navzájem shodovat a zbývající vrcholy nestačí k vytvoření dokonalé shody.
Ačkoli Apolloniovy grafy samy o sobě nemohou mít dokonalé shody, grafy duální k Apolloniovým grafům jsou 3-regulární grafy bez řezných hran , takže podle Petersenovy věty [21] nutně mají alespoň jednu perfektní shodu. U Apolloniových grafů je známo ještě více – grafy duální k Apolloniovým grafům mají exponenciálně velký počet dokonalých shod [22] . Laszlo Lovas a Michael D. Plummer předpokládali, že podobná exponenciální dolní mez by měla existovat pro všechny 3-regulární grafy bez řezných hran, což bylo později potvrzeno.
J. Andrade, G. Herrmann, R. Andrade a L. de Silva [12] studovali mocninné zákony posloupností stupňů speciálních typů grafů tohoto typu vzniklých dělením všech trojúhelníků stejným počtem časů. Pomocí těchto grafů modelovali vyplnění prostoru díly různých velikostí. Na základě své práce jiní autoři navrhli náhodné Apolloniovy grafy získané náhodným výběrem plochy pro dělení a ukázali, že tyto grafy se řídí mocninným zákonem v rozložení stupňů vrcholů [23] a také ukázali, že tyto grafy mají malé vzdálenosti [ 24] [25] . Freese a Tsourakakis analyzovali největší stupně vrcholů a vlastní hodnoty náhodných Apolloniových grafů [26] . J. Andrade, G. Herrmann, R. Andrade a L. de Silva si také všimli, že jejich grafy splňují efekt „ malého světa “ (teorie šesti podání rukou), to znamená, že všechny vrcholy jsou od sebe blízko. . Na základě numerických experimentů odhadli průměrnou vzdálenost mezi náhodně vybranými dvojicemi vrcholů v n -vertexovém grafu jako úměrnou (log n ) 3/4 , ale další výzkum ukázal, že průměrná vzdálenost byla ve skutečnosti úměrná log n [27] [28] .
Butler a Graham [29] poznamenali, že pokud je každý nový vrchol umístěn v průsečíku os trojúhelníku, pak množina trojic úhlů trojúhelníků v pododdílu, pokud je interpretována jako barycentrické souřadnice bodů v pravidelném trojúhelníku , tvoří Sierpinského trojúhelník v limitě , jak se úroveň dělení zvyšuje.
Takeo [30] chybně tvrdil, že všechny Apolloniovy grafy mají hamiltonovské cykly , ale graf Goldner-Harari poskytuje protipříklad. Pokud má Apolloniův graf tuhost větší než jedna (což znamená, že odstraněním libovolného počtu vrcholů z grafu zůstane méně připojených komponent, než je počet odstraněných vrcholů), je nutně hamiltonovský, ale existují i nehamiltonovské Apolloniovy grafy, pokud tuhost je jedna [31]
Úlohou kombinatoriky pro výpočet Apolloniových triangulací se zabýval Takeo [30] . Ukázal, že pro počet triangulací existuje jednoduchá generující funkce f ( x ) popsaná rovností f ( x ) = 1 + x ( f ( x )) 3 . V této generující funkci obsahuje člen stupně n počet Apolloniových grafů s vnějším trojúhelníkem a n + 3 vrcholy. Počet Apolloniových grafů (s vnějším trojúhelníkem) a 3, 4, 5, ... vrcholy:
1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, ... (sekvence A001764 v OEIS ).Stejná sekvence určuje počet ternárních stromů a počet rozdělení konvexního mnohoúhelníku na mnohoúhelníky s lichým počtem stran. Například existuje 12 Apolloniových grafů se 6 vrcholy - tři jsou vytvořeny rozdělením vnějšího trojúhelníku, následuje rozdělení dvou výsledných trojúhelníků a devět dalších je vytvořeno rozdělením vnějšího trojúhelníku a rozdělením jednoho z výsledných trojúhelníků, následovaným rozdělením rozdělení jednoho z malých trojúhelníků.
Birkhoff [32] má ranou práci, která používá duální formu Apolloniových grafů, rovinných map vytvořených opakovaným umístěním nových oblastí na vrcholy jednodušších map, jako příklad třídy rovinných grafů s malým počtem barev.
Geometrické struktury podobné Apolloniovým grafům byly studovány v kombinatorice mnohostěnů od počátku 60. let 20. století, kdy je Grünbaum použil [33] k popisu grafů, které lze v mnohostěnech realizovat jedinečným způsobem z hlediska rozměru i pohledu. kombinatoriky. Používali je také Moon a Moser [34] k hledání jednoduchých mnohostěnů bez dlouhých cest. V teorii grafů lze těsný vztah mezi rovinností a šířkou stromu vysledovat zpět k práci Robertsona a Seymoura z roku 1984 [35] , kteří ukázali, že rodina grafů, která je uzavřena s ohledem na nezletilé, má buď omezenou šířku stromu, nebo obsahuje všechny rovinné grafy. Rovinné 3-stromy jako třídu grafů uvažovali Hakimi a Schmeichel [36] , Alon a Caro [37] , Patil [38] a po nich mnoho dalších autorů.
Název „graf Apollonia“ byl navržen v článku J. Andradeho, G. Herrmanna, R. Andradeho a L. de Silvy [12] pro grafy, ve kterých je úroveň dělení trojúhelníků homogenní. Geometricky tyto grafy odpovídají blokovým polytopům ( Klee polytopes ) [33] [39] . Jiní autoři použili termín pro širší třídu grafů, rovinné 3-stromy, aby zobecnili model na náhodné Apolloniovy grafy [24] [25] . Takto získaná triangulizace byla také nazývána "bloková triangulace" [37] [40] [41] [7] [27] [8] [22] .