Fokszám (gráfelmélet)

A gráfelméletben 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

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. Ez azt jelenti, 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

Irányított gráf

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)$.

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

Különleges fokszámértékek

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ő.

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

Ha egy gráf minden csúcsának fokszáma k, k-reguláris gráfnak hívjuk. Azt a 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.)