Scara Möbius

Scara Möbius  este un grafic circular cubic cu un număr par de vârfuri , format dintr-un ciclu cu vârfuri prin adăugarea de muchii (numite „trepte”) care conectează perechi opuse de vârfuri de ciclu. Numit astfel deoarece constă din cicluri de lungime 4 [1] conectate între ele prin muchii comune și formând topologic o bandă Möbius . Graficul bipartit complet (graficul „ case și puțuri ”) este o scară Möbius (spre deosebire de celelalte, are cicluri suplimentare de lungime 4).

Studiat mai întâi de Guy și Harari [2] .

Proprietăți

Orice scară Möbius este un grafic de vârf neplanar . Numărul de treceri ale scării Möbius este unul, iar graficul poate fi încorporat fără auto-intersecții într-un torus sau plan proiectiv (adică este un grafic toroidal ). Lee [3] a studiat încorporarea acestor grafice în suprafețe de gen superior.

Scările Möbius sunt tranzitive de vârf , dar (cu excepția ) nu tranzitive de margine  - fiecare margine a ciclului din care se formează scara aparține unui singur ciclu cu 4 margini, în timp ce fiecare treaptă aparține la două astfel de cicluri.

Dacă , atunci este bipartit . Când , conform teoremei lui Brooks , numărul cromatic este 3. Se știe [4] că scara Möbius este determinată în mod unic de polinomul său Tatta .

Scara Möbius are 392 de copaci întinși . Acest grafic are, de asemenea, cel mai mare număr de arbori spanning dintre graficele cubice cu același număr de vârfuri [5] [6] . Cu toate acestea, dintre graficele cubice cu 10 vârfuri, graficul Petersen are cel mai mare număr de arbori care se întind , care nu este o scară Möbius.

Polinoamele Tutt ale scărilor Möbius pot fi obținute printr-o formulă recursivă simplă [7] .

Numărați minorii

Scările Möbius joacă un rol important în teoria grafurilor minore . Cel mai vechi rezultat de acest tip este teorema lui Wagner [8] conform căreia un graf care nu conține -minori poate fi format folosind sume de clicuri pentru combinarea grafurilor plane și scara Möbius (în această legătură numită graf Wagner .

Toate graficele aproape plane cu 3 conexiuni [9] sunt scări Möbius sau aparțin unui număr mic de alte familii, iar restul graficelor aproape plane pot fi obținute din aceste grafice folosind o serie de operații simple [10] .

Aproape tot[ clarifica ] graficele care nu conțin un cub ca minor pot fi obținute din scări Möbius ca urmare a aplicării secvențiale a operațiilor simple [11] .

Chimie și fizică

În 1982, a fost sintetizată o structură moleculară sub forma unei scări Möbius [12] , iar de atunci astfel de grafice au fost de interes pentru chimiști și stereografie chimică [13] , în special în lumina moleculelor de ADN asemănătoare cu scara Möbius. Având în vedere acest lucru, simetriile matematice ale înglobărilor de scări Möbius au fost studiate special în [14] .

Scările Möbius sunt folosite ca model al unui inel supraconductor în experimente pentru a studia efectele topologiei de conducție în interacțiunea electronilor [15] [16] .

Optimizare combinatorie

Scările Möbius sunt, de asemenea, utilizate în informatică ca parte a unei abordări de programare cu numere întregi pentru a stabili problemele de împachetare și ordonare liniară. Unele configurații din aceste probleme pot fi folosite pentru a defini fețele politopilor care descriu relaxarea condițiilor ale programării liniare . Aceste fețe sunt numite constrângeri ale scărilor Möbius [17] [18] [19] [20] .

Vezi și

Note

  1. ↑ McSorley, 1998 .
  2. ↑ Guy, Harari, 1967 .
  3. ↑ Lee, 2005 .
  4. ↑ De Mieu, Nua, 2004 .
  5. ↑ Jacobson, Rivin, 1999 .
  6. ↑ Valdes, 1991 .
  7. ↑ Biggs, Daymrell, Sands, 1972 .
  8. ↑ Wagner, 1937 .
  9. ↑ Un grafic aproape plan  este un grafic neplan pentru care orice minor non-trivial este plan
  10. ↑ Gubser, 1996 .
  11. ↑ Maharri, 2000 .
  12. ↑ Walba, Richards, Haltiwanger 1982 .
  13. ↑ Simon, 1992 .
  14. ↑ Flapan, 1989 .
  15. ↑ Mila, Stafford, Capponi, 1998 .
  16. ↑ Deng, Xu, Liu, 2002 .
  17. ↑ Bolotașvili, Kovalev, Girlich, 1999 .
  18. ↑ Borndörfer, Weissmantel, 2000 .
  19. ↑ Grötschel, Jünger, Reinelt, 1985 .
  20. ↑ Newman, Vempala, 2001 .

Literatură

Link -uri