Conte minor

Un minor în teoria grafurilor  este un graf pentru un graf dat , care poate fi format din îndepărtarea muchiilor și vârfurilor și a muchiilor contractante .

Teoria grafurilor minore a început cu teorema lui Wagner , care afirmă că un graf este plan dacă și numai dacă minorii lui nu aparțin nici grafului complet K 5 , nici grafului complet bipartit K 3,3 [1] [2] . Din teorema Robertson-Seymour rezultă că analogi ai caracterizării minore interzise există pentru orice proprietate a graficelor care este păstrată sub îndepărtarea și contracția muchiilor [3] [4] .

Pentru orice grafic H , se poate verifica dacă H este minor al graficului de intrare G în timp polinomial [5] . Odată cu caracterizarea prin minori interziși, rezultă că orice proprietate de graf care se păstrează sub ștergeri și contracții poate fi recunoscută în timp polinomial [6] .

Printre alte rezultate și presupuneri care folosesc minori de graf se numără teorema structurii grafului , conform căreia grafurile care nu conțin H ca minor pot fi formate prin lipirea unor părți mai simple și conjectura Hadwiger , care leagă imposibilitatea colorării grafului cu existența. a unui grafic mare complet ca minorul lui. Variante importante ale minorilor de graf sunt minorii topologici și minorii imersați.

Definiții

Contracția muchiei este o operație care elimină o muchie dintr-un grafic și îmbină capetele muchiei într-un singur vârf. Un graf nedirecționat H este minor al altui graf nedirecționat G dacă un graf izomorf cu H poate fi obținut din G prin contractarea muchiilor, eliminând unele muchii și eliminând unele vârfuri izolate. Ordinea în care se fac contracțiile și ștergerile în G nu afectează graficul rezultat H .

Minorii grafici sunt adesea studiati în contextul mai general al minorilor matroide . În acest context, se presupune de obicei că graficele sunt conectate, pot avea bucle și margini multiple (adică sunt considerate multigrafe , nu grafice simple). Tragerea buclei și îndepărtarea muchiei de tăiere sunt interzise. Cu această abordare, eliminarea unei muchii lasă rangul graficului neschimbat, în timp ce contractarea unei muchii reduce întotdeauna rangul cu unu.

În alte contexte (ca în studiul pseudopădurilor , de exemplu ), are sens să se permită eliminarea marginilor tăietoare și să permită deconectarea graficelor, dar are și sens să se interzică multigrafele. În această versiune a teoriei graficelor minore, graficul este întotdeauna simplificat după orice contracție a muchiei pentru a elimina buclele și muchiile multiple [7]

Exemplu

În exemplul următor, graficul H este un minor al graficului G :

H.

G.

Figura următoare ilustrează acest lucru. Mai întâi, construim un subgraf al lui G eliminând muchiile punctate (și vârful izolat rezultat) și apoi contractând muchia gri (prin unirea celor două vârfuri pe care marginea le conectează):

Principalele rezultate și presupuneri

Se poate verifica cu ușurință că relația minorilor de graf formează o ordine parțială pe clasa de izomorfism a grafurilor nedirecționate - relația este tranzitivă (minorul unui graf G este el însuși un minor al lui G ) iar grafurile G și H pot fi unul celuilalt. minore dacă sunt izomorfe, deoarece orice operație non-trivială cu un minor elimină muchii sau vârfuri. Un rezultat profund al lui Neil Robertson și Paul Seymour afirmă că această ordine parțială este, de fapt, o complet cvasi-ordonată  - având în vedere o listă infinită G 1 , G 2 ,... de grafice finite, există întotdeauna două indicii i < j , astfel încât G i este un minor al graficului G j . O formulare echivalentă a enunțului este că orice set de grafice poate avea doar un număr finit de elemente minime printr-o relație minoră [8] . Acest rezultat demonstrează conjectura cunoscută până acum sub numele de conjectura Wagner. Wagner a făcut conjecturi mult mai devreme, dar a publicat-o abia în 1970 [9] .

În cursul demonstrației, Seymour și Robertson au demonstrat și teorema structurii grafului , în care au determinat, pentru orice graf fix H , structura brută a oricărui graf care nu conține H ca minor. Enunțul teoremei este lung și complicat, dar pe scurt, teorema afirmă că un astfel de graf trebuie să aibă structura unei sume peste clicuri de grafuri mai mici, care sunt obținute printr-o ușoară modificare a grafurilor încorporate în suprafețele de gen mărginit . Astfel, teoria lor stabilește o legătură fundamentală între grafurile minore și înglobările topologice ale grafurilor [10] [11] .

Pentru orice grafic H , graficele simple fără H-minore trebuie să fie rare , ceea ce înseamnă că numărul de muchii este mai mic decât unele constante ori numărul de vârfuri [12] . Mai precis, dacă H are h vârfuri, atunci un simplu n -vertex H -grafic fără minore poate avea cel mult muchii, iar unele K h -grafice fără minore au cel puțin acel număr de muchii [13] . Astfel, dacă H are h vârfuri, atunci H -graficele minore au grad mediu și, în plus, degenerare . În plus, graficele H - fără minore au o teoremă de partiționare similară cu teorema de partiționare a graficului plan - pentru orice H fix și orice n - vârf H - graf fără minor G , se poate găsi o submulțime de vârfuri de mărime , a căror îndepărtarea împarte graficul G în două subgrafe (eventual deconectate) cu cel mult 2 n /3 vârfuri fiecare [14] . Chiar mai strict, pentru orice H fix, graficele libere de H -minor- au lățimea arborelui [15] .

Conjectura lui Hadwiger face ipoteza că dacă graficul G nu conține o izomorfă minoră la un graf complet cu k vârfuri, atunci graficul G are o colorare regulată în k  − 1 culori [16] . Cazul k  = 5 este o reformulare a problemei celor patru culori . Conjectura lui Hadwiger a fost dovedită pentru k  ≤ 6 [17] , dar nu într-un mod general. Bolobas, Katlin și Erdős [18] au numit problema „una dintre cele mai profunde probleme nerezolvate din teoria grafurilor”. Un alt rezultat care leagă teorema celor patru culori cu minorii graficului este teorema snark , care a fost anunțată de Robertson, Sanders, Seymour și Thomas [19] . Teorema este o consolidare a teoremei celor patru culori și a fost prezentată (ca o presupunere) de către Tutt și afirmă că orice graf cu 3 puncte regulate care necesită ca patru culori să fie colorate în linie trebuie să conțină graficul Petersen ca minor [20]. ] [21] .

Familii de grafice închise la minori

Multe familii de grafuri au proprietatea că orice minor al unui graf din F este, de asemenea, în F . În acest caz, se spune că clasa de grafice este minoră închisă . De exemplu, pentru orice graf planar sau înglobare de graf într-o suprafață topologică fixă , nici îndepărtarea muchiilor, nici contractarea muchiilor nu poate crește genul înglobării. Astfel, graficele plane și graficele încorporabile în orice suprafață fixă ​​formează familii minor închise.

Dacă F este o familie minor închisă, atunci (datorită proprietății de cvasi-ordonare completă a minorilor) printre graficele care nu aparțin lui F , există o mulțime finită X de grafice minime minore. Aceste grafice sunt minore interzise pentru F  — un grafic aparține lui F dacă și numai dacă nu conține niciun grafic din X ca minori . Astfel, orice familie minoră închisă F poate fi caracterizată ca o familie de grafuri minore libere din X pentru o mulțime finită X de minori interziși [3] [4] .

Un exemplu binecunoscut al acestui tip de caracterizare este Teorema lui Wagner , care caracterizează grafurile plane ca grafuri care nu au nici K 5 , nici K 3,3 ca minore [1] [2] .

În unele cazuri, proprietățile graficelor dintr-o familie minor închisă pot fi strâns legate de proprietățile minorilor excluși. De exemplu, o familie închisă minoră de grafuri F are o cale mărginită dacă și numai dacă familia interzisă a familiei include o pădure [22] , F are o adâncime de arbore mărginită dacă și numai dacă minorii interziși includ o uniune de cale decuplată , F are o lățime de arbore mărginită dacă și numai dacă minorii săi interziși includ un grafic planar [23] , iar F are o lățime locală de arbore mărginită (o relație funcțională între diametru și lățime de arbore) dacă și numai dacă minorele sale interzise includ un grafic de vârf (a graf care devine plan când un singur vârf) [24] [25] . Dacă H poate fi desenat pe planul cu o singură intersecție (adică numărul de intersecții ale graficului este egal cu unul), atunci pentru graficele fără H -minor, teorema de structură simplificată este adevărată, conform căreia astfel de grafice sunt o sumă clică de grafice plane și grafice cu o lățime de arbore mărginită [26] [27] . De exemplu, atât K 5 cât și K 3,3 au un număr de intersecție de unu și, după cum a arătat Wagner, graficele libere de K 5 sunt exact sumele de 3 clicuri ale graficelor plane și un grafic Wagner cu opt vârfuri , în timp ce cele lipsite de K 5 . Graficele K 3,3 sunt exact sumele de 2 clicuri ale graficelor plane și K 5 [28] .

Variante

Minori topologici

Un grafic H este numit minor topologic al unui grafic G dacă graficul de subdiviziune al lui H este izomorf cu un subgraf al lui G [29] . Este ușor de observat că orice minor topologic este minor (în sensul obișnuit). Reversul, însă, nu este în general adevărat (de exemplu, graficul complet K 5 din graficul Petersen este minor, dar nu este un minor topologic), dar este valabil pentru un grafic cu un grad maxim care nu depășește trei [30] .

Relația dintre minorii topologici nu este complet cvasi-ordonată pe setul de grafuri finite [31] și, prin urmare, rezultatul lui Robertson și Seymour este inaplicabil minorilor topologici. Cu toate acestea, este ușor să construiești caracterizări prin minori topologici finiți interziși dintr-o caracterizare prin minori finiți interziși.

Minor scufundat

Operația grafică, numită ridicare , este un concept central în conceptul de imersiune . Ridicarea este o operație pe marginile adiacente. Având în vedere trei vârfuri v , u și w , unde (v, u) și (u, w)  sunt muchii ale graficului, ridicarea vuw , sau echivalent (v, u), (u, w)  este o operație care elimină două muchii (v). , u) și (u, w) și adaugă o muchie (v, w) . În cazul în care muchia (v, w) este deja prezentă, v și w vor fi conectate printr-o altă muchie și astfel operația este în esență o operație multigraf.

În cazul în care graficul H poate fi obținut din graficul G printr-o succesiune de operații de ridicare (peste G ) și apoi găsirea unui subgraf izomorf, spunem că H este un minor imersat al graficului G .

Există o altă modalitate de a defini minorii scufundați, care este echivalentă cu operația de ridicare. Spunem că H este un minor imersat al unui grafic G dacă există o mapare injectivă de la vârfurile lui H la vârfurile lui G astfel încât imaginile elementelor adiacente ale lui H sunt conectate în G prin căi care nu au muchii comune.

Relația minorilor scufundați este complet cvasi-ordonată pe setul de grafice finite și, prin urmare, rezultatele lui Roebrtson și Seymour sunt aplicabile minorilor scufundați. Mai mult, aceasta înseamnă că orice familie închisă în minori scufundați se caracterizează printr-o familie finită de minori încorporați interzis.

În vizualizarea graficului, minorele imersate apar ca planariizări ale graficelor neplanare  — dintr-un desen al unui grafic pe un plan cu intersecții, un minor imersat poate fi format prin înlocuirea fiecărui punct de intersecție cu un nou vârf și împărțirea fiecărei muchii încrucișate. într-o potecă. Acest lucru permite ca metodele de desen pentru graficele plane să fie extinse la graficele neplanare [32] .

Minori superficiali

Un minor superficial al unui graf G  este un minor în care muchiile grafului G , contractate pentru a obține minorul, formează subgrafe disjunse de diametru mic . Minorii superficiali formează un fel de punte între minorii graf și subgrafe, în sensul că minorii superficiali cu adâncime mare sunt la fel ca tipurile obișnuite de minori, în timp ce minorii superficiali cu adâncime zero sunt exact subgrafe [33] . Ele permit, de asemenea, extinderea teoriei grafurilor minore la clase de grafuri, cum ar fi grafurile 1-planare , care nu sunt închise în luarea minorilor [34] .

Algoritmi

Problema decidabilitatii dacă un grafic H este conținut într-un grafic G ca minor este, în general, NP-complet. De exemplu, dacă H este un ciclu cu același număr de vârfuri ca și G , atunci H este un minor al lui G dacă și numai dacă G conține un grafic hamiltonian . Totuși, dacă G este o intrare și H este fix, problema poate fi rezolvată în timp polinomial. Mai precis, timpul de rulare al verificării dacă H este un minor al lui G în acest caz este O ( n 3 ), unde n  este numărul de vârfuri din G , iar O mare ascunde o constantă care depinde supraexponențial de H [5] . Datorită unui rezultat pe graf minori, acest algoritm se îmbunătățește la O ( n 2 ) [35] . Astfel, atunci când se aplică un algoritm de timp polinomial pentru a verifica dacă un anumit grafic conține vreunul dintre minorii interziși, este posibil să recunoaștem membrii oricărei familii minore închise în timp polinomial . Totuși, pentru a aplica în mod constructiv acest rezultat, este necesar să se cunoască minorii interziși din familia grafurilor [6] .

Note

  1. ↑ 12 Lovász , 2006 , p. 77.
  2. ↑ 12 Wagner, 1937a .
  3. ↑ 1 2 Lovász, 2006 , Vol. 4, p. 78.
  4. ↑ 12 Robertson , Seymour, 2004 .
  5. ↑ 12 Robertson , Seymour, 1995 .
  6. ↑ 12 Fellows , Langston, 1988 .
  7. ↑ Lovász (2006 ) se contrazice. La pagina 76 scrie că „sunt permise muchii și bucle paralele”, dar la pagina 77 afirmă că „un grafic este o pădure dacă și numai dacă nu conține triunghiul K 3 ca minor”, ​​ceea ce este valabil doar pentru simplu. grafice .
  8. ↑ Diesel (2005 ), capitolul 12: Minori, copaci și WQO; Robertson, Seymour (2004 ).
  9. ↑ Lovász, 2006 , p. 76.
  10. ↑ Lovász, 2006 , p. 80-82.
  11. ↑ Robertson, Seymour, 2003 .
  12. ↑ Mader, 1967 .
  13. ↑ Kostochka, 1984 ; Thomason, 1984 ; Thomason, 2001 .
  14. ↑ Alon, Seymour, Thomas, 1990 ; Plotkin, Rao, Smith, 1994 ; Reed, Wood, 2009 .
  15. ↑ Grohe, 2003 .
  16. ↑ Hadwiger, 1943 .
  17. ↑ Robertson, Seymour, Thomas, 1993 .
  18. ↑ Bollobás, Catlin, Erdős, 1980 .
  19. ↑ Cu toate acestea, din 2012, dovada nu a fost încă publicată.
  20. ↑ Thomas, 1999 .
  21. ^ Pegg , 2002 .
  22. ↑ Robertson, Seymour, 1983 .
  23. ↑ Lovász (2006 ), Teorema 9, p. 81; Robertson, Seymour (1986 ).
  24. ↑ Eppstein, 2000 .
  25. ↑ Demaine, Hajiaghayi, 2004 .
  26. ↑ Robertson, Seymour, 1993 .
  27. ↑ Demaine, Hajiaghayi, Thilikos, 2002 .
  28. ↑ Wagner, 1937a ; Hall, 1943 .
  29. ↑ Diesel, 2005 , p. douăzeci.
  30. ↑ Diesel, 2005 , p. 22.
  31. ↑ Ding, 1996 .
  32. ↑ Buchheim, Chimani, Gutwenger, Jünger, Mutzel, 2014 .
  33. ↑ Nešetřil, de Mendez, 2012 .
  34. ↑ Nešetřil, de Mendez, 2012 , p. 319-321.
  35. ↑ Kawarabayashi, Kobayashi, Reed, 2012 .

Literatură

Link -uri