Cage (gráfelmélet)
| (3-6)-cage | |
 |
|
| Heawood-gráf | |
|
|
|
| Névadó | Percy John Heawood |
| Csúcsok száma | 14 |
| Élek száma | 21 |
| Átmérő | 3 |
| Kromatikus szám | 2 |
| Élkromatikus szám | 3 |
Egy cage-gráf egy olyan reguláris gráf, amelynek a lehető legkevesebb csúcsa van, adott girth paraméter mellett.
Tehát egy (r,g)-cage olyan gráf ahol minden fokszám r és a gráfban található legrövidebb kör hossza g. Minden r ≥ 2 és g ≥ 3 esetén létezik r-reguláris g-girth paraméterű gráf, ezek közül a legkevesebb csúccsal rendelkezőket hívjuk (r,g)-cage gráfoknak.
Adott r és g esetén létezhet több (r,g)-cage, például három nem izomorf (3,10)-cage létezik.
Ismert cage-k [szerkesztés]
r=1 esetén egy gráf nem tartalmazhat kört, így szükségképpen girth paramétere végtelen.
r=2 esetén a gráf körök uniója lehet csak, így girth paramétere a legkisebb kör hossza, de mivel a lehető legkevesebb csúcsot tartalmazza, ezért a (2,g)-cage gráfok g hosszú körök.
Tetszőleges r esetén:[1]
- Az (r,3)-cage a Kr+1 teljes gráf
- Az (r,4)-cage a Kr,r teljes páros gráf
r=3 esetén már számos cage-t ismerünk, az első néhány:[2]
- (3,3)-cage a K4 teljes gráf
- (3,4)-cage a K4,4 teljes páros gráf
- (3,5)-cage a Petersen-gráf
- (3,6)-cage a Heawood-gráf (melynek a tórusz felszínébe való beágyazása a Szilassi-poliéder)
- (3,7)-cage a McGee-gráf
- (3,8)-cage a Levi-gráf (másik nevén a Tutte 8-cage)
Jegyzetek [szerkesztés]
- ↑ A jelenleg ismert cage gráfok, és a nem ismertek csúcsszámára vonatkozó becslések[1]
- ↑ az ismert 3-reguláris cage gráfok g=32 ig
Források [szerkesztés]
- Wolfram MathWorld Cage Graph
- Brouwer, Andries E. Cage
