Acoperire plană

O acoperire plană a unui graf finit G  este un graf finit de acoperire a lui G care este un graf plan . Orice grafic care poate fi încorporat în planul proiectiv are o acoperire plană. Conjectura nerezolvată a lui Seiya Negami afirmă că numai aceste grafice au acoperiri plane [1] .

Existența unui înveliș plan este o proprietate închisă sub minori [2] , și de aceea poate fi descrisă de un număr finit de minori interziși , dar nu se cunoaște setul exact al minorilor interziși. Din aceleași motive, există un algoritm de timp polinomial pentru a testa dacă un graf dat are o acoperire plană, dar nu este cunoscută o descriere explicită a acestui algoritm.

Definiție

O mapare de acoperire de la un grafic C la un alt grafic H poate fi descrisă printr-o funcție f de la vârfurile lui C la vârfurile lui H , care pentru fiecare vârf v al lui C creează o bijecție între vecinătatea lui v și vecinătatea lui f ( v ) [3] . Dacă H este un graf conex , fiecare vârf al lui H trebuie să aibă același număr de vârfuri în preimaginea lui C [2] . Acest număr se numește numărul de straturi ale hărții, iar C se numește graficul de acoperire al lui G. Dacă ambele C și H sunt finite și C este un grafic plan , C se numește acoperire plană a lui H.

Exemple

Graficul unui dodecaedru obișnuit are o simetrie care mapează fiecare vârf cu un vârf antipodal. Setul de perechi antipodale de vârfuri și adiacențele lor pot fi, de asemenea, privite ca un grafic, graficul Petersen . Dodecaedrul formează o acoperire plană a acestui graf neplan [4] . Acest exemplu arată că nu orice grafic cu o acoperire plană este el însuși plan. Când un graf plan acoperă unul neplan, numărul de straturi trebuie să fie par [5] [6] .

Graficul unei prisme k -gonale are 2k vârfuri și este plan cu două k -fețe -gonale și k fețe pătrate. Dacă k  =  ab , și , atunci graficul are un strat a acoperind maparea într-o prismă cu laturile b în care două vârfuri ale prismei k sunt mapate la același vârf al prismei b dacă ambele aparțin aceluiași k - fetele gonale si distanta de la una la alta este multiplu al lui b . De exemplu, o prismă dodecagonală poate forma o acoperire cu 2 straturi a unei prisme hexagonale , o acoperire cu 3 straturi a unui cub sau o acoperire cu 4 straturi a unei prisme triunghiulare . Aceste exemple arată că un grafic poate avea multe acoperiri plane diferite și poate fi o acoperire plană pentru multe grafice. Mai mult, aceste exemple arată că fibra unui înveliș plan poate fi arbitrar mare. Ele nu numai că acoperă prisme, de exemplu, o prismă hexagonală poate acoperi și un graf comun neplanar K 3,3 prin identificarea perechilor antipodale de vârfuri [7] .

Operațiuni de păstrare a acoperirii

Dacă graficul H are o acoperire plană, atunci același lucru este valabil pentru orice grafic minor al graficului H [2] . Un G minor al unui grafic H poate fi format prin îndepărtarea muchiilor și vârfurilor din H și contractând muchiile în H . Graficul de acoperire C poate fi transformat în același mod - pentru fiecare vârf eliminat din H îi eliminăm preimaginea în C , iar pentru fiecare muchie contractată sau vârf din H îi micșorăm preimaginea la C . Rezultatul acestor operații pe C va fi un minor din C care acoperă G . Deoarece orice minor al unui graf plan este el însuși plan, aceasta oferă o acoperire plană a minorului lui G.

Deoarece graficele cu acoperiri plane sunt închise sub operațiunea de a lua minori, din teorema Robertson-Seymour rezultă că ele pot fi descrise printr-un set finit de minori interziși [8] . Un grafic este un minor interzis pentru această proprietate dacă nu are acoperire plană, dar toți minorii săi au acoperiri plane. Această descriere poate fi folosită pentru a demonstra existența unui algoritm de timp polinomial care testează existența unei acoperiri plane prin căutarea fiecărui minor interzis și returnează „o acoperire plană există” dacă acea căutare nu găsește niciuna [9] . Cu toate acestea, din moment ce setul exact de minori interziși pentru această proprietate nu este cunoscut, această dovadă a existenței nu este constructivă și nu conduce la o descriere explicită a setului de minori interziși sau la un algoritm bazat pe aceștia [10]

O altă operație asupra graficelor care păstrează existența unei acoperiri plane este transformarea stea-triunghi , care înlocuiește orice vârf de gradul trei din H cu un triunghi al celor trei vecini ai săi [2] . Cu toate acestea, transformarea inversă, transformarea stea delta, nu păstrează neapărat acoperiri plane.

Mai mult, unirea disjunctă a două grafuri care au acoperiri va avea, de asemenea, un înveliș format ca unire disjunsă a grafurilor de acoperire. Dacă două învelișuri au aceeași fibră, atunci va fi și fibra unirii lor.

Ipoteza lui Negami

Probleme nerezolvate în matematică : Orice graf conex cu o acoperire plană are o încorporare în planul proiectiv?

Dacă un grafic H are o încorporare în planul proiectiv , atunci are în mod necesar o acoperire plană dată de imaginea inversă a lui H în capacul dublu orientabil planului proiectiv, care este o sferă. Negami [11] a demonstrat contrariul, că dacă un graf conex H are o acoperire plană cu două straturi, atunci H trebuie să aibă o încorporare în planul proiectiv [11] [12] . Presupunerea că H este conectat este necesară aici, deoarece uniunea disjunctă a graficelor plane proiectiv poate să nu fie plană proiectiv [13] , dar să aibă totuși o acoperire plană, uniunea disjunctă a capacelor duble orientabile.

O acoperire obișnuită a unui grafic H  este o acoperire rezultată din grupul de simetrie al graficului său de acoperire - imaginile inverse ale fiecărui vârf din H formează o orbită a grupului. Negami [14] a demonstrat că orice graf conex cu o acoperire plană regulată poate fi încorporat într-un plan proiectiv [14] [15] . Pe baza acestor două rezultate, el a presupus că, de fapt, orice graf conex cu o acoperire plană este proiectiv [14] [16] . Din 2013, ipoteza a rămas nerezolvată [17] . Este cunoscută și sub denumirea de „ conjectura Negami”, deoarece poate fi reformulată ca afirmația că numărul minim de fibre ale unei acoperiri plane, dacă există, trebuie să fie fie 1, fie 2 [18] .

Asemenea graficelor cu acoperiri plane, graficele cu înglobări în plan proiectiv pot fi descrise de minorii interziși. În acest caz, se cunoaște setul exact de minori interziși, sunt 35. 32 dintre ei sunt conectați, iar unul dintre aceste 32 de grafice apare în mod necesar ca minor în orice graf planar neproiectiv conectat [19] [20] . Când Negami și-a prezentat conjectura, s-a dovedit că 31 dintre acești 32 de minori interziși fie nu au coperți plane, fie pot fi reduse printr-o transformare stea-triunghi la grafice mai simple din această listă [14] [18] [21] [22 ] [ 23] . Singurul grafic rămas pentru care acest lucru nu a fost încă făcut este K 1,2,2,2 , un grafic de vârf cu șapte vârfuri care formează scheletul unei piramide octaedrice cu patru dimensiuni . Dacă arătăm că K 1,2,2,2 nu are acoperiri plane, aceasta va fi o dovadă completă a presupunerii. Pe de altă parte, dacă presupunerea nu este adevărată, K 1,2,2,2 va fi un contraexemplu minim [24] .

O presupunere înrudită a lui Michael Fellows, deja rezolvată, se referă la emulatorii planari , o generalizare a acoperirilor plane în care vecinătățile graficelor sunt mapate mai degrabă surjectiv decât bijectiv [25] [26] [27] . Graficele cu emulatori plani, ca și graficele [29][28]cu acoperiri plane, sunt închise sub transformări minore și stea-triunghi [30] . Conjectura este adevărată pentru emulatorii obișnuiți derivați din automorfisme ale graficului de acoperire subiacent, similar cu rezultatul lui Negami [14] pentru acoperiri plane regulate [26] . Cu toate acestea, s-a dovedit că unele dintre cele 32 de minore interzise conectate pentru grafurile planare proiectiv au emulatori planari [31] [32] [17] . Prin urmare, ipoteza Fellowes nu este corectă. Găsirea setului complet de minori interziși pentru existența emulatorilor plani rămâne o problemă deschisă [33] .

Note

  1. ↑ Hliněny, 2010 , p. unu.
  2. ↑ 1 2 3 4 Hliněný, 2010 , p. 2 Propunerea 1.
  3. ↑ Hliněny, 2010 , p. 2 Definiție.
  4. ↑ Inkmann, Thomas (2011 ): „Această construcție este ilustrată în Figura 1, unde dodecaedrul este prezentat ca o acoperire dublă plană a graficului Petersen”.
  5. ↑ Arhidiacon, Richter, 1990 .
  6. ↑ Negami, 2003 .
  7. ↑ Zelinka, 1982 .
  8. ↑ Robertson, Seymour, 2004 .
  9. ↑ Robertson, Seymour, 1995 .
  10. ↑ Fellows, Langston (1988 ); Fellows, Koblitz (1992 ). Neconstructivitatea verificării algoritmice a existenței acoperirilor plane k -fold a fost prezentată ca exemplu de către Fellowes și Koblitz.
  11. ↑ 12 Negami , 1986 .
  12. ↑ Hliněny, 2010 , p. 2 Teorema 2.
  13. ↑ De exemplu, două grafice Kuratowski sunt plane proiectiv, orice unire a două dintre ele nu este ( Arhidiacon 1981 ).
  14. ↑ 1 2 3 4 5 Negami, 1988 .
  15. ↑ Hliněny, 2010 , p. 3 Teorema 3.
  16. ↑ Hliněny, 2010 , p. 4 Conjectura 4.
  17. ↑ 1 2 Chimani, Derka, Hliněny, Klusáček, 2013 .
  18. ↑ 12 Huneke , 1993 .
  19. ↑ Hliněny, 2010 , p. patru.
  20. ↑ O listă a minorilor planari proiectivi interziși poate fi găsită în Arhidiacon (1981 ). Negami Negami (1988 ) a afirmat observația corespunzătoare pentru 103 grafice plane neproiective ireductibile din Glover, Huneke, Wang (1979 ).
  21. ↑ Hliněny, 1998 .
  22. ↑ Arhidiacon, 2002 .
  23. ↑ Hliněny, 2010 , p. 4–6.
  24. ↑ Hliněny, 2010 , p. 6–9.
  25. ↑ Fellows, 1985 .
  26. ↑ 12 Kitakubo , 1991 .
  27. ↑ Hliněny, 2010 , p. 9 Definiție, p..
  28. ↑ Hliněny, 2010 , p. 9 Propunerea 13.
  29. ↑ Glineny atribuie acest fapt Fellows și scrie că dovada lui nu este banală
  30. ↑ Hliněny, 2010 , p. 9, Conjectura 14.
  31. ↑ Hliněny, 2010 , p. 9–10.
  32. ↑ Rieck, Yamashita, 2010 .
  33. ↑ Hliněny, 2010 , p. zece.

Literatură

Surse secundare despre conjectura Negami

Surse principale privind acoperirile plane

Literatură auxiliară