Fokszám (gráfelmélet)

A Wikipédiából, a szabad enciklopédiából

A gráfelméletben egy gráfban egy csúcs fokszáma azoknak az éleknek a száma, amik illeszkednek a csúcsra. Egy v csúcs fokszámának jele \deg(v).

Irányítatlan gráfok[szerkesztés | forrásszöveg szerkesztése]

Irányítatlan gráf 6 csúccsal és 7 éllel.

Egy irányítatlan gráf egy csúcsának fokszáma a csúcsba befutó élek száma, úgy értve, hogy a hurokéleket kétszer számoljuk.

Az ábrán látható gráfhoz az alábbi fokszámok tartoznak:

Csúcs Fokszám
1 2
2 3
3 2
4 3
5 3
6 1

Egy gráfban a fokszámok összege mindig páros, pontosabban az élek számának kétszerese. Ennek következménye, hogy a páratlan fokú csúcsok száma páros.

Irányított gráf[szerkesztés | forrásszöveg szerkesztése]

Irányított gráf 4 csúccsal és 5 éllel.

Irányított gráfokban megkülönböztetjük a csúcsok kifokát és befokát: a kifok azt adja meg, hány él indul egy csúcsból, a befok pedig azt, hogy hány végződik benne.

A befok jele \deg^-(v), a kifoké pedig \deg^+(v).[1]

Az ábrán látható gráfhoz az alábbi fokszámok tartoznak:

Csúcs Befok Kifok
1 0 2
2 2 0
3 2 2
4 1 1

Irányított gráfban a befokok és a kifokok összege is egyenlő az élek számával.

Különleges fokszámértékek[szerkesztés | forrásszöveg szerkesztése]

Egy gráf egy csúcsát izolált csúcsnak nevezzük, ha a fokszáma nulla. Ha a fokszám egy, levélről beszélünk; ez a fogalom elsősorban fák kapcsán fordul elő, mivel egy legalább két csúcsú fának mindig van legalább két levele.

Ha egy irányított gráf egy csúcsának nulla a befoka, forrásnak, ha a kifoka nulla, nyelőnek nevezzük.

Ha egy gráf minden csúcsának fokszáma k, k-reguláris gráfnak hívjuk. Azt az összefüggő gráfot, aminek pontosan 0 vagy 2 páratlan fokszámú csúcsa van, Euler-gráfnak mondjuk. (Ezek pontosan azok a gráfok, amiket meg lehet rajzolni egyetlen vonallal.)

Források[szerkesztés | forrásszöveg szerkesztése]

  1. Járai Antal. Bevezetés a matematikába, 3, Elte Eötvös Kiadó. ISBN 9789632840772 (2009)