Apolloniuksen graafi [1] on suuntaamaton graafi , joka muodostuu rekursiivisella prosessilla jakamalla kolmio kolmeen pienempään kolmioon. Apollonius-graafit voidaan määritellä vastaavasti tasomaisiksi 3-puiksi , maksimitasomaisiksi sointukaavioiksi , yksilöllisesti 4-värisiksi tasokaavioiksi tai lohkopolytooppigraafiksi . Kaaviot on nimetty Apolloniuksen Pergasta , joka tutki toisiinsa liittyviä ympyräpakkausrakenteita.
Apollonius-graafi voidaan saada euklidiseen tasoon upotetusta kolmiograafista valitsemalla toistuvasti kolmion sisäkkäinen pinta, lisäämällä siihen uusi kärki ja yhdistämällä uusi kärki jokaiseen pinnan sisällä olevaan kärkeen. Tuloksena kasvot jaetaan kolmeen pienempään kolmioon, jotka puolestaan voidaan jakaa samalla tavalla.
Täydelliset graafit , joissa on kolme ja neljä kärkeä, K 3 ja K 4 , ovat Apollonius-graafia. K 3 muodostetaan alkukolmiolla ilman lisäjakooperaatioita, kun taas K 4 muodostetaan yhdellä osajakooperaatiolla.
Goldner-Harari-graafi on Apolloniuksen graafi ja myös pienin ei-Hamiltonin maksimaalinen tasograafi [2] . Toista monimutkaisempaa Apollonius-graafia käytti Nishizeki [3] esimerkkinä 1-jäykästä ei-Hamiltonin maksimaalisesta tasograafista.
Koska Apollonius-graafit määritellään kolmioiden rekursiivisella alajaolla, niillä on erilaiset matemaattiset kuvaukset. Kaaviot ovat sointujen maksimitasokaavioita, sointujen monitahoisia kuvaajia ja tasomaisia 3-puita . Kaaviot ovat ainutlaatuisesti 4-värisiä tasokaavioita ja tasokaavioita, jotka on jaettu ainutlaatuisella tavalla Schneider-metsään , joka koostuu kolmesta puusta. Graafit ovat maksimaalisia tasokaavioita, joiden puunleveys on kolme, luokka kaavioita, jotka voidaan kuvata niiden kiellettyjen graafien avulla tai niiden vähentämisellä Y-Δ-muunnoksilla . Kaaviot ovat maksimaalisia tasokaavioita, joiden degeneraatio on kolme. Graafit ovat myös tasograafisia, joissa on määrätty määrä pisteitä, joissa on suurin mahdollinen määrä kolmioita, suurin mahdollinen määrä tetraedrisä alagraafia, suurin mahdollinen määrä klikkejä ja suurin mahdollinen määrä osia yksittäisiksi kolmioksi hajoamisen jälkeen.
Apollonius-graafit ovat esimerkkejä maksimaalisista tasograafista , joihin ei voida lisätä reunaa tasoittamatta, tai vastaavasti graafit, jotka voidaan piirtää tasoon siten, että mikä tahansa pinta (mukaan lukien ulkopinta) on kolmio. Graafit ovat myös sointugraafia , joissa jokaisessa neljän tai useamman kärjen syklissä on diagonaalinen reuna, joka yhdistää kaksi syklin kärkeä, jotka eivät ole peräkkäisiä syklissä, ja järjestys, jossa kärjet lisätään Apollonius-graafin rakentamisen aikana, on eliminointijärjestys sointukaaviossa. Tämä ominaisuus antaa vaihtoehtoisen kuvauksen Apollonius-graafista - ne ovat täsmälleen sointu maksimitasograafia tai vastaavasti sointu monitahoisia graafisia [4] .
Apollonia-graafissa mikä tahansa maksimiklikki on täydellinen graafi, jossa on neljä kärkeä ja joka muodostuu minkä tahansa kärjen ja kolmen lähimmän naapurin valinnasta. Mikä tahansa minimaalinen klikkierotin (klikki, jonka poistaminen jakaa kaavion kahdeksi irralliseksi kaavioksi) on yksi jaetuista kolmioista. Sointugraafi, jossa kaikki maksimiklikit ja kaikki pienimmät klikkien erottimet ovat samankokoisia, on k - puu , ja Apollonius-graafit ovat esimerkkejä 3 -puista. Kaikki 3-puut eivät ole tasomaisia, mutta tasomaiset 3-puut ovat täsmälleen Apollonius-graafia.
Kaikissa Apollonius-kaavioissa on ainutlaatuinen 4-värinen väritys . Koska kuvaaja on tasomainen, nelivärilause tarkoittaa, että kuvaajan väritys on nelivärinen , mutta koska alkuperäisen kolmion värit ovat kiinteät, uudelle kärkipisteelle on vain yksi värivaihtoehto, eli permutaatioon asti. värejä, kaavion väritys on ainutlaatuinen. Sitä on vaikeampi näyttää, mutta on myös totta, että mikä tahansa tasograafi, jolla on yksi väritys, on Apollonius-graafi. Apollonius-graafia voidaan siis luonnehtia tasograafiksi, jolla on ainutlaatuinen 4-väri [5] . Apollonius-graafit antavat esimerkkejä tasokaavioista, joissa on minimimäärä k -värjäyksiä arvolle k > 4 [6]
Lisäksi Apollonius-graafit ovat täsmälleen maksimaalisia tasografioita, joissa (jos ulkopinta on kiinteä) on ainutlaatuinen Schneiderin metsä , graafin reunojen osio kolmeen puuhun, jotka ovat juurtuneet ulkopinnan kärkipisteisiin [7] [8] .
Apollonius-graafit eivät muodosta graafiperhettä, joka on suljettu graafin molaarien ottamisen operaation suhteen , koska poistamalla reunoja, mutta ei huippuja, saadaan graafi, joka ei ole Apollonius-graafi. Kuitenkin tasomaisten osittaisten 3-puiden perhe , Apolloniuksen graafien aligraafit, on vähän suljettu perhe. Siten Robertson-Seymourin lauseen mukaan heitä voidaan luonnehtia rajallisella määrällä kiellettyjä alaikäisiä . Vähimmäiskielletyt alavärit tasomaisille osittaisille 3-puille ovat tasograafien ja osittaisten 3-puiden neljä minimigraafia: täydellinen graafi K 5 , täydellinen kaksiosainen graafi K 3,3 , oktaedrigraafi ja viisikulmainen prismagraafi . Apollonius-graafit ovat maksimikaavioita, jotka eivät sisällä näitä neljää graafia sivuaineina [9]
Y-Δ-muunnos , joka korvaa kolmannen asteen kärjen naapureita yhdistävällä kolmiolla, riittää (yhdessä usean reunan poistooperaation kanssa) pelkistämään Apollonius-graafin yhdeksi kolmioksi. Tasograafit, jotka voidaan pelkistää yhdeksi reunaksi Y-Δ-muunnolla, poistamalla useita reunoja, poistamalla asteen 1 kärkipisteitä ja korvaamalla asteen 2 kärkipisteen reunoilla yhdellä reunalla, ovat täsmälleen tasomaisia osittaisia 3-puita. Tasomaisten osittaisten 3-puiden kaksoisgraafit muodostavat toisen graafiperheen, joka on suljettu alaikäisten ottamiseen, jotka ovat juuri niitä graafia, jotka voidaan pelkistää yhdeksi reunaksi käyttämällä Δ-Y-muunnosta, poistamalla useita reunoja, poistamalla 1-asteen kärjet ja päästä eroon asteen 2 huipuista [10] .
Missä tahansa Apollonius-graafin aligraafissa viimeisellä lisätyllä kärjellä on aste kolme, joten Apollonius-graafilla on degeneraatio kolme. Järjestys, jossa pisteet lisätään graafia luotaessa, on siis degeneraatiojärjestys, ja Apollonius-graafit ovat samat kuin 3-degeneroituneet maksimaaliset tasograafit.
Toinen Apolloniuksen graafia luonnehtiva ominaisuus on liitettävyys . Mikä tahansa maksimaalinen tasograafi voidaan hajottaa 4 kärkeen kytketyiksi maksimaalisiksi tasograafisiksi jakamalla kolmioita pitkin (ei graafin pintaa) - jos on kolmio, joka ei ole kasvo, voidaan muodostaa kaksi pienempää maksimaalista tasograafia, joista toinen koostuu osa kolmion sisällä, toinen koostuu kolmion ulkopuolisesta osasta. Suurimpia tasokaavioita , joissa ei ole erottelevia kolmioita ja jotka on luotu useilla tämän tyyppisillä osioilla, kutsutaan joskus lohkoiksi, vaikka samaa nimeä käytetään myös graafin, joka ei itse ole kaksoiskytkentäinen, kaksikytketyille komponenteille . Apollonius-graafi on maksimaalinen tasograafi, jossa kaikki lohkot ovat isomorfisia koko graafin K 4 kanssa .
Ekstremaaligrafiikkateoriassa Apollonius-graafit ovat täsmälleen tasomaisia graafisia n -pisteisiä graafisia graafisia osia , joissa lohkojen lukumäärä saavuttaa maksimiarvon n − 3 , ja tasograafit , joissa kolmioiden lukumäärä on maksimi ja 3 n − 8 . Koska tasograafin jokaisen K 4 -aligraafin on oltava lohko, nämä graafit saavuttavat K 4 -aligraafien enimmäismäärän (tämä luku on yhtä suuri kuin n − 3 ). Samoilla kaavioilla saavutetaan minkä tahansa tyyppisten klikkien enimmäismäärä ( klikkien määrä on 8 n − 16 ) [11]
Kaaviot on nimetty Apolloniuksen Pergan mukaan , joka tutki kolmea muuta ympyrää tangenttien ympyröiden muodostamisongelmaa. Eräs tapa Apolloniuksen graafien muodostamiseksi on aloittaa kolmella toisiaan tangentilla olevalla ympyrällä ja toistuvasti merkitä toinen ympyrä kolmen aiemmin rakennetun ympyrän muodostamaan aukkoon. Tällä tavalla muodostettua fraktaalia kutsutaan Apollonius-ruudukoksi .
Jos Apollonius-ruudukon rakennusprosessi pysäytetään piirtämällä vain äärellinen määrä ympyröitä, niin graafi, jolla on kullekin ympyrälle kärki ja kahdelle tangenttiympyrän reuna, on Apolloniuksen graafi [12] . Tangenttiympyröiden joukon olemassaolo, jonka tangentti edustaa Apolloniuksen graafia, määräytyy Koebe-Andreev-Thurston-lauseen avulla, jonka mukaan mikä tahansa tasograafi voidaan esittää tangenttiympyröillä [13] .
Apollonius-graafit ovat tasomaisia kärkipisteitä 3-liitettyjä graafeja , ja siksi ne voidaan Steinitzin lauseen mukaan aina esittää konveksien monitahoisen graafina . Apollonius-graafia edustava konveksi polytooppi on 3-ulotteinen lohkopolytooppi . Tällaisia monitahoja voidaan saada tetraedristä liimaamalla toistuvasti lisää tetraedreita (yksi kerrallaan) monitahoisen kolmion muotoisiin pintoihin. Siten Apollonius-graafit voidaan määritellä lohkon 3-ulotteisten polyhedrien graafiksi [14] . Mikä tahansa Apolloniuksen graafi on mahdollista löytää konveksina 3-ulotteisena monitahoisena, jossa kaikki koordinaatit ovat polynomisia kokonaislukuja, mikä on parempi kuin muiden tasograafien kohdalla [15] .
Kolmioiden rekursiivista jakamista kolmeen pienempään kolmioon tutkivat Elcock, Gargantini ja Walsh kuvan segmentointitekniikana tietokonenäössä [16] . Tässä yhteydessä he viittaavat tällaiseen jakoon kolminkertaisena epätasasivuisen kolmion hajotuksena . He huomasivat, että kun jokainen uusi kärkipiste lisätään kolmion sentroidiin , kolmiokolmioiden pinta-ala on sama, vaikka ne eivät ole saman muotoisia. Yleisemmin Apollonius-kuvaajat voidaan piirtää tasoon, millä tahansa ennalta määrätyllä alueella kunkin pinnan. Jos alueet annetaan rationaalilukuina , niin myös pisteiden koordinaatit [17] .
Kolmioiden jakoprosessi on mahdollista toteuttaa Apollonius-graafia rakennettaessa siten, että jokaisessa vaiheessa reunojen pituudet ovat rationaalilukuja. Ei tiedetä, voidaanko piirtää mitään tasograafia, jolla on samat ominaisuudet [18] . Polynomiajassa voidaan löytää piirustus tasomaisesta 3 - puusta kokonaislukukoordinaateilla, joiden raja -alueen vähimmäispinta-ala on, ja tarkistaa, voidaanko tietty tasomainen 3-puu piirtää pisteillä tietyssä pistejoukossa [19 ]
Plummer [20] käytti Apollonius-graafia rakentaakseen äärettömän perheen maksimaalisia tasograafisia graafisia parillisia pisteitä, joilla ei ole täydellistä yhteensopivuutta . Plummer-kaaviot rakennetaan kahdessa vaiheessa. Ensimmäisessä vaiheessa kolmiosta abc alkaen reunan bc sisältävän kolmiomaisen pinnan jako toistetaan monta kertaa . Tuloksena oleva graafi sisältää polun a :sta lopulliseen jakopisteeseen, ja jokainen tämän polun kärki on yhdistetty reunoilla pisteisiin b ja c . Toisessa vaiheessa tuloksena olevan tasograafin kukin (kolmio) puoli jaetaan uudelleen. Jos polku a :sta ensimmäisen vaiheen osion viimeiseen kärkeen on parillinen, myös graafin kärkien kokonaismäärä on parillinen. Kuitenkin noin 2/3 toisessa vaiheessa lisätyistä kärkeistä muodostaa itsenäisen joukon eivätkä voi sovittaa toisiaan, eivätkä loput kärjet riitä muodostamaan täydellistä yhteensopivuutta.
Vaikka Apollonius-grafeilla itsessään ei voi olla täydellistä yhteensopivuutta, Apolloniuksen graafien kanssa duaaliset graafit ovat 3-säännöllisiä graafeja , joissa ei ole leikkaussärmiä , joten Petersenin lauseen [21] mukaan niillä on välttämättä vähintään yksi täydellinen yhteensopivuus. Apollonius-graafien osalta tiedetään vielä enemmän – Apolloniuksen graafien kanssa kaksoisgrafeissa on eksponentiaalisesti suuri määrä täydellisiä yhteensopivuuksia [22] . Laszlo Lovas ja Michael D. Plummer arvelivat, että samanlainen eksponentiaalinen alaraja pitäisi olla kaikille 3-säännöllisille graafisille ilman leikkausreunoja, mikä myöhemmin vahvistettiin.
J. Andrade, G. Herrmann, R. Andrade ja L. de Silva [12] tutkivat tämän tyyppisten erikoistyyppisten graafien astejonojen teholakeja, jotka on muodostettu jakamalla kaikki kolmiot yhtä monta kertaa . He käyttivät näitä kaavioita mallintaessaan tilan täyttymistä erikokoisilla osilla. Työnsä perusteella muut kirjoittajat ehdottivat satunnaisia Apollonius-graafia, jotka saatiin valitsemalla satunnaisesti jakolasku, ja osoittivat, että nämä graafit noudattavat potenssilakia kärkiasteiden jakautumisessa [23] , ja osoittivat myös, että näillä kuvaajilla on pienet etäisyydet [ 23]. 24] [25] . Freese ja Tsourakakis analysoivat satunnaisten Apollonius-graafien pisteiden ja ominaisarvojen suurimmat asteet [26] . J. Andrade, G. Herrmann, R. Andrade ja L. de Silva huomasivat myös, että heidän graafinsa tyydyttävät " pienen maailman " efektin (kuuden kädenpuristuksen teorian), eli sen, että kaikki kärjet ovat lähellä toisiaan. . Numeeristen kokeiden perusteella he arvioivat keskimääräisen etäisyyden satunnaisesti valittujen kärkiparien välillä n -vertex-graafissa suhteessa (log n ) 3/4 :ään , mutta lisätutkimukset osoittivat, että keskimääräinen etäisyys oli itse asiassa verrannollinen log n :ään [27] . [28] .
Butler ja Graham [29] totesivat, että jos jokainen uusi kärkipiste sijoitetaan kolmion puolittajien leikkauspisteeseen, niin kolmioiden kulmien kolmioiden joukko alajaossa, jos se tulkitaan säännöllisen kolmion pisteiden barysentrisiksi koordinaateiksi . , muodostaa rajaan Sierpinskin kolmion alajaon tason kasvaessa.
Takeo [30] väitti virheellisesti, että kaikissa Apollonius-grafeissa on Hamiltonin jaksoja , mutta Goldner-Harari-graafi tarjoaa vastaesimerkin. Jos Apollonius-graafin jäykkyys on suurempi kuin yksi (mikä tarkoittaa, että kun graafista poistetaan mikä tahansa määrä pisteitä, jää vähemmän yhdistettyjä komponentteja kuin poistettujen pisteiden määrä), se on välttämättä Hamiltonin, mutta on olemassa ei-Hamiltonin Apollonius-grafeja, jos jäykkyys on yksi [31]
Takeo [30] tutki kombinatoriikan tehtävää Apolloniuksen kolmioiden laskennassa . Hän osoitti, että kolmioiden lukumäärälle on olemassa yksinkertainen generoiva funktio f ( x ) , jota kuvaa yhtälö f ( x ) = 1 + x ( f ( x )) 3 . Tässä generoivassa funktiossa n -asteen termi sisältää Apolloniuksen graafien lukumäärän, joissa on ulompi kolmio ja n + 3 kärkeä. Apollonius-graafien lukumäärä (ulkokolmiolla) ja 3, 4, 5, ... kärkipisteet:
1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, ... (sekvenssi A001764 OEIS : ssä ).Sama sekvenssi määrittää kolmipuiden lukumäärän ja kuperan monikulmion osioiden lukumäärän monikulmioiksi, joissa on pariton määrä sivuja. Esimerkiksi on olemassa 12 Apollonius-graafia, joissa on 6 kärkeä - kolme muodostetaan jakamalla ulompi kolmio, jonka jälkeen jaetaan kaksi tuloksena olevaa kolmiota, ja yhdeksän muuta muodostetaan jakamalla ulompi kolmio ja jakamalla yksi tuloksena olevista kolmioista. jakaa yksi pienistä kolmioista.
Birkhoffilla [32] on varhainen paperi, joka käyttää Apolloniuksen graafien kaksoismuotoa, tasomaisia karttoja, jotka on muodostettu sijoittamalla toistuvasti uusia alueita yksinkertaisempien karttojen kärkipisteisiin, esimerkkinä vähän värejä sisältävien tasograafien luokasta.
Apolloniuksen graafien kaltaisia geometrisia rakenteita on tutkittu polyhedrien kombinatoriikassa 1960-luvun alusta lähtien, jolloin Grünbaum [33] käytti niitä kuvaamaan graafia, jotka voidaan toteuttaa polyhedraissa ainutlaatuisella tavalla mitoiltaan ja näkökulmaltaan. kombinatoriikasta. Niitä käyttivät myös Moon ja Moser [34] etsiessään yksinkertaisia polyhedraja ilman pitkiä polkuja. Graafiteoriassa tasomaisuuden ja puunleveyden välinen läheinen suhde voidaan jäljittää Robertsonin ja Seymourin vuonna 1984 julkaisemaan artikkeliin [35] , joka osoitti, että alaikäisten ottamiseen suljetulla graafiperheellä on joko rajoitettu puunleveys tai se sisältää kaikki tasograafit. Tasomaisia 3-puita graafien luokkana pitivät Hakimi ja Schmeichel [36] , Alon ja Caro [37] , Patil [38] ja monet muut kirjoittajat heidän jälkeensä.
Nimeä "Apollonian graafi" ehdottivat J. Andraden, G. Herrmannin, R. Andraden ja L. de Silvan [12] artikkelissa kaavioille, joissa kolmioiden jakotaso on homogeeninen. Geometrisesti nämä kuvaajat vastaavat lohkopolytooppeja ( Klee polytooppeja ) [33] [39] . Muut kirjoittajat ovat käyttäneet termiä laajemmasta graafiluokasta, tasomaisista 3-puista, yleistääkseen mallin satunnaisiin Apolloniuksen graafisiin [24] [25] . Näin saatua triangulisointia on kutsuttu myös "lohkokolmiotukseksi" [37] [40] [41] [7] [27] [8] [22] .