Grafic poliedric

Un graf poliedric  este un graf nedirecționat format din vârfurile și muchiile unui poliedru convex sau, în contextul teoriei grafurilor, un graf planar cu 3 vârfuri .

Descriere

Diagrama Schlegel a unui poliedru convex reprezintă vârfurile și marginile sale ca puncte și segmente de linie pe planul euclidian , formând o partiție a poligonului convex exterior în poligoane convexe mai mici. Diagrama nu are auto-intersecții, deci orice graf poliedric este, de asemenea, plan . De asemenea, după teorema lui Balinsky , acest grafic este conectat la vârf 3 .

Conform teoremei lui Steinitz, aceste două proprietăți sunt suficiente pentru a descrie complet graficele poliedrice - sunt exact grafice plane legate de 3 vârfuri. Astfel, dacă graful este atât plan, cât și conectat cu 3 vârfuri, există un poliedru ale cărui vârfuri și muchii formează un grafic izomorf cu cel original [1] [2] . Având în vedere un astfel de grafic, o reprezentare a acestuia ca o partiție a unui poligon convex în poligoane convexe mai mici poate fi găsită folosind încorporarea lui Tutta [3] .

Hamiltonianitatea și exponentul scurtității

Tate a presupus că orice graf poliedric cubic (adică un graf poliedric în care fiecare vârf este incident cu exact trei muchii) are un ciclu hamiltonian , dar această presupunere a fost respinsă de William Tutt , care a construit un contraexemplu - un graf poliedric non-Hamiltonian. ( Graficul Tatta ). Dacă relaxăm condiția ca graficul să fie cubic, vor apărea multe alte grafice poliedrice non-Hamiltoniene mai mici, unul dintre ele cu 11 vârfuri și 18 muchii este graficul Herschel [4] , există și un graf poliedric non-Hamiltonian cu 11 vârfuri, în care toate fețele triunghiulare - graficul Goldner - Harari [5] .

Strict vorbind, există o constantă ( exponent de scurtare[ rafina ] ) și o familie infinită de grafuri poliedrice astfel încât lungimea celei mai lungi căi simple a unui graf cu vârfuri în familie este [6] [7] .

Enumerarea combinatorie

În 1996, a fost determinat numărul de grafice poliedrice cu până la 26 de muchii [8] , în special numărul de astfel de grafice cu 6, 7, ..., 21 de muchii este:

1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810 [9] .

De asemenea, puteți enumera graficele poliedrice după numărul de vârfuri ale acestora, numărul de astfel de grafice este:

1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, … [10] .

Ocazii speciale

Un graf poliedric este un graf politop simplu dacă este cubic (trei muchii converg la fiecare vârf) și este un graf politop simplu dacă este un graf planar maximal . Graficele halin , formate din arbori plani prin adăugarea unei bucle exterioare prin toate frunzele copacului, formează o altă subclasă importantă de grafice poliedrice.

Note

  1. ↑ Günter M. Ziegler. Prelegeri despre politopi. - 1995. - P. 103, Capitolul 4 „Teorema lui Steinitz pentru 3-politopi”. — ISBN 0-387-94365-X .
  2. ↑ Branko Grünbaum. Politopi convexe. - Springer-Verlag, 2003. - Vol. 221. - (Texte de absolvire a matematicii). - ISBN 978-0-387-40409-7 .
  3. ↑ WT Tutte. Cum se desenează un grafic // Proceedings of the London Mathematical Society. - 1963. - T. 13 . — S. 743–767 . - doi : 10.1112/plms/s3-13.1.743 .
  4. ^ Weisstein , Eric W. Herschel Graph  pe site- ul Wolfram MathWorld .
  5. ^ Weisstein, Eric W. Goldner-Harary Graph pe site- ul Wolfram MathWorld .  
  6. ^ Weisstein, Eric W. Shortness Exponent pe site- ul Wolfram MathWorld .  
  7. ↑ Branko Grünbaum, TS Motzkin. Cele mai lungi căi simple în graficele poliedrice // Journal of the London Mathematical Society. - 1962. - T. s1-37 , nr. 1 . — S. 152–160 . - doi : 10.1112/jlms/s1-37.1.152 .
  8. ↑ AJW Duijvestijn. Numărul de grafice poliedrice (planare cu 3 conexiuni)  // Mathematics of Computation. - 1996. - T. 65 . - S. 1289-1293 . - doi : 10.1090/S0025-5718-96-00749-1 . Arhivat din original pe 17 februarie 2019.
  9. ↑ Secvența OEIS A002840 _
  10. ↑ Secvența OEIS A000944 _

Link -uri