Teorema de îndreptare a graficului lui Fari

Teorema lui Farey  este o afirmație teoretică a grafurilor despre posibilitatea de a îndrepta muchiile oricărui graf plan . Cu alte cuvinte, permisiunea de a desena marginile nu ca segmente, ci ca curbe, nu extinde clasa graficelor plane.

Numit după matematicianul maghiar István Fáry [1] , deși a fost dovedit independent de Klaus Wagner în 1936 [2] și Stein în 1951 [3] .

Afirmație: orice graf planar simplu are o reprezentare plană în care toate muchiile sunt reprezentate ca segmente de linie .

Dovada

Una dintre modalitățile de a demonstra teorema Fari este utilizarea inducției matematice [4] . Fie G un graf plan  simplu cu n vârfuri. Putem considera graficul ca maxim planar, dacă este necesar, putem adăuga muchii la graficul original G . Toate fețele lui G în acest caz trebuie să fie triunghiuri, deoarece putem adăuga o muchie oricărei fețe cu mai multe laturi fără a rupe planaritatea graficului, ceea ce contrazice convenția de maximalitate a graficului. Alegem vreo trei vârfuri a , b , c , formând o față triunghiulară a graficului G . Vom demonstra prin inducție pe n că există o altă înglobare combinatorică izomorfă cu muchii directe ale graficului G în care triunghiul abc este fața exterioară a înglobării. ( Izomorfismul combinatoriu înseamnă că vârfurile, muchiile și fețele noului desen pot fi făcute să corespundă elementelor desenului vechi, păstrând în același timp toate relațiile de incidență dintre muchii, vârfuri și fețe, nu doar între vârfuri și muchii. ) Baza inducției este trivială când a , b și c sunt singurele vârfuri din G ( n =3 ).

După formula lui Euler pentru graficele plane, graficul G are 3n − 6 muchii . În mod echivalent, dacă definim deficitul unui vârf v în G ca 6 − grade ( v ) , suma deficitelor este 12 . Fiecare vârf din G poate avea un deficit de cel mult trei, deci există cel puțin patru vârfuri cu un deficit pozitiv. În special, putem alege un vârf v cu cel mult cinci vecini care este diferit de a , b și c . Să se formeze G' prin îndepărtarea vârfului v din graficul G și triangularea feței f obținută după îndepărtarea vârfului v . Prin inducție, graficul G' are o încorporare combinatorică izomorfă a muchiei drepte în care abc este o față exterioară. Deoarece înglobarea rezultată G a fost combinatoric izomorfă cu G' , ștergerea din acesta a muchiilor care au fost adăugate pentru a obține graficul G' lasă o față f , care este acum un poligon P cu cel mult cinci laturi. Pentru a obține un desen G cu o înglobare combinatorică izomorfă cu muchii drepte, vârful v trebuie adăugat la poligon și conectat prin segmente la vârfurile poligonului. După teorema galeriei de imagini, există un punct în interiorul P unde poate fi plasat un vârf v , astfel încât muchiile care leagă vârful v cu vârfurile poligonului P să nu intersecteze alte muchii ale poligonului, ceea ce completează demonstrația.

Etapa de inducție a demonstrației este ilustrată în dreapta.

Rezultate înrudite

De Freysix, Pach și Polak au arătat cum să găsești în timp liniar un model cu muchii drepte pe o rețea cu dimensiuni dependente liniar de dimensiunea graficului, dând un set universal de puncte cu dimensiuni pătratice. O metodă similară a fost folosită de Schneider pentru a demonstra limitele îmbunătățite și caracterizarea planarității , unde s-a bazat pe un ordin de incidență parțial. Lucrarea sa subliniază existența unei anumite partiționări a muchiilor unui graf planar maxim în trei copaci, care este cunoscut sub numele de pădurea Schneider .

Teorema de „ambalaj de cauciuc” a lui Tutt afirmă că orice graf planar cu trei conexiuni poate fi desenat pe plan fără intersecții, astfel încât marginile sale să fie segmente de linie și fața sa exterioară să fie un poligon convex [5] . Denumirea reflectă faptul că o astfel de încorporare poate fi găsită ca punct de echilibru pentru un sistem de arcuri reprezentând marginile graficului.

Teorema lui Steinitz afirmă că orice graf planar cu 3 conexiuni poate fi reprezentat ca muchiile unui poliedru convex în spațiul tridimensional. O încorporare cu muchii drepte ale unui grafic poate fi obținută ca proiecție a unui astfel de poliedru pe un plan.

Teorema de împachetare a cercurilor afirmă că orice grafic plan poate fi reprezentat ca graficul de intersecție al unui set de cercuri disjunse în plan. Dacă plasăm fiecare vârf al graficului în centrul cercului corespunzător, obținem o reprezentare a graficului cu muchii drepte.

Probleme nerezolvate în matematică : Are vreun grafic plan o reprezentare cu muchii directe în care lungimile tuturor muchiilor sunt numere întregi?

Haiwo Harbort a ridicat întrebarea dacă pentru orice graf plan există o reprezentare cu muchii directe în care toate lungimile muchiilor sunt numere întregi [6] . Este corectă ipoteza lui Harbort?, rămâne o întrebare deschisă (din 2014). Cu toate acestea, se știe că există o încorporare cu muchii directe întregi pentrugraficele cubice[7].

Sachs [8] a ridicat întrebarea dacă orice graf cu o încorporare nelegată în spațiul euclidian tridimensional are o încorporare nelegată în care toate muchiile sunt reprezentate prin segmente de linie, prin analogie cu teorema Farey pentru înglobarile bidimensionale.

Vezi și

Note

  1. ↑ Fáry, 1948 , p. 229–233.
  2. ↑ Wagner, 1936 .
  3. ↑ Stein, 1951 .
  4. ↑ Dovada de mai sus o găsiți în cartea lui V. V. Prasolov. Elemente de topologie combinatorie si diferentiala. M.: MTsNMO, 2004.
  5. ↑ Tutte, 1963 , p. 743–767.
  6. ↑ Harborth, Kemnitz, Moller, Sussenbach, 1987 ; Kemnitz, Harborth, 2001 ; Mohar, Thomassen, 2001 .
  7. ↑ Geelen, Guo, McKinnon, 2008 .
  8. ↑ Sachs, 1983 .

Literatură