Poliédergráf
A matematika, azon belül a geometriai gráfelmélet területén a poliédergráf egy konvex poliéder élváza által alkotott irányítatlan gráf. Tisztán gráfelméleti fogalmakkal leírva a poliédergráfok 3-szorosan összefüggő síkgráfok.
Jellemzésük[szerkesztés]
Egy konvex poliéder Schlegel-diagramja annak csúcsait és éleit az euklideszi sík pontjaiként és egyenes szakaszaiként jeleníti meg, egy külső konvex sokszög kisebb konvex sokszögekre való felosztását alkotva. Élei nem metszik egymást, tehát a poliédergráfok egyben síkbarajzolható gráfok is. A Balinski-tétel értelmében továbbá 3-szorosan összefüggő gráfok.
A Steinitz-tétel szerint ez a két gráfelméleti tulajdonság elegendő a poliédergráfok teljes karakterizációjához: pontosan megegyeznek a 3-szorosan összefüggő síkbarajzolható gráfokkal. Tehát, minden olyan gráfhoz, ami egyszerre síkba rajzolható és 3-szorosan csúcsösszefüggő, rendelhető egy poliéder, melynek csúcsai és élei az eredeti gráffal izomorf gráfot alkotnak.[1][2] Ha adott egy ilyen gráf, a konvex sokszög kisebb konvex sokszögekre osztásával történő reprezentációja megtalálható a Tutte-beágyazás segítségével.[3]
Hamilton-körök és rövidség[szerkesztés]
Tait gráfelméleti sejtése szerint minden 3-reguláris poliédergráf (tehát a poliédergráfok, melyekben minden csúcsból pontosan három él indul ki) rendelkezik Hamilton-körrel, de ezt a sejtést W. T. Tutte ellenpéldája, a poliédergráf, de Hamilton-kört nem tartalmazó Tutte-gráf cáfolta. Ha elengedjük a 3-regularitási követelményt, jóval kisebb, Hamilton-kör nélküli poliédergráfok is léteznek; a legkevesebb csúccsal és éllel rendelkezők egyike a 11 csúcsú, 18 élű Herschel-gráf,[4] de létezik olyan, 11 csúcsú, Hamilton-kör nélküli poliédergráf is, melynek minden lapja háromszög, ez a Goldner–Harary-gráf.[5]
Létezik továbbá egy α < 1 konstans (a rövidségi kitevő – shortness exponent) és egy végtelen sok poliédergráfból álló gráfcsalád, melyben az n-csúcsú gráfban a leghosszabb útvonal O(nα).[6][7]
Kombinatorikai leszámlálás[szerkesztés]
Duijvestijn megadja a legfeljebb 26 éllel rendelkező poliédergráfok számát;[8] A 6, 7, 8, ... éllel rendelkező poliédergráfok száma
- 1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, ... (A002840 sorozat az OEIS-ben).
Leszámlálhatók a poliédergráfok csúcsaik száma alapján is: a 4, 5, 6, ... csúcsú poliédergráfok száma
- 1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, ... (A000944 sorozat az OEIS-ben).
Speciális esetek[szerkesztés]
Ha a poliédergráf 3-reguláris, akkor egyszerű poliéder gráfja (minden csúcsból három él indul ki), ha pedig maximális síkbarajzolható, akkor szimpliciális poliéder (minden lapja háromszög) gráfja. A Halin-gráfok a poliédergráfok szintén fontos alcsoportját alkotják; ezek úgy kaphatók meg, hogy egy síkba ágyazott fa összes levelét egy külső kör segítségével összekötjük.
Fordítás[szerkesztés]
- Ez a szócikk részben vagy egészben a Polyhedral graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek[szerkesztés]
- ↑ Lectures on Polytopes, by Günter M. Ziegler (1995) ISBN 0-387-94365-X , Chapter 4 "Steinitz' Theorem for 3-Polytopes", p.103.
- ↑ Grünbaum, Branko (2003), Convex Polytopes, vol. 221 (2nd ed.), Graduate Texts in Mathematics, Springer-Verlag, ISBN 978-0-387-40409-7.
- ↑ Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society 13: 743–767, DOI 10.1112/plms/s3-13.1.743.
- ↑ Weisstein, Eric W.: Herschel Graph (angol nyelven). Wolfram MathWorld.
- ↑ Weisstein, Eric W.: Goldner-Harary Graph (angol nyelven). Wolfram MathWorld.
- ↑ Weisstein, Eric W.: Shortness Exponent (angol nyelven). Wolfram MathWorld.
- ↑ Grünbaum, Branko & Motzkin, T. S. (1962), "Longest simple paths in polyhedral graphs", Journal of the London Mathematical Society s1-37 (1): 152–160, DOI 10.1112/jlms/s1-37.1.152.
- ↑ Duijvestijn, A. J. W. (1996), "The number of polyhedral (3-connected planar) graphs", Mathematics of Computation 65: 1289–1293, DOI 10.1090/S0025-5718-96-00749-1.
További információk[szerkesztés]
- Weisstein, Eric W.: Polyhedral Graph (angol nyelven). Wolfram MathWorld