Grafic toroidal

Un graf toroidal  este un graf care poate fi desenat pe un tor în așa fel încât marginile acestuia să se intersecteze numai la vârfuri comune.

Din punct de vedere formal, acesta este un grafic care poate fi încorporat într-un tor .

Proprietăți

• Numărul cromatic al oricărui graf toroidal nu depășește 7 [1] .
  • Un exemplu de graf toroidal cu număr cromatic 7 este un graf complet [2] .

• Numărul cromatic al oricărui graf toroidal fără triunghiuri nu depășește 4 [3] .

• Prin analogie cu teorema Farey , orice graf toroidal poate fi desenat cu muchii ca segmente într-un dreptunghi cu limite periodice (adică se identifică limite opuse ale pătratului) [4] . De asemenea, teorema lui Tutta se aplică în acest caz .

• Graficele toroidale permit imbricarea cărților cu maximum 7 foi [5] .

• Teorema Robertson-Seymour garantează că grafurile toroidale pot fi definite printr-un set finit de grafuri interzise. Cu toate acestea, setul de grafice interzise în acest caz este necunoscut, iar numărul lor este de cel puțin 250815 [6] .

Exemple

• Orice grafic cu numărul de intersecție egal cu 1 este toroidal.
  • În special, acestea sunt graficul complet și graficul bipartit complet (" graficul caselor și puțurilor ") și toate celelalte scări Möbius .
• grafic complet ,
• grafic bipartit complet ,
• conte de Petersen ,
• Contele de Heawood ,
• Graficul Möbius-Cantor [7] ,
• unul dintre snark-urile lui Blanuchi [8] .

Vezi și

• Graficul planar
• Teoria grafurilor topologice
• poliedrul Chasar

Note

1. ↑ Heawood, 1890 .
2. ↑ Chartrand & Zhang, 2008 .
3. ↑ Kronk & White, 1972 .
4. ↑ Kocay, Neilson, Szypowski, 2001 .
5. ↑ Endo, 1997 .
6. ↑ Myrvold & Woodcock, 2018 .
7. ↑ Marusic & Pisanski, 2000 .
8. ↑ Orbanic și colab., 2004 .

Link -uri

• Chartrand, Gary; Zhang Ping. Teoria grafurilor cromatice. - CRC Press, 2008. - ISBN 978-1-58488-800-0 .
• Endo, Toshiki. Numărul de pagini al graficelor toroidale este de cel mult șapte // Matematică discretă. - 1997. - Vol. 175, nr. 1–3. - P. 87-96. - doi : 10.1016/S0012-365X(96)00144-6 .
• Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan. Forme unice discrete pe rețele și aplicații la parametrizarea rețelei 3D // Proiectare geometrică asistată de computer. - 2006. - Vol. 23, nr. 2. - P. 83-112. - doi : 10.1016/j.cagd.2005.05.002 .
• Heawood P. J.  Teoreme de colorare a hărţilor // Trimestrial J. Math. Oxford Ser. - 1890. - Vol. 24. - P. 322-339.
• Kocay W., Neilson D., Szypowski R.  Drawing graphs on the torus  // Ars Combinatoria. - 2001. - Vol. 59. - P. 259-277. Arhivat din original pe 24 decembrie 2004.
• Kronk, Hudson V.; White, Arthur T.  O teoremă cu 4 culori pentru graficele toroidale // Proceedings of the American Mathematical Society . - 1972. - Vol. 34, nr. 1. - P. 83-86. - doi : 10.2307/2037902 .
• Marusic, Dragan; Pisanski, Tomaz.  Remarcabilul graf Petersen generalizat G (8,3)  // Math. Slovaca. - 2000. - Vol. 50. - P. 117-121.  (link indisponibil)
• Myrvold, Wendy; Woodcock, Jennifer. Un set mare de obstacole de torus și modul în care au fost descoperite. - 2018. - Vol. 25. doi : 10.37236/3797 .
• Neufeld, Eugen; Myrvold, Wendy. Testare practică de toroidalitate // Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. - 1997. - P. 574-580.
• Orbanic, Alen; Pisanski, Tomaz; Randic, Milano; Servatius, Brigitte. Blanuša dublă // Math. comun. - 2004. - Vol. 9, nr. 1. - P. 91-103.