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

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 2Sablon:Pí/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 $⟨r,f\mid r^n,f^2,(rf{)}^2⟩$ (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⁻¹ és f) a generátorai.

Páratlan n-ekre az n-szögű hasábgráfok előállíthatók $C_{2n}^{2,n}$ 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.

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(2^n/2) 1-faktora van, a prizmagráfoknak pedig Ω(2^n/2).

Az n-csúcsú prizmagráf feszítőfáinak számát a következő képlet adja meg:

$\frac{n}{2}((2+\sqrt{3}{)}^n+(2-\sqrt{3}{)}^n-2)$

n = 3, 4, 5-re ezek a számok

75, 384, 1805, 8100, 35287, 150528, ... Sablon:OEIS.

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), CL_n áll elő. Ez megegyezik a hasábgráffal. Szimbolikusan: CL_n = C_n × P₁.

Fordítás

• Sablon:Fordítás