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

Irányítatlan gráfok

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:

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.

${\displaystyle \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á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 ${\displaystyle \deg ^{-}(v)}$, a kifoké pedig ${\displaystyle \deg ^{+}(v)}$.^[1]

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

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

A fokszámok sorozata egy gráf csúcsainak fokszámait tartalmazza nemnövekvő sorrendben (például d₁ ≥ d₂ ≥ … ≥ d_n). Egy ${\displaystyle 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.

Források

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