Cage (gráfelmélet)

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez
(3-6)-cage
Heawood-gráf
Heawood-gráf

Névadó Percy John Heawood
Csúcsok száma 14
Élek száma 21
Sugár 3
Átmérő 3
Derékbőség 6
Kromatikus szám 2
Élkromatikus szám 3
Automorfizmusok 336
Génusz 1

Azokat a speciális gráfokat nevezzük cage-nek (kalitkának) amelyek reguláris gráfok, és egy rögzített girth (a legrövidebb kör a gráfban) mellett a lehető legkevesebb csúcsuk van.

Tehát az (r,g)-cage-k speciális elemei annak a gráfcsaládnak amik azokból a gráfokból állnak 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 olyan gráf ami r-reguláris és amiben a girth éppen g. Mivel ezek közül a legkevesebb csúccsal rendelkezőket hívjuk (r,g)-cage gráfoknak, ezért ezekben az esetekben létezik is (r,g)-cage. Rögzített r és g esetén létezhet több (r,g)-cage is, például három nem izomorf (3,10)-cage létezik.

Ismert cage-ek[szerkesztés]

r=1 esetén egy gráf nem tartalmazhat kört, így semmilyen véges g esetén nincs (1,g)-cage.

r=2 esetén egy gráf csak diszjunkt körök uniója lehet. Ezekben az esetekben a girth nyilvánvalóan a legkisebb kör hossza. Mivel azokat a gráfokat nevezzük cage-nek amik ilyen feltételek mellett a lehető legkevesebb csúcsot tartalmazzák, ezért a (2,g)-cage gráfok pontosan a g hosszú körök.

r=3 esetén már számos cage-t ismerünk, az első néhány:[1]

Tetszőleges r esetén:[2]

Jegyzetek[szerkesztés]

  1. az ismert 3-reguláris cage gráfok g=32 ig
  2. A jelenleg ismert cage gráfok, és a nem ismertek csúcsszámára vonatkozó becslések [1] Archiválva 2009. január 25-i dátummal a Wayback Machine-ben

Források[szerkesztés]