A matematika, azon belül a gráfelmélet területén egy hasábgráf vagy prizmagráf (prism graph) olyan gráf, melynek vázát egy hasáb alkotja.
Példák A család egyes gráfjai a kiindulásul szolgáló testről kapják nevüket:
Háromszög alapú hasábgráf – 6 csúcs, 9 él Kockagráf – 8 csúcs, 12 él Ötszög alapú hasábgráf – 10 csúcs, 15 él Hatszög alapú hasábgráf – 12 csúcs, 18 él Hétszög alapú hasábgráf – 14 csúcs, 21 él Nyolcszög alapú hasábgráf – 16 csúcs, 24 él ...
Y3 = GP(3,1)Y4 = Q3 = GP(4,1)Y5 = GP(5,1)Y6 = GP(6,1)Y7 = GP(7,1)Y8 = GP(8,1)
Bár mértani értelemben a csillagsokszögek prizma jellegű (önmagukat metsző, nem konvex) testek egy másik sorozatát képezik, ezen csillaghasábok gráfjai a hasábgráfokkal izomorfak, nem alkotnak külön gráfsorozatot.
Konstrukció A hasábgráfok az általánosított Petersen-gráfok közé tartoznak, paramétereik GP(n,1) alakban írhatók fel. Előállíthatók körgráf egyetlen éllel történő Descartes-szorzataként is.
Ahogy az a csúcstranzitív gráfok között gyakori, a prizmagráfok és előállíthatók Cayley-gráfokként. Az n rendű diédercsoport a sík szabályos n-szöge szimmetriáinak csoportja; az n-szögön forgatásokkal és tükrözésekkel hat. Két elem, a 2/n-nel való forgatás és egyetlen tükrözés segítségével generálható, és az ezzel a generátorhalmazzal előálló Cayley-gráf éppen a prizmagráf. Absztraktan kezelve a csoport prezentációja (ahol r a forgatás – rotáció –, f pedig a tükrözés – flip), a Cayley-gráfnak pedig r és f (illetve r, r−1 és f) a generátorai.
Páratlan n-ekre az n-szögű hasábgráfok előállíthatók cirkuláns gráfként. Ez a konstrukció azonban páros n-ekre nem működik.
Tulajdonságok Egy n-szögű hasáb gráfja 2n csúccsal és 3n éllel rendelkezik. Reguláris, azon belül 3-reguláris gráfok. edges. Mivel léteznek tetszőleges csúcsot bármely más csúcsba átvivő szimmetriáik, a prizmagráfok csúcstranzitívak. Mint minden poliédergráf, 3-összefüggő síkbarajzolható gráfok. Minden hasábgráfnak van Hamilton-köre.Read, R. C. and Wilson, R. J. An Atlas of Graphs, Oxford, England: Oxford University Press, 2004 reprint, Chapter 6 special graphs pp. 261, 270.
A kétszeresen összefüggő 3-reguláris gráfok közt (konstans faktoron belül) a prizmagráfoknak van a legtöbb lehetséges 1-faktora. Az 1-faktor a gráf élhalmazának három teljes párosításba való particionálása, vagy ami ezzel ekvivalens, három színnel történő élszínezése. Minden kétszeresen összefüggő n-csúcsú 3-reguláris gráfnak O(2n/2) 1-faktora van, a prizmagráfoknak pedig Ω(2n/2).. Eppstein személyes kommunikációjuk alapján Greg Kuperbergnek tulajdonítja azt a megfigyelést, hogy a prizmagráfok a maximálishoz közeli 1-faktorizációval rendelkeznek.
Az n-csúcsú prizmagráf feszítőfáinak számát a következő képlet adja meg:.
n = 3, 4, 5-re ezek a számok 75, 384, 1805, 8100, 35287, 150528, ... .
Az n-csúcsú prizmagráfok páros n esetében parciális kockák. A 3-reguláris parciális kockák kevés ismert végtelen családjának egyikét alkotják, és (négy sporadikus példa kivételével) kizárólag ezek a csúcstranzitív 3-reguláris parciális kockák..
Az ötszög alapú prizmagráf a három favastagságú gráfok tiltott minorainak egyike.. A háromszögű prizmagráf és a kockagráf favastagsága pontosan három, az összes nagyobb hasábgráf favastagsága négy.
Kapcsolódó gráfok A szabályos sokszög alapú testekből hasonlóan képzett végtelen poliédergráf-sorozatok közé tartoznak az antiprizmagráfok (antiprizmák gráfjai) és a kerékgráfok (gúlák gráfjai). A csúcstranzitív poliédergráfok közé tartoznak az arkhimédészi testek gráfjai.
Ha egy hasábgráf két körét megszakítjuk az ugyanazon pozícióban lévő egy-egy él eltávolításával, létragráfot kapunk. Ha a két törölt élt felcseréljük két keresztbe kötött éllel, Möbius-létra jön létre..
Megfordítva, a létragráf négy 2 fokszámú csúcsát egyenesen összekötve, avagy egy n≥3 hosszúságú kör és egy él Descartes-szorzatával körkörös létragráf (circular ladder graph), CLn áll elő. Ez megegyezik a hasábgráffal. Szimbolikusan: CLn = Cn × P1.
Fordítás
Jegyzetek
Kategória:Gráfcsaládok Kategória:Reguláris gráfok Kategória:Síkgráfok