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

Irányítatlan gráfok 250px|bélyegkép|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

Fokszámösszeg-képlet, kézfogáslemma Fokszámösszeg-képlet: 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 (kézfogás-lemma).

Irányított gráf bélyegkép|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 , a kifoké pedig .

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 száma és a kifokok száma is egyenlő az élek számával.

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

Fokszámsorozat thumb|200px|Két nem izomorf gráf, melynek ugyanaz a fokszámsorozata (3, 2, 2, 2, 2, 1, 1, 1). A fokszámok sorozata egy gráf csúcsainak fokszámait tartalmazza nemnövekvő sorrendben (például d1 ≥ d2 ≥ ... ≥ dn). Egy fokszámsorozat megvalósítható, ha van olyan gráf, melynek ez a fokszámsorozata. A fokszámok sorozata gráfinvariáns, tehát izomorf gráfoknak mindig ugyanaz lesz a fokszámsorozatuk. Viszont a fokszámsorozat nem azonosít egyértelműen egy gráfot, tehát, mint az ábrán látható esetben is, tartozhat nem izomorf gráfokhoz ugyanaz a sorozat.

Források

Kategória:Gráfelmélet