Teorema Robertson-Seymour (numită și teorema minoră a grafului [1] ) afirmă că orice familie de grafuri care este închisă sub operațiunile de îndepărtare și contracție a muchiilor poate fi definită printr-un set finit de grafuri interzise .
De exemplu, setul de grafice plane este închis sub operațiunile de îndepărtare și contractare a muchiilor; graficele interzise în acest caz sunt graficul complet K 5 și graficul complet bipartit K 3,3 . Ultima afirmație se numește teorema Wagner și este strâns legată de teorema Pontryagin-Kuratovsky .
Teorema este larg cunoscută pentru formularea sa elementară în absența unei dovezi simple. Ea poartă numele de Neil Robertson.și Paul Seymour , care a dovedit-o într-o serie de douăzeci de articole însumând 500 de pagini publicate din 1983 până în 2004 [2] [3] [4] . Înainte de demonstrare, afirmația teoremei era cunoscută sub numele de conjectura Wagner , deși Wagner însuși a susținut că nu a afirmat niciodată această presupunere [5] .
O afirmație mai slabă pentru copaci rezultă din teorema lui Kruskal. Afirmația a fost făcută sub forma unei ipoteze în 1937 de către matematicianul ungur Andrew Vazonyiși dovedit în 1960 independent de Joseph Kruskalși S. Tarkovski [6] [7] .
Un minor al unui graf nedirecționat G este orice graf care poate fi obținut din G printr-o secvență (posibil goală) de contracție a muchiilor și îndepărtarea muchiilor și vârfurilor lui G . Relația minoritară formează o ordine parțială pe mulțimea tuturor grafurilor finite distincte nedirecționate, deoarece această relație satisface trei axiome de ordin parțial - relația este reflexivă (orice graf este minor al lui însuși), tranzitivă (un minor al unui graf G este el însuși ). un minor al unui grafic G ) și antisimetric (dacă două grafice G și H sunt minore unul față de celălalt, ele trebuie să fie izomorfe ). Totuși, dacă graficele sunt izomorfe, ele pot fi considerate totuși obiecte diferite, atunci ordonarea pe minori formează o preordonare , o relație care este reflexivă și tranzitivă, dar nu neapărat antisimetrică [1] .
Se spune că o preordonare formează o relație complet cvasi-ordonată, dacă nu conține nici un lanț infinit descrescător, nici un anticlanț infinit [8] . De exemplu, raportul obișnuit al numerelor întregi nenegative este complet cvasi-ordonat, dar aceeași ordine în mulțimea tuturor numerelor întregi nu va fi astfel, deoarece conține un lanț descendent infinit 0, −1, −2, −3...
Teorema Robertson-Seymour afirmă că grafurile finite nedirecționate și minorele grafurilor (ca relație) sunt complet cvasi-ordonate. În mod evident, relația minoritară nu conține nicio lanț descendent infinit, deoarece orice contracție sau îndepărtare reduce numărul de muchii sau vârfuri ale graficului (numere întregi nenegative) [9] . Partea netrivială a teoremei este că nu există antilanțuri infinite, adică seturi infinite de grafice care nu sunt legate între ele printr-o relație minoritară. Dacă S este un set de grafice și M este o submulțime a lui S care conține un grafic reprezentativ pentru fiecare clasă de echivalență a elementelor minime (grafice care aparțin lui S , dar orice minor propriu al acestora nu aparține lui S ), atunci M formează un anticlanț. Astfel, afirmația echivalentă a teoremei este că pentru orice mulțime infinită S de grafice, trebuie să existe doar un număr finit de elemente minime neizomorfe.
O altă formulare echivalentă a teoremei afirmă că în orice set infinit S de grafice trebuie să existe o pereche de grafice, dintre care unul este minor al celuilalt [9] . Afirmația că orice mulțime infinită are un număr finit de elemente minime implică această ultimă afirmație, deoarece toate graficele rămase (ne-minimale) formează o astfel de pereche. În cealaltă direcție, din această formulare a teoremei rezultă că nu pot exista antilanțuri infinite, deoarece un antilanț infinit nu conține elemente legate printr-o relație minoritară.
Se spune că o familie F de grafice este închisă sub operațiunea de a lua un minor dacă orice minor al unui grafic din F aparține și lui F . Dacă F este o familie minoră închisă, atunci să fie S mulțimea de grafice care nu aparțin lui F ( complementul mulțimii F ). Conform teoremei Robertson-Seymour, în S există o mulțime finită H de elemente minime . Aceste elemente minime formează o caracterizare grafică interzisă a mulțimii F —grafice din F sunt exact acele grafice care nu au niciun grafic din H ca minor [10] [11] . Membrii setului H sunt numiți minori invalidi (sau minori interziși ) pentru familia F , iar setul H însuși este numit un set obstructiv.
De exemplu, grafurile plane sunt închise prin formarea unui minor - contractarea unei muchii într-un graf plan sau îndepărtarea unei muchii sau a unui vârf nu poate distruge planaritatea. Astfel, grafurile plane au o caracterizare prin minore interzise, care, în acest caz, sunt definite de teorema lui Wagner - mulțimea H de grafuri neplanare minime minore conține exact două grafuri, un graf complet K 5 și un graf complet bipartit K 3,3 . Graficele plane sunt exact acele grafice care nu au elemente din mulțimea { K 5 , K 3,3 } ca minore.
Existența caracterizărilor de către minori interziși pentru toate familiile de grafuri minor închise este o formulare echivalentă a teoremei Robertson-Seymour. Să presupunem că orice familie minor închisă F are o mulțime finită H de minori minime interzise și fie S orice set infinit de grafice. Definim F pentru S ca o familie de grafice care nu au minori în S . Atunci mulțimea F este minoră închisă și are o mulțime finită H de minori minime interzise. Fie C complementul lui F . S este o submulțime a lui C deoarece S și F nu se intersectează. Mulțimea H conține grafice minime din C . Luați un grafic G din H . G nu poate avea minore proprii în S , deoarece G este minim în C. În același timp, G trebuie să aibă un minor în S , deoarece altfel G ar fi un element al lui F. Astfel , G este un element al lui S , ceea ce înseamnă că H este o submulțime a lui S și toate celelalte grafice din S au minore din setul de grafice H , deci H este o mulțime finită de elemente minime ale lui S.
Pe de altă parte, să presupunem că orice set de grafice are un subset finit de grafice minime și fie F o mulțime minoră închisă . Vrem să găsim o mulțime H de grafice astfel încât graficul să fie conținut în F dacă și numai dacă nu are minore în H . Fie E mulțimea de grafice care nu sunt minore ale niciunui grafic din F și fie H o mulțime finită de elemente minime din E. Acum să fie dat un grafic arbitrar G. Fie G să aparțină lui F. G nu poate avea minori din H deoarece G aparține lui F și H este o submulțime a lui E. Acum să nu aparțină G lui F . Atunci G nu este minor al niciunui grafic din F , deoarece F este închis în minore. Astfel G aparține lui E , deci G are un minor în H.
Următoarele seturi de grafice finite sunt închise în minore și, prin urmare (conform teoremei Robertson-Seymour) au o caracterizare prin grafice interzise:
Câteva exemple de mulțimi obstructive finite erau deja cunoscute pentru unele clase chiar înainte de demonstrarea teoremei Robertson-Seymour. De exemplu, obstacolul pentru toate pădurile este o buclă (sau, dacă ne limităm la grafice simple , un ciclu cu trei vârfuri). Aceasta înseamnă că un grafic este o pădure dacă și numai dacă niciunul dintre minorele sale nu este o buclă (sau, respectiv, un ciclu cu trei vârfuri). Singurul obstacol pentru un set de căi este un arbore cu patru vârfuri, dintre care unul are gradul 3. În aceste cazuri, obstacolul este format dintr-un singur element, dar în general pot fi mai multe elemente. Teorema lui Wagner afirmă că un graf este plan dacă și numai dacă nu conține nici K 5 , nici K 3,3 ca minor. Cu alte cuvinte, mulțimea { K 5 , K 3,3 } este setul de obstacole pentru toate graficele plane și este setul minim de obstrucții. O teoremă similară afirmă că K 4 și K 2,3 sunt minore interzise pentru setul de grafuri exterioare.
Deși teorema Robertson-Seymour extinde aceste rezultate la familiile arbitrare minore închise de grafuri, ea nu înlocuiește aceste rezultate deoarece nu descrie în mod explicit setul de obstrucții pentru nicio familie. De exemplu, teorema indică faptul că mulțimea de grafuri toroidale are o mulțime finită de obstacole, dar nu dă nici o astfel de mulțime. Setul complet de minori interziși pentru graficele toroidale rămâne necunoscut și conține cel puțin 16.000 de grafice [13] .
Teorema Robertson–Seymour are o consecință importantă în teoria complexității computaționale, deoarece Robertson și Seymour au demonstrat că pentru fiecare graf fix G , există un algoritm de timp polinomial pentru a verifica dacă graficul mai mare G are un minor. Timpul de rulare al acestui algoritm este exprimat printr-un polinom cubic în dimensiunea graficului mai mare (deși există un factor constant în acest polinom care depinde superpolinom de dimensiunea lui G ), iar de această dată a fost îmbunătățit la unul pătratic de Kawarabayashi , Kobayashi și Reid [14] . Astfel, pentru orice familie F închisă în minori , există un algoritm cu timp de rulare polinom care verifică dacă graficul aparține familiei F — doar pentru toți minorii interziși pentru F , verificăm dacă graficul dat conține acest minor interzis [15] [16] [17 ] .
Totuși, pentru ca această metodă să funcționeze, este necesar să existe o mulțime finită obstructivă, iar teorema nu o dă. Teorema arată că o astfel de mulțime există, iar dacă o astfel de mulțime este cunoscută, problema devine polinomială. În practică, algoritmul poate fi aplicat doar atunci când avem o mulțime obstructivă. Ca rezultat, teorema arată că problema poate fi rezolvată în timp polinomial, dar nu oferă un algoritm specific de timp polinomial. O astfel de demonstrație a polinomialității este neconstructivă [ 18] [19] . În multe cazuri specifice, verificarea că un grafic aparține unei anumite familii care este închisă la minori se poate face mai eficient. De exemplu, planaritatea unui grafic poate fi verificată în timp liniar.
Aceeași metodă poate fi aplicată invarianților de graf cu proprietatea că, pentru orice k , familia de grafuri pentru care invariantul nu depășește k este minor închisă. De exemplu, conform acestui rezultat, lățimea arborelui, lățimea ramurilor, lățimea traseului, acoperirea vârfurilor și genul de cuibărit minim se pretează toate acestei abordări și pentru orice k fix , există un algoritm în timp polinomial pentru a verifica dacă un anumit invariant nu depășește k , iar exponentul în timpul de rulare al algoritmului nu depinde k . Problemele cu timp de rezolvare polinomial pentru orice k fix și un exponent în timpul de rulare independent de k sunt cunoscute ca probleme rezolvabile cu parametri fix..
Cu toate acestea, această metodă nu oferă un algoritm direct fixat-parametric decidabil pentru calcularea valorii unui parametru pentru un grafic dat cu k necunoscut din cauza dificultății de a găsi mulțimea minorilor interziși. În plus, factorii constanti uriași rezultați fac ca algoritmul să fie puțin folositor în practică. Astfel, dezvoltarea unor algoritmi expliciți rezolvabili cu parametri fix pentru aceste probleme cu dependență îmbunătățită de k rămâne o linie importantă de cercetare.
Friedman, Robertson și Seymour [20] au arătat că următoarea teoremă demonstrează fenomenul de independență , fiind de nedemonstrat în diverse sisteme formale mai puternice decât aritmetica Peano , dar este demonstrabilă în sisteme substanțial mai slabe decât teoria mulțimilor Zermelo-Fraenkel :
Teoremă : Pentru orice număr întreg pozitiv n există un întreg m astfel încât dacă G 1 , …, G m este o succesiune de grafice finite nedirecționate, unde fiecare grafic G i are dimensiunea cel mult n + i , atunci G j ≤ G k pentru unele j < k .(Aici , dimensiunea unui grafic este numărul total de vârfuri ale acestuia și ≤ înseamnă ordonarea după minori.)