Fokszám (gráfelmélet)

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

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.

$\sum _{v\in V}\deg(v)=2|E|$

Ennek következménye, hogy a páratlan fokú csúcsok száma páros (kézfogás-lemma).

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

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

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 d₁ ≥ d₂ ≥ … ≥ d_n). Egy $d_{1}\geq d_{2},\geq \dots \geq d_{n}$ 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.