Graficul Apollonius [1] este un grafic nedirecționat format prin procesul recursiv de împărțire a unui triunghi în trei triunghiuri mai mici. Graficele Apollonius pot fi definite în mod echivalent ca 3-arbori plani , ca grafuri de acorduri planare maxime , ca grafuri plane cu 4 culori unice sau ca grafuri cu politop în bloc . Graficele sunt numite după Apollonius din Perga , care a studiat construcțiile de împachetare în cerc.
Graficul Apollonius poate fi obținut dintr-un grafic triunghiular încorporat în planul euclidian selectând în mod repetat o față triunghiulară de imbricare, adăugând un nou vârf la acea față triunghiulară și conectând noul vârf la fiecare vârf din interiorul feței. Ca urmare, fața este împărțită în trei triunghiuri mai mici, care, la rândul lor, pot fi împărțite în același mod.
Graficele complete cu trei și patru vârfuri, K 3 și K 4 , sunt grafice Apollonius. K 3 este format din triunghiul inițial fără alte operații de subdiviziune, în timp ce K 4 este format dintr-o singură operație de subdiviziune.
Graficul Goldner-Harari este graficul Apollonius și, de asemenea, cel mai mic graf planar maximal non-Hamiltonian [2] . Un alt graf Apollonius mai complex a fost folosit de Nishizeki [3] ca exemplu de graf planar maximal 1-rigid non-Hamiltonian.
Deoarece graficele Apollonius sunt definite prin subdiviziunea recursivă a triunghiurilor, ele au descrieri matematice diferite. Graficele sunt grafice planare maxime de acorduri, grafice poliedrice de acorduri și trei arbori plani . Graficele sunt grafice plane cu 4 culori unice și grafice plane cu o descompunere unică într-o pădure Schneider formată din trei copaci. Graficele sunt grafice plane maxime cu lățimea arborelui trei, o clasă de grafice care pot fi descrise prin graficele lor interzise sau prin reducerea lor prin transformări Y-Δ . Graficele sunt grafice plane maxime cu degenerarea trei. Graficele sunt, de asemenea, grafice plane cu un număr dat de vârfuri care au cel mai mare număr posibil de triunghiuri, cel mai mare număr posibil de subgrafe tetraedrice, cel mai mare număr posibil de clicuri și cel mai mare număr posibil de părți după descompunerea în triunghiuri individuale.
Graficele Apollonius sunt exemple de grafice plane maxime la care nu se poate adăuga o muchie fără a încălca planaritatea sau, echivalent, grafice care pot fi desenate în plan astfel încât orice față (inclusiv fața exterioară) să fie un triunghi. Graficele sunt, de asemenea , grafice cordale , în care fiecare ciclu de patru sau mai multe vârfuri are o margine diagonală care conectează două vârfuri ale ciclului care nu sunt consecutive în ciclu, iar ordinea în care sunt adăugate vârfurile în timpul construcției graficului Apollonius este ordinea eliminării în graficul cordal. Această proprietate oferă o descriere alternativă a grafurilor Apollonius - ele sunt exact grafuri planare maxime de corduri sau, echivalent, grafuri poliedrice de armonii [4] .
În graficul Apollonia, orice clică maximă este un grafic complet cu patru vârfuri, format prin alegerea oricărui vârf și a trei vecini cei mai apropiați. Orice separator de clică minimă (o clică a cărei îndepărtare împarte graficul în două grafice deconectate) este unul dintre triunghiurile împărțite. Un grafic cordal în care toate clicurile maxime și toți separatorii de clicuri minime au aceeași dimensiune este un arbore k , iar graficele Apollonius sunt exemple de arbori cu trei. Nu toți cei 3 arbori sunt plani, dar cei 3 arbori plani sunt exact grafice Apollonius.
Orice grafic Apollonius are o colorare unică de 4 culori . Deoarece graficul este planar, teorema în patru culori implică faptul că graficul are o colorare în patru culori , dar deoarece culorile triunghiului inițial sunt fixe, există o singură alegere de culoare pentru noul vârf, deci până la o permutare. de culori, colorarea graficului va fi unică. Este mai greu de arătat, dar este și adevărat că orice graf planar cu o singură colorare este un graf Apollonius. Astfel, graful Apollonius poate fi caracterizat ca un graf plan cu o unică 4-colorare [5] . Graficele Apollonius oferă exemple de grafice plane având numărul minim de k -colorări pentru k > 4 [6]
De asemenea, grafurile Apollonius sunt grafuri planare maxime care (dacă fața exterioară este fixă) au o pădure Schneider unică , o împărțire a marginilor grafului în trei arbori înrădăcinați la vârfurile feței exterioare [7] [8] .
Graficele Apollonius nu formează o familie de grafice care este închisă în ceea ce privește operațiunea de luare a minorilor grafului , deoarece la eliminarea muchiilor, dar nu a vârfurilor, obținem un graf care nu este un graf Apollonius. Cu toate acestea, familia de 3 arbori parțiali planari, subgrafe ale grafurilor Apollonius, este o familie minor închisă. Astfel, conform teoremei Robertson-Seymour , ei pot fi caracterizați printr-un număr finit de minori interziși . Minorii minimi interzis pentru 3-arborii parțiali plani sunt cele patru grafice minime pentru grafurile plane și 3-arborele parțiale: graficul complet K 5 , graficul bipartit complet K 3,3 , graficul octaedric și graficul prismă pentagonală . Graficele Apollonius sunt grafice maxime care nu conțin aceste patru grafice ca minore [9]
O transformare Y-Δ care înlocuiește un vârf de gradul trei cu un triunghi care leagă vecinii este suficientă (împreună cu operația de îndepărtare a muchiilor multiple) pentru a reduce graficul Apollonius la un singur triunghi. Graficele plane care pot fi reduse la o singură muchie cu o transformare Y-Δ, ștergerea mai multor muchii, ștergerea vârfurilor de gradul 1 și înlocuirea unui vârf de gradul 2 cu muchii cu o singură muchie, sunt tocmai 3-arbori parțiali plani. Graficele duale de 3 arbori parțiali plani formează o altă familie de grafice închise prin luarea de minori, care sunt exact acele grafice care pot fi reduse la o singură muchie folosind transformarea Δ-Y, eliminând muchii multiple, eliminând vârfuri de gradul 1 și scăparea de vârfuri de gradul 2 [10] .
În orice subgraf al unui graf Apollonius, ultimul vârf adăugat are gradul trei, deci graficele Apollonius au degenerarea trei. Ordinea în care sunt adăugate vârfurile atunci când se creează un graf este, prin urmare, ordinea degenerării, iar graficele Apollonius sunt aceleași cu grafurile plane maxime cu 3 degenerate.
O altă proprietate care caracterizează graficele lui Apollonius este conexiunea . Orice graf planar maximal poate fi descompus în subgrafe plane maxime conectate cu 4 vârfuri prin împărțirea de-a lungul triunghiurilor (nu fețelor graficului) - dacă există un triunghi care nu este o față, se pot forma două grafuri plane maxime mai mici, unul constând din parte din interiorul triunghiului, cealaltă constă dintr-o parte exterioară triunghiului. Graficele plane maxime fără triunghiuri separatoare, care sunt generate de mai multe partiții de acest fel, sunt uneori numite blocuri, deși același nume este folosit și pentru componentele biconectate ale unui graf care nu este el însuși biconectat. Graficul Apollonius este un grafic planar maximal în care toate blocurile sunt izomorfe la graficul complet K 4 .
În teoria grafurilor extreme, grafurile Apollonius sunt exact grafuri plane cu n vârfuri, în care numărul de blocuri atinge valoarea maximă n − 3 , și grafuri plane, în care numărul de triunghiuri este maxim și egal cu 3 n − 8 . Deoarece fiecare K 4 subgraf al unui graf plan trebuie să fie un bloc, aceste grafice ating numărul maxim de K 4 subgrafe (acest număr este egal cu n - 3 ). Pe aceleași grafice, se realizează numărul maxim de clicuri de orice tip (numărul de clicuri este 8 n − 16 ) [11]
Graficele sunt numite după Apollonius din Perga , care a studiat problema construirii unor cercuri tangente la alte trei cercuri. O metodă de construire a graficelor Apollonius este să începeți cu trei cercuri reciproc tangente și să înscrieți în mod repetat un alt cerc în golul format de cele trei cercuri construite anterior. Un fractal format în acest fel se numește grilă Apollonius .
Dacă procesul de construire a rețelei Apollonius este oprit prin desenarea unui număr finit de cercuri, atunci graficul care are un vârf pentru fiecare cerc și o muchie pentru oricare două cercuri tangente este graficul Apollonius [12] . Existența unei mulțimi de cercuri tangente a căror tangență reprezintă graficul Apollonius este determinată de teorema Koebe-Andreev-Thurston , care afirmă că orice graf plan poate fi reprezentat prin cercuri tangente [13] .
Graficele Apollonius sunt grafice planare cu 3 noduri și, prin urmare, prin teorema lui Steinitz , pot fi întotdeauna reprezentate ca grafice ale politopilor convexe . Politopul convex care reprezintă graficul Apollonius este un politop cu bloc tridimensional . Astfel de poliedre pot fi obținute dintr-un tetraedru prin lipirea în mod repetat de tetraedre suplimentare (pe rând) pe fețele triunghiulare ale poliedrului. Astfel, graficele Apollonius pot fi definite ca grafice ale poliedrelor tridimensionale în bloc [14] . Este posibil să găsim o reprezentare a oricărui graf Apollonius ca un poliedru tridimensional convex în care toate coordonatele sunt numere întregi polinomiale, ceea ce este mai bun decât pentru alte grafice plane [15] .
Împărțirea recursivă a triunghiurilor în trei triunghiuri mai mici a fost explorată de Elcock, Gargantini și Walsh ca tehnică de segmentare a imaginii în viziunea computerizată [16] . În acest context, ei se referă la o astfel de diviziune ca o descompunere triplă a triunghiului inechilateral . Ei au observat că, pe măsură ce fiecare vârf nou este adăugat centrului dintr-un triunghi, triunghiurile de triunghiulare vor avea aceeași zonă, deși nu au aceeași formă. Mai general, graficele Apollonius pot fi desenate în plan, cu orice zonă predeterminată a fiecărei fețe. Dacă ariile sunt date ca numere raționale , la fel vor fi și coordonatele vârfurilor [17] .
Este posibil să se efectueze procesul de împărțire a triunghiurilor atunci când se construiește graficul Apollonius în așa fel încât la fiecare pas lungimile muchiilor să fie numere raționale. Nu se știe dacă poate fi trasat vreun graf planar cu aceleași proprietăți [18] . În timp polinomial, se poate găsi un desen al unui arbore 3 plan cu coordonate întregi cu o zonă minimă a casetei de delimitare și se poate verifica dacă un arbore 3 plan dat poate fi desenat cu vârfuri la un set dat de puncte [19] ]
Plummer [20] a folosit grafurile Apollonius pentru a construi o familie infinită de grafuri plane maxime cu un număr par de vârfuri care nu au o potrivire perfectă . Graficele Plummer sunt construite în două etape. În prima etapă, pornind de la triunghiul abc , se repetă de mai multe ori împărțirea feței triunghiulare care conține muchia bc . Graficul rezultat conține o cale de la a la vârful de diviziune finală, iar fiecare vârf al acestei căi este conectat prin muchii la vârfurile b și c . În a doua etapă, fiecare față (triunghiulară) a graficului plan rezultat este împărțită din nou. Dacă calea de la a la vârful final al partiției primei etape are o lungime pară, numărul total de vârfuri din grafic este de asemenea par. Cu toate acestea, aproximativ 2/3 dintre vârfurile introduse în a doua etapă formează un set independent și nu se pot potrivi între ele, iar vârfurile rămase nu sunt suficiente pentru a forma o potrivire perfectă.
Deși graficele Apollonius în sine nu pot avea potriviri perfecte, graficele duale cu graficele Apollonius sunt grafice cu trei obișnuiți fără muchii tăietoare , așa că, după teorema lui Petersen [21] , ele au în mod necesar cel puțin o potrivire perfectă. Pentru graficele Apollonius, se cunosc și mai multe — graficele duale cu graficele Apollonius au un număr exponențial mare de potriviri perfecte [22] . Laszlo Lovas și Michael D. Plummer au presupus că o limită inferioară exponențială similară ar trebui să existe pentru toate graficele cu 3 regulate fără margini tăietoare, ceea ce a fost confirmat ulterior.
J. Andrade, G. Herrmann, R. Andrade și L. de Silva [12] au studiat legile puterii șirurilor de grade ale unor tipuri speciale de grafice de acest tip formate prin împărțirea tuturor triunghiurilor de același număr de ori. Ei au folosit aceste grafice pentru a modela umplerea spațiului cu părți de diferite dimensiuni. Pe baza lucrărilor lor, alți autori au propus grafice aleatorii Apollonius obținute prin alegerea aleatorie a unei fețe pentru divizare și au arătat că aceste grafice se supun unei legi de putere în distribuția gradelor de vârfuri [23] , și au arătat, de asemenea, că aceste grafice au distanțe mici [ 23] 24] [25] . Freese și Tsourakakis au analizat cele mai mari grade de vârfuri și valori proprii ale graficelor aleatorii Apollonius [26] . J. Andrade, G. Herrmann, R. Andrade și L. de Silva au observat, de asemenea, că graficele lor satisfac efectul „ lume mică ” (teoria a șase strângeri de mână), adică toate vârfurile sunt la o distanță apropiată unul de celălalt. . Pe baza experimentelor numerice, ei au estimat distanța medie dintre perechile de vârfuri selectate aleatoriu într-un grafic n -vertex ca fiind proporțională cu (log n ) 3/4 , dar cercetările ulterioare au arătat că distanța medie a fost de fapt proporțională cu log n [27] [28] .
Butler și Graham [29] au observat că, dacă fiecare vârf nou este plasat la punctul de intersecție al bisectoarelor unui triunghi, atunci mulțimea de triplete de unghiuri ale triunghiurilor dintr-o subdiviziune, dacă este interpretată ca coordonatele baricentrice ale punctelor dintr-un triunghi regulat . , formează un triunghi Sierpinski în limită pe măsură ce nivelul de subdiviziune crește.
Takeo [30] a afirmat în mod eronat că toate graficele Apollonius au cicluri hamiltoniene , dar graficul Goldner-Harari oferă un contraexemplu. Dacă un graf Apollonius are o rigiditate mai mare decât unu (ceea ce înseamnă că eliminarea oricărui număr de vârfuri din grafic lasă mai puține componente conectate decât numărul de vârfuri eliminate), acesta este neapărat hamiltonian, dar există grafuri Apollonius non-Hamiltoniene dacă rigiditatea este unul [31]
Sarcina combinatoriei pentru calcularea triangulațiilor Apollonius a fost studiată de Takeo [30] . El a arătat că pentru numărul de triangulații există o funcție generatoare simplă f ( x ) descrisă de egalitatea f ( x ) = 1 + x ( f ( x )) 3 . În această funcție generatoare, termenul de grad n conține numărul de grafice Apollonius cu un triunghi exterior și n + 3 vârfuri. Numărul de grafice Apollonius (cu triunghi exterior) și vârfuri 3, 4, 5, ...:
1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, ... (secvența A001764 în OEIS ).Aceeași secvență specifică numărul de arbori ternari și numărul de partiții ale unui poligon convex în poligoane cu un număr impar de laturi. De exemplu, există 12 grafice Apollonius cu 6 vârfuri - trei sunt formate prin împărțirea triunghiului exterior, urmată de împărțirea a două dintre triunghiurile rezultate și încă nouă sunt formate prin împărțirea triunghiului exterior și împărțirea unuia dintre triunghiurile rezultate, urmate de despicarea unuia dintre triunghiurile mici.
Birkhoff [32] are o lucrare timpurie care folosește forma duală a graficelor Apollonius, hărți plane formate prin plasarea în mod repetat de noi zone la vârfurile hărților mai simple, ca exemplu de clasă de grafice plane cu puține culori.
Structurile geometrice similare graficelor Apollonius au fost studiate în combinatoria poliedrelor încă de la începutul anilor 1960, când au fost folosite de Grünbaum [33] pentru a descrie grafice care pot fi realizate în poliedre într-un mod unic din punct de vedere al dimensiunii și din punct de vedere. a combinatoriei. Ele au fost, de asemenea, folosite de Moon și Moser [34] pentru a căuta poliedre simple fără căi lungi. În teoria grafurilor, relația strânsă dintre planaritate și lățimea arborelui poate fi urmărită până la o lucrare din 1984 a lui Robertson și Seymour [35] , care au arătat că o familie de grafice care este închisă prin luarea de minori fie are lățime de arbore mărginită, fie conține toate graficele plane. Arborii planari 3 ca o clasă de grafice au fost considerați de către Hakimi și Schmeichel [36] , Alon și Caro [37] , Patil [38] și mulți alți autori după ei.
Denumirea de „graf al Apolloniei” a fost propusă în articolul de J. Andrade, G. Herrmann, R. Andrade și L. de Silva [12] pentru graficele în care nivelul de împărțire a triunghiurilor este omogen. Din punct de vedere geometric, aceste grafice corespund politopilor bloc ( Klee polytopes ) [33] [39] . Alți autori au folosit termenul pentru o clasă mai largă de grafice, 3-arbori plani, pentru a generaliza modelul la grafurile aleatoare ale Apollonius [24] [25] . Triunghiularea astfel obținută a mai fost numită „triunghiulare în bloc” [37] [40] [41] [7] [27] [8] [22] .