Poliéder gráf

A poliéder gráf  egy konvex poliéder csúcsaiból és éleiből kialakított irányítatlan gráf , vagy a gráfelmélet kontextusában egy 3 csúcsú síkgráf .

Leírás

A konvex poliéder Schlegel-diagramja csúcsait és éleit pontokként és vonalszakaszokként ábrázolja az euklideszi síkon , a külső konvex sokszög partícióját alkotva kisebb konvex sokszögekre. A diagramnak nincsenek önmetszéspontjai, így minden poliéder gráf síkbeli is . Balinsky tétele szerint ez a gráf a 3-as csúcshoz kapcsolódik .

Steinitz tétele szerint ez a két tulajdonság elegendő a poliéder gráfok teljes leírásához – ezek pontosan 3 csúcshoz kapcsolódó síkgráfok. Így, ha a gráf síkbeli és 3-csúccsal összefüggő, akkor létezik egy poliéder, amelynek csúcsai és élei az eredetivel izomorf gráfot alkotnak [1] [2] . Adott egy ilyen gráf, egy konvex sokszög kisebb konvex sokszögekre való felosztásaként Tutta-féle beágyazással [3] található .

Hamiltonitás és rövidségi kitevő

Tate úgy sejtette , hogy minden köbös poliéder gráfnak (vagyis olyan poliéder gráfnak, amelyben minden csúcs pontosan három élre esik) van Hamilton-ciklusa , de ezt a sejtést William Tutt cáfolta , aki egy ellenpéldát - egy nem Hamilton-féle poliéder gráfot szerkesztett. ( Tatta grafikon ). Ha lazítjuk azt a feltételt, hogy a gráfnak köbösnek kell lennie, akkor sok más kisebb nem Hamilton poliéder gráf fog megjelenni, ezek közül az egyik 11 csúcsú és 18 élű a Herschel-gráf [4] , van egy nem Hamilton poliéder gráf is 11 csúcs, amelyben minden lap háromszög alakú - Goldner gráf - Harari [5] .

Szigorúan véve létezik egy állandó ( rövidségi kitevő[ finomítás ] ) és poliéder gráfok végtelen családja úgy, hogy a család csúcsaival rendelkező gráf leghosszabb egyszerű útjának hossza [6] [7] .

Kombinatorikus felsorolás

1996-ban meghatározták a legfeljebb 26 élű poliéder gráfok számát [8] , konkrétan a 6, 7, ..., 21 élű gráfok száma:

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

A poliéder gráfokat a csúcsaik számával is felsorolhatja , az ilyen gráfok száma:

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

Különleges alkalmak

A poliéder gráf egyszerű politópgráf, ha köbös (minden csúcsban három él konvergál), és egyszerű politópgráf, ha maximális síkgráf . A síkfákból kialakított Halin-gráfok a fa összes levelén áthaladó külső hurok hozzáadásával a poliéder gráfok másik fontos alosztályát alkotják.

Jegyzetek

  1. ↑ Günter M. Ziegler. Előadások a politópokról. - 1995. - 103. o., 4. fejezet "Steinitz-tétel 3-politópokra". — ISBN 0-387-94365-X .
  2. ↑ Branko Grünbaum. Konvex politópok. - Springer-Verlag, 2003. - 221. évf. - (Matematika diplomás szövegei). - ISBN 978-0-387-40409-7 .
  3. ↑ WT Tutte. Hogyan rajzoljunk grafikont // 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  a Wolfram MathWorld webhelyen .
  5. ↑ Weisstein, Eric W. Goldner-Harary Graph  a Wolfram MathWorld webhelyen .
  6. ↑ Weisstein, Eric W. Shortness Exponent  a Wolfram MathWorld webhelyen .
  7. ↑ Branko Grünbaum, TS Motzkin. Leghosszabb egyszerű utak poliéderes gráfokban // Journal of the London Mathematical Society. - 1962. - T. s1-37 , sz. 1 . – S. 152–160 . - doi : 10.1112/jlms/s1-37.1.152 .
  8. ↑ AJW Duijvestijn. A poliéderes (3 összekapcsolt síkbeli) gráfok száma  // Számítási matematika. - 1996. - T. 65 . - S. 1289-1293 . - doi : 10.1090/S0025-5718-96-00749-1 . Archiválva az eredetiből 2019. február 17-én.
  9. ↑ OEIS szekvencia A002840 _
  10. ↑ OEIS sorozat A000944 _

Linkek