Az Apollonius-gráf [1] egy irányítatlan gráf , amely egy háromszög három kisebb háromszögre való felosztásának rekurzív folyamatával jön létre. Az Apollonius-gráfok ekvivalens módon definiálhatók sík 3-fákként , maximális síkú akkordgráfokként , egyedileg 4 színezhető síkgráfokként vagy blokkpolitóp gráfokként . A grafikonok nevét Pergai Apolloniusról kapták , aki a kapcsolódó körcsomagolási konstrukciókat tanulmányozta.
Az Apollonius-gráfot az euklideszi síkba ágyazott háromszöggráfból kaphatjuk meg úgy, hogy ismételten kiválasztunk egy háromszög egymásba ágyazott lapját, új csúcsot adunk ehhez a háromszöglaphoz, és az új csúcsot a lapon belüli minden csúcshoz csatlakoztatjuk. Ennek eredményeként az arc három kisebb háromszögre oszlik, amelyek viszont ugyanúgy feloszthatók.
A három és négy csúcsú, K 3 és K 4 teljes gráfok Apollonius-gráfok. A K 3 a kezdő háromszögből jön létre további felosztási műveletek nélkül, míg a K 4 egyetlen felosztási művelettel.
A Goldner-Harari gráf az Apollonius-gráf és egyben a legkisebb nem Hamilton-féle maximális síkgráf [2] . Egy másik összetettebb Apollonius-gráfot Nishizeki [3] használt példaként egy 1-merev nem Hamilton-féle maximális síkgráfra.
Mivel az Apollonius-gráfokat háromszögek rekurzív felosztásával határozzák meg, eltérő matematikai leírásaik vannak. A gráfok húr maximális sík gráfok, akkord poliéder gráfok és sík 3 fák . A grafikonok egyedülállóan 4 színezhető síkgrafikonok és síkgráfok, amelyek egyedi bontása három fából álló Schneider erdővé . A grafikonok maximális síkbeli gráfok három faszélességgel, a gráfok egy osztálya, amely leírható tiltott gráfjaikkal vagy Y-Δ transzformációkkal redukálva . A grafikonok maximális sík gráfok, három degenerációval . A gráfok adott számú csúcsú síkgráfok is, amelyek a lehető legtöbb háromszöggel, a lehető legtöbb tetraéder részgráftal, a lehető legtöbb klikkel és az egyes háromszögekre bontás után a lehető legnagyobb részgráfokkal rendelkeznek.
Az Apollonius-gráfok olyan maximális síkgráfok példái , amelyekhez nem adható él a síkság megsértése nélkül, vagy ezzel egyenértékű gráfok, amelyek úgy rajzolhatók meg a síkban, hogy bármely lap (beleértve a külső oldalt is) háromszög legyen. A gráfok akkordgráfok is , amelyekben minden négy vagy több csúcsból álló ciklusnak van egy átlós éle, amely összeköti a ciklus két olyan csúcsát, amelyek nem egymást követik a ciklusban, és az Apollonius-gráf felépítése során a csúcsok hozzáadásának sorrendje a eliminációs sorrendje az akkordgráfban. Ez a tulajdonság alternatív leírást ad az Apollonius-gráfokról – ezek pontosan akkordális maximális síkgráfok, vagy ezzel egyenértékű húr- poliéder gráfok [4] .
Az Apollónia-gráfban bármely maximális klikk egy teljes gráf négy csúcstal, amely bármely csúcs és három legközelebbi szomszéd kiválasztásával jön létre. Bármely minimális klikkelválasztó (olyan klikk, amelynek eltávolítása a grafikont két szétválasztott gráfra osztja) a felosztott háromszögek egyike. Egy akkordgráf , amelyben az összes maximális klikk és az összes minimális klikkelválasztó azonos méretű, egy k -fa , az Apollonius-gráfok pedig a 3 fák példái . Nem minden 3-fa sík, de a sík 3-fák pontosan Apollonius-gráfok.
Bármely Apollonius-gráf egyedi 4 színnel rendelkezik . Mivel a gráf sík, a négyszín tételből következik, hogy a gráf négyszínű színezésű , de mivel a kezdeti háromszög színei rögzítettek, csak egy szín választható az új csúcshoz, tehát egy permutációig színek, a grafikon színezése egyedi lesz. Nehezebb megmutatni, de az is igaz, hogy minden egyetlen színezésű síkgráf Apollonius-gráf. Így az Apollonius-gráf egy egyedi 4 színezésű síkgráfként jellemezhető [5] . Az Apollonius-gráfok példákat adnak olyan síkgráfokra, amelyekben a minimális számú k színezés k > 4 esetén [6]
Ezenkívül az Apollonius-gráfok pontosan maximális síkgráfok, amelyeknek (ha a külső felület rögzített) egyedi Schneider-erdőjük van , amely a gráf éleinek felosztása három fára, amelyek a külső lap csúcsaiban gyökereznek [7] [8] .
Az Apollonius-gráfok nem alkotnak egy olyan gráfcsaládot, amely a gráf molljainak felvételi művelete szempontjából zárt , mivel az élek, de nem a csúcsok eltávolításakor olyan gráfot kapunk, amely nem Apollonius-gráf. A síkbeli részleges 3-fák családja azonban, az Apollonius-gráfok részgráfjai, egy kis mértékben zárt család. Így a Robertson-Seymour-tétel szerint véges számú tiltott kiskorúval jellemezhetők . A síkbeli részleges 3-fák minimálisan tiltott melléke a négy minimális gráf sík gráfokhoz és részleges 3 fákhoz: a teljes gráf K 5 , a teljes kétrészes gráf K 3,3 , az oktaéder gráf és az ötszögű prizmagráf . Az Apollonius-gráfok olyan maximális gráfok, amelyek nem tartalmazzák ezt a négy gráfot mellékként [9]
Egy Y-Δ transzformáció , amely a harmadik fokú csúcsot egy szomszédokat összekötő háromszögre cseréli, elegendő (a többszörös él eltávolítási művelettel együtt), hogy az Apollonius-gráfot egyetlen háromszöggé redukáljuk. Azok a síkgráfok, amelyek Y-Δ transzformációval egyetlen élre redukálhatók, több él törlésével, 1-es fokú csúcsok törlésével és egy 2-es fokú csúcsot élekkel egyetlen élre cserélve pontosan sík részleges 3-fák. A síkbeli részleges 3-fák duális gráfjai egy másik, a minorok felvétele alá zárt gráfcsaládot alkotnak, amelyek pontosan azok a gráfok, amelyek Δ-Y transzformációval, több él eltávolításával, 1-es fokú csúcsok eltávolításával egyetlen élre redukálhatók, ill. fokú csúcsoktól való megszabadulás [10] .
Egy Apollonius-gráf bármely részgráfjában az utolsó hozzáadott csúcs 3- as fokozatú , tehát az Apollonius-gráfok degenerációja három. A gráf létrehozásakor a csúcsok hozzáadásának sorrendje tehát a degeneráció sorrendje, és az Apollonius-gráfok megegyeznek a 3-degenerált maximális síkgráfokkal.
Egy másik tulajdonság, amely az Apollonius-gráfokra jellemző, az összekapcsoltság . Bármely maximális síkgráfot fel lehet bontani 4 csúcshoz kapcsolódó maximális síkbeli részgráfokra háromszögek (nem gráflapok) mentén történő felosztással - ha van olyan háromszög, amely nem lap, akkor két kisebb maximális síkgráf alakítható ki, amelyek közül az egyik a része a háromszögön belül, a másik a háromszögön kívüli részből áll. Az elválasztó háromszögek nélküli maximális síkgráfokat, amelyeket több ilyen típusú partíció generál, néha blokknak nevezik, bár ugyanezt a nevet használják egy olyan gráf bikapcsolt összetevőire is, amelyek nem kapcsolódnak egymáshoz. Az Apollonius-gráf egy maximális síkgráf, amelyben minden blokk izomorf a teljes K 4 gráfhoz .
Az extremális gráfelméletben az Apollonius-gráfok pontosan n csúcsú síkgráfok , amelyekben a blokkok száma eléri a maximális n − 3 értéket , valamint síkgráfok, amelyekben a háromszögek száma maximális és egyenlő 3 n − 8 . Mivel egy síkgráf minden K 4 részgráfja egy blokk kell, hogy legyen, ezek a gráfok elérik a K 4 részgráfok maximális számát (ez a szám egyenlő n − 3 ). Ugyanezen a grafikonon a tetszőleges típusú klikkek maximális száma elérhető (a klikkek száma 8 n − 16 ) [11]
A gráfok nevét Pergai Apolloniusról kapták , aki a három másik kört érintő körök felépítésének problémáját tanulmányozta. Az Apollonius-gráfok megszerkesztésének egyik módja az, hogy három, egymást kölcsönösen érintő körrel kezdjük, és ismételten beírunk egy másik kört a korábban megépített három kör által alkotott résbe. Az így kialakított fraktálokat Apollonius-rácsnak nevezzük .
Ha az Apollonius-rács felépítésének folyamatát csak véges számú kör megrajzolásával állítjuk le, akkor az a gráf, amelynek minden körnek van csúcsa, és bármely két érintőkörnek éle, az Apollonius-gráf [12] . Az Apollonius-gráfot reprezentáló érintőkörök halmazának létezését a Koebe-Andreev-Thurston-tétel határozza meg , amely kimondja, hogy bármely síkgráf ábrázolható érintőkörökkel [13] .
Az Apollonius-gráfok 3-as síkcsúcsú gráfok , ezért Steinitz tétele szerint mindig konvex politópok gráfjaként ábrázolhatók . Az Apollonius-gráfot reprezentáló konvex politóp egy 3-dimenziós blokkpolitóp . Ilyen poliédereket úgy lehet előállítani egy tetraéderből, hogy ismételten további tetraédereket ragasztanak (egyenként) a poliéder háromszöglapjaira. Így az Apollonius-gráfok blokk 3-dimenziós poliéderek gráfjaként definiálhatók [14] . Bármely Apollonius-gráfot meg lehet találni konvex 3-dimenziós poliéderként, amelyben minden koordináta polinomiális egész szám, ami jobb, mint más síkgráfoknál [15] .
A háromszögek három kisebb háromszögre való rekurzív felosztását Elcock, Gargantini és Walsh a számítógépes látás képszegmentációs technikájaként vizsgálta [16] . Ebben az összefüggésben az ilyen felosztást hármas egyenlő oldalú háromszög dekompozíciónak nevezik . Észrevették, hogy amint minden új csúcsot hozzáadunk a háromszög súlypontjához , a háromszögelési háromszögek területe azonos lesz, bár nem azonos alakúak. Általánosságban elmondható, hogy az Apollonius-gráfok a síkban rajzolhatók, az egyes lapok bármely előre meghatározott területével. Ha a területeket racionális számként adjuk meg , akkor a csúcsok koordinátái is [17] lesznek .
Lehetőség van az Apollonius-gráf megalkotásánál a háromszögek osztásának folyamatára úgy, hogy az élek hossza minden lépésben racionális szám legyen. Nem ismert, hogy meg lehet-e rajzolni azonos tulajdonságú síkgráfot [18] . Polinom időben meg lehet találni egy síkbeli 3-fa rajzát egész koordinátákkal a határolókeret minimális területével, és ellenőrizheti, hogy egy adott sík 3-fa megrajzolható-e csúcsokkal egy adott ponthalmazban [19 ]
Plummer [20] Apollonius gráfokat használt, hogy megalkotta a maximális sík gráfok végtelen családját páros számú csúcsokkal, amelyeknek nincs tökéletes illeszkedése . A Plummer grafikonok két szakaszban készülnek. Az első szakaszban az abc háromszögből kiindulva a bc élt tartalmazó háromszöglap felosztása többször megismétlődik . A kapott gráf tartalmaz egy utat a - tól a végső osztási csúcsig, és ennek az útnak minden csúcsa élekkel kapcsolódik a b és c csúcsokhoz . A második szakaszban az eredményül kapott síkgráf minden (háromszögletű) lapját újra felosztjuk. Ha az a -tól az első szakasz partíciójának végső csúcsáig vezető út páros hosszúságú, akkor a gráf csúcsainak teljes száma is páros. A második szakaszba beszúrt csúcsok körülbelül 2/3-a azonban független halmazt alkot, és nem egyezhet egymással, a fennmaradó csúcsok pedig nem elegendőek a tökéletes illeszkedéshez.
Bár maguk az Apollonius-gráfok nem rendelkeznek tökéletes illeszkedéssel, az Apollonius -gráfokkal duál gráfok 3-reguláris gráfok , amelyek nem rendelkeznek vágóélekkel , így Petersen [21] tétele szerint szükségszerűen van legalább egy tökéletes illeszkedésük. Az Apollonius-gráfok esetében még több ismeretes – az Apollonius-gráfokkal kettős gráfok exponenciálisan sok tökéletes illeszkedéssel rendelkeznek [22] . Lovas László és Michael D. Plummer úgy sejtették, hogy hasonló exponenciális alsó korlátnak kellene léteznie minden 3-reguláris gráfnál vágóélek nélkül, ami később be is igazolódott.
J. Andrade, G. Herrmann, R. Andrade és L. de Silva [12] az összes háromszög ugyanannyiszori elosztásával kialakított, ilyen típusú speciális gráfok foksorozatainak hatványtörvényeit tanulmányozták . Ezekkel a grafikonokkal modellezték a tér különböző méretű részekkel való kitöltését. Munkájuk alapján más szerzők véletlenszerű Apollonius-gráfokat javasoltak, amelyeket úgy kaptak meg, hogy véletlenszerűen választottak egy osztási lapot, és kimutatták, hogy ezek a gráfok a csúcsok fokszámainak eloszlásában hatványtörvénynek engedelmeskednek [23] , és azt is kimutatták, hogy ezeknek a gráfoknak kicsi a távolsága . 24] [25] . Freese és Tsourakakis elemezte a véletlen Apollonius-gráfok csúcsainak és sajátértékeinek legnagyobb fokait [26] . J. Andrade, G. Herrmann, R. Andrade és L. de Silva is észrevette, hogy gráfjaik kielégítik a „ kis világ ” hatást (a hat kézfogás elméletét), vagyis azt, hogy minden csúcs közel van egymástól. . Numerikus kísérletek alapján egy n -csúcs gráfban véletlenszerűen kiválasztott csúcspárok közötti átlagos távolságot (log n ) 3/4 arányosnak becsülték , de további kutatások kimutatták, hogy az átlagos távolság valójában log n -nel arányos [27]. [28] .
Butler és Graham [29] megjegyezte, hogy ha minden új csúcsot egy háromszög felezőjének metszéspontjába helyezünk , akkor a háromszögek szöghármasainak halmaza egy felosztásban, ha egy szabályos háromszög pontjainak baricentrikus koordinátáiként értelmezzük. , Sierpinski-háromszöget alkot a határban , ahogy a felosztás szintje nő.
Takeo [30] tévesen azt állította, hogy minden Apollonius-gráfnak van Hamilton-ciklusa , de a Goldner–Harari gráf egy ellenpéldát ad. Ha egy Apollonius-gráf merevsége nagyobb, mint egy (ami azt jelenti, hogy a gráfból tetszőleges számú csúcs eltávolításával kevesebb összefüggő komponens marad, mint az eltávolított csúcsok száma), akkor szükségszerűen Hamilton-gráf, de vannak nem Hamiltoni Apollonius-gráfok, ha a merevség egy [31]
A kombinatorika feladatát Apollonius-háromszögelések számítására Takeo tanulmányozta [30] . Megmutatta, hogy a háromszögelések számára létezik egy egyszerű f ( x ) generáló függvény , amelyet az f ( x ) = 1 + x ( f ( x )) 3 egyenlőség ír le . Ebben a generáló függvényben az n fokú tag a külső háromszögű és n + 3 csúcsú Apollonius-gráfok számát tartalmazza. Apollonius-gráfok száma (külső háromszöggel) és 3, 4, 5, ... csúcsok száma:
1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, ... ( A001764 sorozat az OEIS -ben ).Ugyanez a szekvencia határozza meg a hármas fák számát és a konvex sokszög partícióinak számát páratlan számú oldalú sokszögekre. Például 12 Apollonius-gráf van 6 csúcsúval – hármat a külső háromszög felosztásával, majd a kapott háromszögek közül kettő felosztásával, további kilenc pedig a külső háromszög felosztásával és a kapott háromszögek egyikének felosztásával jön létre. felhasítva az egyik kis háromszöget.
Birkhoffnak [32] van egy korai tanulmánya, amely az Apollonius-gráfok kettős formáját használja, olyan síkbeli térképeket, amelyeket úgy alakítottak ki, hogy az egyszerűbb térképek csúcsaira ismételten új területeket helyeznek el, mint például a kevés színt tartalmazó síkgráfok osztályát.
Az Apollonius-gráfokhoz hasonló geometriai szerkezeteket a poliéderek kombinatorikájában az 1960-as évek eleje óta tanulmányozták, amikor is Grünbaum [33] használta azokat a gráfok leírására, amelyek dimenziója és nézőpontja szempontjából egyedi módon megvalósítható poliéderekben. a kombinatorika. Moon és Moser [34] is használta egyszerű poliéderek keresésére, hosszú utak nélkül. A gráfelméletben a síkság és a faszélesség közötti szoros kapcsolat Robertson és Seymour [35] 1984-es cikkére vezethető vissza , amely kimutatta, hogy a kiskorúak felvételére zárt gráfcsalád vagy korlátos faszélességű, vagy tartalmazza az összes síkgráfot. Hakimi és Schmeichel [36] , Alon és Caro [37] , Patil [38] és sok más szerző a gráfok osztályának tekintette a sík 3-fákat.
Az "Apollonia gráf" nevet J. Andrade, G. Herrmann, R. Andrade és L. de Silva [12] cikkében javasolták olyan gráfokhoz, amelyekben a háromszögek felosztási szintje homogén. Geometriailag ezek a gráfok blokkpolitópoknak ( Klee polytopes ) felelnek meg [33] [39] . Más szerzők a gráfok szélesebb osztályára, a sík 3 fákra használták a kifejezést, hogy a modellt véletlenszerű Apollonius-gráfokra általánosítsák [24] [25] . Az így kapott háromszögelést "blokkháromszögelésnek" is nevezték [37] [40] [41] [7] [27] [8] [22] .