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

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

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

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

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

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

↑ 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

Weisstein, Eric W.: Polyhedral Graph (angol nyelven). Wolfram MathWorld

[1] Lectures on Polytopes, by Günter M. Ziegler (1995) ISBN 0-387-94365-X , Chapter 4 "Steinitz' Theorem for 3-Polytopes", p.103.

[grun-2] Grünbaum, Branko (2003), Convex Polytopes, vol. 221 (2nd ed.), Graduate Texts in Mathematics, Springer-Verlag, ISBN 978-0-387-40409-7.

[3] 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.

[4] Weisstein, Eric W.: Herschel Graph (angol nyelven). Wolfram MathWorld.

[5] Weisstein, Eric W.: Goldner-Harary Graph (angol nyelven). Wolfram MathWorld.

[6] Weisstein, Eric W.: Shortness Exponent (angol nyelven). Wolfram MathWorld.

[7] 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.

[8] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]