Girth (gráfelmélet)

A Wikipédiából, a szabad enciklopédiából
(Girthparaméter szócikkből átirányítva)

A gráfelméletben akkor mondjuk, hogy egy gráf girth-e (ejtsd: görsz-e) k, ha a gráfban található legrövidebb kör k hosszú. Ha a gráf nem tartalmaz kört (erdő), akkor a girth-e végtelen.

A „girth” szakszónak nincs bejáratott magyar fordítása, néha a derékbőség vagy bőség kifejezést használják rá.

Tetszőleges k ≥ 2, g ≥ 3 esetén létezik k-reguláris g-girthparaméterű gráf, ezek közül a legkevesebb csúccsal rendelkező gráfokat nevezzük cage-gráfoknak.

Példák[szerkesztés]

  • Egy n hosszú kör girth-e n.
  • Egy négyzetrács-gráf girth-e 4.
  • Ha egy gráf klikkszáma legalább 3 akkor a gráf girth-e is 3.
  • A teljes gráf girth-e 3, ha .
  • A teljes páros gráf girth-e 4, ha és .

A girthparaméter és a kromatikus szám kapcsolata[szerkesztés]

Ha egy gráf girth-e nagyobb, mint 3, akkor a gráf háromszögmentes, vagyis a klikkszáma legfeljebb kettő. A klikkszám az egyik legismertebb és legegyszerűbb alsó becslése a kromatikus számnak. A klikkszám és kromatikus szám kapcsolatáról szóló egyik klasszikus eredmény (a Mycielski-konstrukció) szerint konstruálható olyan gráf aminek a klikkszáma csak kettő, de a kromatikus száma tetszőlegesen nagy. Vagyis a klikkszám bár alsó becslése a kromatikus számnak, önmagában (más gráfparaméterek használata nélkül) nem alkalmas a kromatikus szám felső becslésére. Az általánosabb állítást, miszerint tetszőleges a és b egész számokra létezik a girth-ű és b kromatikus számú gráf, Erdős Pál bizonyította először a valószínűségi módszer segítségével. Így a kromatikus számhoz hasonlóan a girth sem használható önmagában (más gráfparaméterek használata nélkül) a kromatikus szám felső becslésére.

Források[szerkesztés]