Încorporarea graficului neconectată

O încorporare a unui grafic nelegat  este o încorporare a unui grafic nedirecționat în spațiul euclidian, astfel încât nici două cicluri ale graficului să nu aibă un coeficient de legătură diferit de zero . O încorporare plată  este o încorporare în care orice ciclu este limita unui cerc topologic al cărui interior nu este legat de grafic. Un grafic încorporabil fără legături  este un grafic care are o încorporare nelegată sau plată. Aceste grafice formează un analog tridimensional al graficelor plane [1] . În schimb, un grafic legat în esență  este unul care nu are încorporare nelegată.

Înglobările plate nu au automat legături, dar nu invers [2] . Graficul complet , graficul Petersen și celelalte cinci grafice din familia de grafice Petersen nu au înglobări nelegate [1] . Graficele de încorporare nelegate sunt închise de grafurile minore [3] și transformările Y-Δ [2] . Aceste grafuri au grafuri ale familiei Petersen drept minori interzise [4] și includ grafuri plane și grafuri de vârf [2] . Graficele pot fi recunoscute (și se poate construi o încorporare plată) în timp liniar [5] .

Definiții

Se spune că două curbe care nu se intersectează în spațiul euclidian sunt nelegate dacă există o mișcare continuă a curbelor care le transformă în două cercuri coplanare care nu se intersectează fără ca o curbă să treacă prin cealaltă sau prin ea însăși. Dacă nu există o astfel de mișcare continuă, se spune că curbele sunt legate . Legătura Hopf formată din două cercuri care trec printr-un disc întins de aceste cercuri oferă cel mai simplu exemplu de pereche de curbe legate, dar curbele pot fi legate în moduri mult mai complexe. Dacă curbele nu sunt legate, se poate găsi un disc (topologic) în spațiu delimitat de prima curbă și care nu se intersectează cu a doua. În schimb, dacă un astfel de disc există, curbele nu sunt legate.

Coeficientul de legătură a două curbe închise în spațiul tridimensional este un invariant topologic al curbei - acesta este un număr definit pentru curbe într-unul din moduri echivalente, care nu se schimbă dacă curbele sunt deplasate în spațiu continuu fără a se încrucișa. sau ei înșiși. Coeficientul de angajare se găsește proiectând o înglobare pe un plan și numărând într-un anumit mod numărul de treceri ale primei curbe peste a doua (cu semnul +1 sau −1 în funcție de direcția de trecere). Proiecția trebuie să fie „corectă”, ceea ce înseamnă că nu sunt proiectate două vârfuri în același punct, niciun vârf nu este proiectat în interiorul unei muchii, iar în orice punct al proiecției în care muchiile se intersectează, acestea se intersectează transversal . Sub astfel de restricții, orice proiecție duce la același coeficient de legătură. Coeficientul de legătură al curbelor nelegate este zero și, prin urmare, dacă o pereche de curbe are un coeficient de legătură diferit de zero, cele două curbe trebuie să fie legate. Cu toate acestea, există exemple de curbe legate care au un factor de legătură zero, cum ar fi legătura Whitehead .

Încorporarea unui grafic în spațiul tridimensional constă în maparea vârfurilor graficului la puncte din spațiu și maparea muchiilor la curbe, astfel încât fiecare punct de capăt al unei margini să fie mapat la un punct final al curbei corespunzătoare și curbele corespunzătoare la două marginile diferite nu se intersectează (cu excepția punctelor finale comune). Orice grafic finit are un număr finit (posibil exponențial) de cicluri simple diferite , iar dacă graficul este încorporat într-un spațiu tridimensional, fiecare astfel de ciclu formează o curbă închisă simplă. Este posibil să se calculeze coeficientul de legătură al fiecărei perechi de curbe care nu se intersectează formate în acest fel. Dacă toate perechile de cicluri au coeficient de legătură zero, se spune că înglobarea este nelegată [6] [1] [2] .

În unele cazuri, un grafic poate fi încorporat în spațiu în așa fel încât pentru fiecare ciclu din grafic se poate găsi un disc delimitat de acest ciclu care nu intersectează alte elemente ale graficului. În acest caz, ciclul nu trebuie să fie legat de alte cicluri ale graficului care nu îl intersectează. Se spune că o încorporare este plată dacă orice ciclu delimitează discul în modul descris [2] . În mod similar, o definiție a „investiției bune” este dată în Motwani, Raghunathan, Saran, 1988 . Vezi și Saran (1989 ) și Böhme (1990 ). O încorporare plată este neapărat deconectată, dar pot exista încorporari nelegate care nu sunt plate. De exemplu, dacă G este un grafic format din două cicluri separate și încorporarea are ca rezultat o legătură Whitehead, încorporarea este nelegată, dar nu plană.

Se spune că un grafic este în esență legat dacă orice încorporare are ca rezultat o încorporare întotdeauna legată. Deși înglobările nelegate și plane nu sunt aceleași, graficele care au înglobări nelegate se dovedesc a fi aceleași grafice ca și graficele care au încorporații plate [7] .

Exemple și contraexemple

După cum a arătat Sacks [1] , toate cele șapte grafice ale unei familii Petersen sunt în esență legate și nu contează modul în care aceste grafice sunt încorporate în spațiu, pentru orice încorporare au două cicluri legate. Aceste grafice includ graficul complet , graficul Petersen , graficul format prin eliminarea unei muchii dintr-un grafic bipartit complet și graficul tripartit complet .

Orice grafic plan are o încorporare plată și nelegată - doar încorporați graficul într-un plan situat în spațiu (tridimensional). Dacă graficul este plan, aceasta este singura modalitate de a încorpora graficul plat și nelegat - orice încorporare plată poate fi deformată continuu într-o încorporare în plan. În schimb, orice graf neplanar nelegat are mai multe înglobări nelegate [2] .

Graficul vârfurilor , format prin adăugarea unui vârf la graficul plan, are și o încorporare plată și neînlănțuită - încorporam partea plană a graficului în plan, plasăm vârful graficului (vârful care încalcă planaritatea) deasupra planului și apoi trageți muchii de la vârf la vârfuri adiacente sub formă de segmente. Orice curbă închisă pe plan delimitează un disc care nu trece prin alt element al graficului, iar orice curbă închisă prin vârf delimitează un disc deasupra planului care nu trece prin niciun alt element al graficului [2] .

Dacă graficul are o încorporare nelegată sau plată, atunci modificarea graficului prin împărțirea sau îmbinarea muchiilor acestuia, adăugarea sau eliminarea mai multor muchii între o pereche de vârfuri sau efectuarea transformărilor Y-Δ , în care un vârf de gradul trei este înlocuit cu un triunghi care leagă trei vecini, sau invers, duce la păstrarea existenței unei înglobări plate sau nelegate [2] . În special, într-un graf cubic plan (în care toate vârfurile au exact trei vecini, ca un cub), se pot face copii ale oricărui set independent de vârfuri efectuând o transformare Y-Δ, adăugând mai multe copii ale muchiilor în rezultatul. triunghiuri și apoi efectuând transformările inverse Δ -Y.

Caracterizare și recunoaștere

Dacă un grafic are o încorporare nelegată sau plată, atunci orice graf minor (graful format prin contractarea muchiilor și eliminarea muchiilor și vârfurilor) are și o încorporare nelegată sau plată. Ștergerea nu poate întrerupe posibilitatea de imbricare nelegată sau plată, iar contracția se poate face lăsând un punct de capăt al muchiei contractate în loc și comutând toate muchiile incidente la vârful opus. Astfel, prin teorema Robertson-Seymour , grafurile care au o încorporare nelegată sunt caracterizate de grafuri interzise ca grafuri care nu conțin niciunul dintr-un set finit de minori [3] .

Setul de minori interziși pentru graficele care admit înglobări nelegate a fost descoperit de Sacks [1] - șapte  grafice ale familiei Petersen sunt grafice minime legate în esență. Cu toate acestea, Sachs a fost incapabil să demonstreze că numai aceste grafice sunt grafice legate de minore-minimale, iar acest lucru a fost făcut de Robertson, Seymour și Thomas [4] .

Caracterizarea prin minori interzise a graficelor care admit încorporare nelegată conduce la un algoritm cu timp de rulare polinomial pentru recunoașterea lor, dar acest algoritm nu construiește o încorporare reală. Karavabaishi, Kreutzer și Mohar [5] au descris un algoritm de timp liniar care verifică dacă un grafic este încorporabil fără o legătură și, dacă este încorporat, construiește o încorporare plată a graficului. Algoritmul lor găsește subgrafe plane mari într-un graf dat, astfel încât, dacă există o încorporare nelegată, ele reprezintă o încorporare plană a subgrafului. Prin re-simplificarea graficului atunci când este găsit un astfel de subgraf, ei reduc problema la una în care graficul rămas este constrâns de lățimea arborelui , moment în care problema poate fi rezolvată folosind programarea dinamică .

Problema verificării efective dacă o încorporare dată este plată sau nelegată a fost pusă de Robertson, Seymour și Thomas [2] . Problema rămâne nerezolvată și este echivalentă ca complexitate cu problema desfacerii nodurilor , problema verificării dacă o curbă în spațiu este deznodat [5] . Se știe că verificarea pentru denodare (și deci și pentru cuibări nelegate) aparține clasei NP , dar nu se știe dacă aparține clasei de probleme NP-complete [8] .

Familii înrudite de grafice

Invariantul Colin de Verdière  este un număr definit pentru orice graf bazat pe teoria grafurilor algebrice . Un grafic cu un invariant Colin de Verdière care nu depășește μ pentru orice constantă fixă ​​μ formează o familie minoră-închisă, iar primele câteva astfel de familii sunt bine cunoscute - graficele cu μ ≤ 1 sunt păduri liniare (o uniune disjunsă de căi), grafice cu μ ≤ 2 sunt grafice planare , iar graficele cu μ ≤ 3 sunt grafice plane . După cum sugerează Robertson, Seymour și Thomas [2] și dovedit de Lowash și Schreiver [9] , graficele cu μ ≤ 4 sunt exact grafice cu înglobări nelegate.

Graficele plane și graficele vârfurilor permit încorporarea nelegată, la fel ca și graficele obținute prin transformări Y-Δ din ele [2] . Graficele reductibile YΔY  sunt grafice care pot fi reduse la un singur vârf printr-o transformare Y-Δ, eliminând vârfurile izolate și vârfurile suspendate (vârfurile de gradul 1) și înlocuind arcele de la un vârf cu gradul doi cu un singur arc. Aceste grafice sunt închise și la minori. Cu toate acestea, există grafice ireductibile YΔY nelegate, cum ar fi graficul de vârfuri format prin conectarea unui vârf (un vârf care încalcă planaritatea) la toate vârfurile de gradul trei ale unui dodecaedru rombic [10] . Există, de asemenea, grafice nelegate care nu pot fi transformate prin transformări Y-Δ, eliminând vârfurile izolate și suspendate și înlocuind arcele de la un vârf cu gradul doi cu un arc într-un grafic de vârf. De exemplu, o coroană cu zece vârfuri are o încorporare nelegată, dar nu poate fi convertită într-un grafic de vârfuri în modul descris mai sus [2] .

Legat de noțiunea de încorporare nelegată este noțiunea de înglobare neînnodată. Este o astfel de încorporare a graficului încât niciun ciclu simplu nu formează un nod non-trivial . Graficele care nu au o încorporare neînnodată includ K 7 și K 3,3,1,1 [6] [11] . Cu toate acestea, există minore minime interzise pentru înglobările neînnodate care nu sunt formate (spre deosebire de cele două grafice de mai sus) prin adăugarea unui vârf la un graf în mod esențial legat [12] .

Se pot defini familii de grafice prin prezența sau absența unor noduri și legături mai complexe în înglobarea lor [3] [13] , sau printr-o încorporare nelegată într -o varietate tridimensională alta decât spațiul euclidian [14] . Flapan, Naimi și Pommersheim [15] au definit o încorporare a unui grafic drept triplu legat dacă există trei cicluri, dintre care niciunul nu poate fi separat de celelalte două. Ei au arătat că K 9 nu este în esență legat de trei ori, în timp ce K 10 este legat [16] . Mai general, se poate defini o încorporare n - legată pentru oricare ca o încorporare care conține o legătură -componentă care nu poate fi împărțită de o sferă topologică în două părți separate. Graficele legate de esențiale minore-minimale sunt cunoscute pentru toți [17] .

Istorie

Întrebarea dacă o încorporare are o legătură sau un plan a fost ridicată în comunitatea de cercetare topologică la începutul anilor 1970 de către Bothe [18] . Înglobarea nelegată a atras atenția teoreticienilor de grafuri Sacks [1] , care au propus mai multe probleme conexe, inclusiv problema găsirii unei caracterizări prin grafice interzise a graficelor cu înglobări nelegate sau plate. Sachs a arătat că șapte grafice ale familiei Petersen (inclusiv ) nu au astfel de înglobări. După cum au observat Nexetril și Thomas [3] , grafurile de încorporare nelegate sunt închise în minorele grafului , ceea ce implică, prin teorema Robertson-Seymour , că există o caracterizare prin grafuri interzise. Dovada existenței unui număr finit de grafice obstructive nu conduce la o descriere explicită a acestui set de minori interziși, dar din rezultatele lui Sacks rezultă că șapte grafice ale familiei Petersen aparțin mulțimii. Aceste probleme au fost în cele din urmă rezolvate de Robertson, Seymour și Thomas [4] [7] care au arătat că aceste șapte grafice ale familiei Petersen sunt singurii minori minim interzis pentru astfel de grafice. Astfel, graficele încorporabile nelegate și graficele încorporabile plane sunt același set de grafice, iar ambele familii pot fi definite ca grafice care nu conțin elemente ale familiei Petersen ca minori.

Sacks [1] a întrebat, de asemenea, despre limitele numărului de muchii și numărul cromatic al graficelor încorporabile fără o legătură. Numărul de muchii dintr-un grafic de vârfuri încorporat fără o legătură nu depășește  — graficele de vârf maxime c au exact acest număr de muchii [1] , iar Mader [19] a demonstrat limita superioară pentru o clasă mai generală de grafice libere K 6 minori. În 1985, s-a arătat că întrebarea lui Sachs despre numărul cromatic ar fi rezolvată dacă s-ar dovedi conjectura lui Hadwiger că orice graf -cromatic are un graf complet cu vârfuri ca minor [3] . Dovada lui Robertson, Seymour și Thomas [20] a cazului conjecturii lui Hadwiger este suficientă pentru a rezolva întrebarea lui Sachs - graficele fără legături pot fi colorate cu cel mult cinci culori, deoarece orice grafic cu 6 cromatice conține un minor și nu este deconectat. , și există grafice nelegate, cum ar fi , care necesită cinci culori. Din teorema snark rezultă că orice grafic cubic încorporabil fără o legătură este colorabil cu 3 muchii .

Studiul înglobărilor fără legături a început în studiul algoritmilor la sfârșitul anilor 1980 [21] [22] . Din punct de vedere algoritmic, problema recunoașterii graficelor încorporabile fără legături și încorporabile plate a fost rezolvată când s-a dovedit caracterizarea de către minori interziși - algoritmul lui Robertson și Seymour [23] poate fi folosit pentru a verifica în timp polinomial dacă un anumit grafic conține vreunul dintre cei șapte minori interziși. [24] . Această metodă nu construiește o încorporare nelegată sau plată dacă există, ci un algoritm care construiește o încorporare [25] și a găsit mai târziu un algoritm mai eficient care rulează în timp liniar [5] .

Ultima întrebare a lui Sachs [1] despre posibilitatea unei analogii a teoremei Fari pentru grafurile nelegate nu a fost încă răspunsă. Întrebarea se pune după cum urmează: când existența unei înglobări nelegate sau plane cu margini liniare curbe sau pe bucăți implică existența unei înglobiri nelegate sau plane în care marginile sunt segmente ?

Note

  1. ↑ 1 2 3 4 5 6 7 8 9 Sachs, 1983 .
  2. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 Robertson, Seymour, Thomas, 1993a .
  3. ↑ 1 2 3 4 5 Nešetřil, Thomas, 1985 .
  4. ↑ 1 2 3 Robertson, Seymour, Thomas, 1995 .
  5. ↑ 1 2 3 4 Kawarabayashi, Kreutzer, Mohar, 2010 .
  6. ↑ 1 2 Conway, Gordon, 1983 .
  7. ↑ 12 Robertson, Seymour, Thomas, 1993b .
  8. ↑ Hass, Lagarias, Pippenger, 1999 .
  9. ↑ Lovász, Schrijver, 1998 .
  10. ↑ Truemper, 1992 .
  11. ↑ Foisy, 2002 .
  12. ↑ Foisy, 2003 .
  13. ↑ Fleming, Diesl, 2005 .
  14. ↑ Flapan, Howards, Lawrence, Mellor, 2006 .
  15. ↑ Flapan, Naimi, Pommersheim, 2001 .
  16. ↑ Pentru alte exemple de grafice nelegate de trei ori, vezi Bowlin și Foisy 2004 .
  17. ↑ Flapan, Pommersheim, Foisy, Naimi, 2001 .
  18. ↑ Bothe, 1973 .
  19. ↑ Mader, 1968 .
  20. ↑ Robertson, Seymour, Thomas, 1993c .
  21. ↑ Fellows, Langston, 1988 .
  22. ↑ Motwani, Raghunathan, Saran, 1988 .
  23. ↑ Robertson, Seymour, 1995 .
  24. ↑ Aplicabilitatea algoritmului Robertson-Seymour la această problemă a fost observată de Fellows și Langston ( Fellows, Langston, 1988 ).
  25. ↑ van der Holst, 2009 .

Literatură