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.Lectures on Polytopes, by Günter M. Ziegler (1995) , Chapter 4 "Steinitz' Theorem for 3-Polytopes", p.103.. 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..
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,. 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..
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α)...
Kombinatorikai leszámlálás Duijvestijn megadja a legfeljebb 26 éllel rendelkező poliédergráfok számát;. 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, ... . 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, ... .
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
Jegyzetek
További információk
Kategória:Geometriai gráfok Kategória:Síkgráfok