Teorema structurii grafurilor este un rezultat fundamental în teoria grafurilor . Rezultatul stabilește o legătură profundă între teoria grafurilor minore și înglobările topologice . Teorema a fost formulată în șaptesprezece articole dintr-o serie de 23 de articole de Neil Robertson și Paul Seymour . Demonstrarea teoremei este foarte lungă și confuză. Kawarabayashi și Mohar [1] și Lowash [2] au revizuit teorema într-o formă accesibilă nespecialiștilor, descriind teorema și corolarele sale.
Un minor al unui graf G este orice graf H izomorf la un graf care poate fi obținut dintr-un subgraf al lui G prin contractarea unor muchii. Dacă G nu are un grafic H ca minor, atunci spunem că G este H - liber . Fie H un grafic fix. În mod intuitiv, dacă G este un grafic mare fără H , atunci trebuie să existe un „motiv bun” pentru a face acest lucru. Teorema structurii graficului oferă un astfel de „motiv bun” sub forma unei descrieri aproximative a structurii graficului G. În esență, orice graf fără H G are unul sau două defecte structurale - fie G este „prea subțire” pentru a conține H ca minor, fie G poate fi (aproape) încorporat topologic într-o suprafață care este prea ușor de încorporat H minor. . Prima cauză apare atunci când H este planar și ambele cauze apar atunci când H este neplanar . Mai întâi, să clarificăm aceste concepte.
Lățimea arborelui G este un număr întreg pozitiv care definește „subțirea ” lui G. De exemplu, un graf conectat G are lățimea arborelui unu dacă și numai dacă este un arbore, iar G are lățimea arborelui doi dacă și numai dacă este un grafic paralel-serial . Este intuitiv clar că un graf mare G are o lățime mică de arbore dacă și numai dacă G presupune structura unui arbore mare în care nodurile și marginile sunt înlocuite cu grafice mici. Vom oferi o definiție precisă a lățimii arborelui în subsecțiunea referitoare la sumele clicurilor. Există o teoremă conform căreia dacă H este minorul unui grafic G , atunci lățimea arborelui H nu depășește lățimea arborelui G. Astfel, un „motiv bun” pentru ca G să fie fără H este că lățimea arborelui G nu este foarte mare . Teorema structurii grafului are corolarul că acest motiv se aplică întotdeauna atunci când H este plan .
Corolarul 1. Pentru orice graf planar H , există un număr întreg pozitiv k astfel încât orice graf fără H are lățimea arborelui mai mică decât k .
Valoarea lui k din Corolarul 1 este de obicei mult mai mare decât lățimea arborelui H (există o excepție notabilă când H = K 4 , adică H este egal cu un grafic complet cu patru vârfuri pentru care k = 3). Acesta este unul dintre motivele pentru care se spune că teorema structurii descrie „structura brută” a graficelor libere H.
În linii mari, o suprafață este un set de puncte cu o structură topologică locală sub forma unui disc. Suprafețele se împart în două familii infinite - suprafețele orientabile includ sferă , torus , torus dublu , etc. Suprafețele neorientabile includ planul proiectiv real , sticla Klein și așa mai departe. Un grafic este încorporat într-o suprafață dacă poate fi desenat pe suprafață ca un set de puncte (vârfuri) și arce (margini), astfel încât acestea să nu se intersecteze sau să se atingă, cu excepția cazului în care vârfurile și marginile sunt incidente sau adiacente. Un grafic este planar dacă este încorporabil într-o sferă. Dacă un grafic G este încorporat într-o anumită suprafață, atunci orice minor al graficului G este, de asemenea, încorporat în aceeași suprafață. Astfel, un „motiv bun” pentru ca un grafic G să fie liber de H este posibilitatea de a încorpora G într-o suprafață în care H nu poate fi încorporat.
Dacă H nu este planar, teorema grafului de structură poate fi privită ca o generalizare puternică a teoremei Pontryagin-Kuratovsky . Versiunea acestei teoreme demonstrată de Wagner [3] afirmă că dacă un graf G este atât K 5 -liber, cât și K 3,3 -liber, atunci G este planar. Această teoremă oferă un „motiv bun” pentru ca G să nu aibă K 5 sau K 3,3 ca minore. Mai precis, G este încorporat într-o sferă, în timp ce nici K5 , nici K3,3 nu pot fi încorporate într-o sferă. Conceptul de „motiv bun” nu este suficient pentru teorema grafului structural. Sunt necesare încă două concepte - sume pe clic și vârtejuri .
O clică într-un grafic G este orice set de vârfuri care sunt perechi adiacente unul altuia în G . Pentru un număr întreg nenegativ k , suma k -clică a două grafice G și K este orice grafic obținut prin alegerea în grafice G și K clicuri de dimensiune m ≤ k pentru unele m nenegative , identificând aceste două clicuri într-o clică (de dimensiunea m ) și ștergerea unui număr (posibil zero) de margini în această nouă clică.
Dacă G 1 , G 2 , ..., G n este o listă de grafice, puteți obține un nou grafic combinând grafice din listă folosind sume k-clic . Adică, creăm o sumă k - clic a graficului G 1 și G 2 , apoi creăm o sumă k - clic a graficului G 3 cu graficul rezultat anterior și așa mai departe. Un grafic are lățimea arborelui de cel mult k dacă poate fi obținut ca sumă k -clic a unei liste de grafice în care fiecare grafic are cel mult k + 1 vârfuri.
Corolarul 1 ne arată că sumele k -clică ale graficelor mici descriu structura brută a graficelor H- free în cazul planarității H . Dacă H este neplanar, suntem forțați să luăm în considerare și sumele k -clică de grafice, fiecare dintre ele încorporate într-o suprafață. Următorul exemplu cu H = K 5 ilustrează acest punct. Graficul K 5 poate fi încorporat în orice suprafață, cu excepția unei sfere. Cu toate acestea, există grafice libere de K 5 care sunt departe de a fi plane. În special, suma de 3 clicuri a oricărei liste de grafuri plane dă un graf liber K5 . Wagner [3] a definit structura exactă a graficelor libere K 5 ca parte a unui grup de rezultate cunoscut sub numele de teorema lui Wagner :
Teorema 2. Dacă G este liber de K 5 , atunci G poate fi obținut ca sume de 3 clicuri ale unei liste de grafuri plane și copii ale unor grafuri neplanare specifice cu 8 vârfuri.
Rețineți că teorema 2 este o teoremă de structură exactă deoarece definește exact structura graficelor libere K 5 . Astfel de rezultate sunt rare în teoria grafurilor. Teorema grafului structural nu este precisă în sensul că pentru majoritatea grafurilor H , descrierea structurală a grafurilor H- free include unele grafuri care nu sunt H- free.
Există o tentație de a presupune că un analog al teoremei 2 este valabil și pentru graficele H altele decât K 5 . Poate că ar suna așa: pentru orice grafic neplanar H, există un număr pozitiv k astfel încât fiecare grafic fără H poate fi obținut ca sumă k-clică a unei liste de grafice, fiecare dintre ele având cel mult k vârfuri, sau înglobări într-o suprafață în care H nu poate fi încorporat . Această afirmație este prea simplă pentru a fi adevărată. Trebuie să permitem fiecărui graf imbricat G i să „trișeze” în două moduri limitate. În primul rând, trebuie să permitem, într-un număr limitat de locuri de pe suprafață, adăugarea unor noi vârfuri și muchii, cărora li se permite să se intersecteze într-o complexitate limitată . Astfel de locuri sunt numite vârtejuri . „Complexitatea” unui vortex este limitată de un parametru numit adâncimea sa , care este strâns legat de lățimea traseului graficului . Cititorul poate sări peste citirea definiției exacte a adâncimii k eddy în secțiunea următoare. În al doilea rând, trebuie să permitem adăugarea unui număr limitat de noi vârfuri pentru graficele vortex imbricate.
O muchie a unui graf imbricat este o celulă deschisă de 2 suprafețe care nu intersectează graficul, dar ale cărei limite sunt uniunea unor muchii ale grafului imbricat. Fie F o față a unui grafic încorporat G și fie v 0 , v 1 , ..., v n −1 , v n = v 0 vârfurile care se află la limita lui F (în ordinea ciclului). Intervalul ciclic pentru F este o mulțime de vârfuri de forma { v a , v a +1 , ..., v a + s }, unde a și s sunt numere întregi și unde indicele este luat modulo n . Fie Λ o listă finită de intervale de ciclu pentru F . Construim un nou grafic după cum urmează. Pentru fiecare interval de ciclu L din Λ, adăugăm un nou vârf v L conectat la un număr (posibil zero) de vârfuri din L . Pentru fiecare pereche { L , M } de intervale din Λ, putem adăuga o muchie care leagă v L cu v M dacă L și M au o intersecție nevidă. Se spune că graficul rezultat este obținut din G prin adăugarea unui vârtej de adâncime de cel mult k (la o față F ) dacă niciun vârf de pe F nu apare în mai mult de k intervale de la Λ.
Teorema grafului structural . Pentru orice grafic H, există un întreg pozitiv k astfel încât orice grafic fără H poate fi obținut după cum urmează:
Rețineți că pașii 1 și 2 produc grafice goale dacă H este plan, dar numărul limitat de vârfuri adăugat la pasul 3 face aserția compatibilă cu Corolarul 1.
Versiuni mai puternice ale teoremei grafului structural sunt posibile în funcție de mulțimea H de minori interzise. De exemplu, dacă unul dintre graficele din H este planar , atunci orice grafic fără H are o descompunere arborescentă de lățime mărginită. În mod echivalent, poate fi reprezentat ca o sumă peste o clică de grafice de dimensiune constantă [4] . Dacă unul dintre graficele H poate fi desenat în planul cu o intersecție , atunci graficele fără H -minore permit o descompunere în sumă de clicuri a graficelor de dimensiune constantă și a graficelor de gen mărginit (fără a utiliza vârtejuri) [5] [6] ). Sunt cunoscute și diverse întăriri dacă unul dintre graficele H este un grafic de vârf [7] .