Hasábgráf
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 szerkesztés
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ó szerkesztés
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.[1]
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.[1]
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.[1]
Tulajdonságok szerkesztés
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.[2]
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).[3]
Az n-csúcsú prizmagráf feszítőfáinak számát a következő képlet adja meg:[4]
n = 3, 4, 5-re ezek a számok
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.[5]
Az ötszög alapú prizmagráf a három favastagságú gráfok tiltott minorainak egyike.[6] 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 szerkesztés
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.[7]
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ő.[8] Ez megegyezik a hasábgráffal. Szimbolikusan: CLn = Cn × P1.
Fordítás szerkesztés
- Ez a szócikk részben vagy egészben a Prism 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
- ↑ a b c Weisstein, Eric W.: Prism graph (angol nyelven). Wolfram MathWorld
- ↑ 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.
- ↑ Eppstein, David (2013), "The complexity of bendless three-dimensional orthogonal graph drawing", Journal of Graph Algorithms and Applications 17 (1): 35–55, DOI 10.7155/jgaa.00283. 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.
- ↑ Jagers, A. A. (1988), "A note on the number of spanning trees in a prism graph", International Journal of Computer Mathematics 24 (2): 151–154, DOI 10.1080/00207168808803639.
- ↑ Marc, Tilen (2015), Classification of vertex-transitive cubic partial cubes.
- ↑ Arnborg, Stefan; Proskurowski, Andrzej & Corneil, Derek G. (1990), "Forbidden minors characterization of partial 3-trees", Discrete Mathematics 80 (1): 1–19, DOI 10.1016/0012-365X(90)90292-P.
- ↑ Guy, Richard K. & Harary, Frank (1967), "On the Möbius ladders", Canadian Mathematical Bulletin 10: 493–496, DOI 10.4153/CMB-1967-046-4.
- ↑ (2013. szeptember 1.) „Total Embedding Distributions of Circular Ladders”. Journal of Graph Theory 74 (1), 32–57. o. DOI:10.1002/jgt.21690.