Graf poliedric
În teoria grafurilor geometrice, o ramură a matematicii, un graf poliedric este graful neorientat format din vârfurile și laturile unui poliedru convex. Alternativ, în termeni din teoria grafurilor, grafurile poliedrice sunt grafuri planare 3-conexe.
Caracterizare[modificare | modificare sursă]
Diagrama Schlegel a unui poliedru convex reprezintă vârfurile și laturile sale ca puncte și segmente în planul euclidian, formând subdiviziuni a unui poligon convex exterior ca poligoane convexe mai mici. Nu are intersectări, așa că orice graf poliedric este și un graf planar. În plus, după teorema lui Balinski, este un graf 3-conex, adică fiecare vârf (nod) este conectat la cel puțin alte trei vârfuri.
Conform teoremei lui Steinitz, aceste două proprietăți teoretice ale grafurilor sunt suficiente pentru a caracteriza complet grafurile poliedrice: sunt exact grafurile planare 3-conexe. Adică, ori de câte ori un graf este atât planar, cât și 3-conex, există un poliedru ale cărui vârfuri și laturi formează un graf izomorf.[1][2] Având în vedere un astfel de graf, o reprezentare a acestuia ca o subdiviziune a unui poligon convex în poligoane convexe mai mici poate fi găsită folosind încorporarea Tutte.[3]
Enumerare combinatorică[modificare | modificare sursă]
Duijvestijn prezintă un număr de grafuri poliedrice cu până la 26 de muchii.[4] Numerele acestor grafuri cu 6, 7, 8, ... laturi este[5]
- 1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, ...
De asemenea, se pot enumera grafurile poliedrice după numărul lor de vârfuri (noduri): pentru grafurile cu 4, 5, 6, ... vârfuri, numărul de grafuri poliedrice este[6]
- 1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, ...
Cazuri particulare[modificare | modificare sursă]
Un graf poliedric este graful unui poliedru simplu dacă este cubic (adică fiecare vârf are trei muchii) și este graful unui poliedru simplu dacă este un graf planar maxim. Grafurile Halin, grafuri formate dintr-un arbore planar la care se adaugă un ciclu exterior care conectează toate frunzele, formează o altă subclasă importantă a grafurilor poliedrice.
Note[modificare | modificare sursă]
- ^ en Günter M. Ziegler (1995), Lectures on Polytopes, ISBN: 0-387-94365-X , Chapter 4 "Steinitz' Theorem for 3-Polytopes", p. 103
- ^ en Grünbaum, Branko (), Convex Polytopes, Graduate Texts in Mathematics, 221 (ed. 2nd), Springer-Verlag, ISBN 978-0-387-40409-7.
- ^ en Tutte, W. T. (), „How to draw a graph”, Proceedings of the London Mathematical Society, 13: 743–767, doi:10.1112/plms/s3-13.1.743, MR 0158387
- ^ en Duijvestijn, A. J. W. (), „The number of polyhedral (3-connected planar) graphs” (PDF), Mathematics of Computation, 65: 1289–1293, doi:10.1090/S0025-5718-96-00749-1
- ^ Șirul A002840 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
- ^ Șirul A000944 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
