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 csúcs fokszámának jele .

Irányítatlan gráfok[szerkesztés]

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]

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 .[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]

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[szerkesztés]

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 d1d2 ≥ … ≥ 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[szerkesztés]

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