graf planar simplu 3-conex parametrizat prin numărul nodurilor From Wikipedia, the free encyclopedia
Î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.
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]
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]
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]
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.