Ahhoz, hogy megértsük a csúcs fokon belüli és kívüli fokát, először meg kell tanulnunk a csúcs fokának fogalmát. Ezek után könnyen megérthetjük egy csúcs be- és külfokozatát. Tudnunk kell, hogy a be- és kifokozat csak az irányított gráfban határozható meg. Irányítatlan gráf segítségével kiszámíthatjuk egy csúcs fokát. Az irányítatlan gráfban nem tudjuk kiszámítani egy csúcs be- és kifokát.

Egy csúcs foka

Ha meg akarjuk találni a gráf egyes csúcsainak fokát, ebben az esetben meg kell számolnunk, hogy egy adott csúcs hány relációt hoz létre a másik csúcshoz. Más szóval egy csúcs fokát az adott csúcshoz csatlakozó élek számának kiszámításával határozhatjuk meg. Egy csúcs fokszámát deg(v) segítségével jelezzük. Ha van egy egyszerű gráf, amely n számú csúcsot tartalmaz, ebben az esetben bármelyik csúcs foka a következő lesz:

 Deg(v) = n-1 ∀ v ∈ G 

Egy csúcs képes élt alkotni a gráf összes többi csúcsával, kivéve önmagát. Tehát egy egyszerű gráfban egy csúcs fokszáma a gráf csúcsainak számától mínusz 1-től fog kiderülni. Itt az 1-et a saját csúcsra használjuk, mert önmagában nem csinál hurkot. Ha a gráf tartalmazza az önhurokkal rendelkező csúcsokat, akkor az ilyen típusú gráf nem lesz egyszerű gráf.

Példa:

Ebben a példában van egy gráfunk, amelynek 6 csúcsa van, azaz a, b, c, d, e és f. Az 'a' csúcsnak 5-ös foka van, és az összes többi csúcsnak 1-es foka van. Ha bármelyik csúcsnak 1-es a foka, akkor ezt a típusú csúcsot 'végcsúcsnak' nevezzük.

A gráfoknak két olyan esete van, amelyben figyelembe vesszük egy csúcs fokát, amelyeket a következőképpen írunk le:

• Irányítatlan gráf
• Irányított grafikon

Most részletesen megtanuljuk egy irányított gráf csúcsának fokát, és egy irányítatlan gráfban a csúcs fokát.

Egy irányítatlan gráf csúcsának foka

Ha van irányítatlan gráf, akkor ebben a típusú gráfban nem lesz irányított él. Az irányítatlan gráfban egy csúcs fokának meghatározására szolgáló példák a következők:

1. példa: Ebben a példában egy irányítatlan gráfot fogunk figyelembe venni. Most megtudjuk, hogy a gráf egyes csúcsai milyen fokszámúak.

Megoldás: A fenti irányítatlan gráfban összesen 5 számú csúcs van, azaz a, b, c, d és e. Az egyes csúcsok mértékét a következőképpen írjuk le:

• A fenti gráf 2 élt tartalmaz, amelyek az 'a' csúcsban találkoznak. Ezért Deg(a) = 2
• Ez a gráf 3 élt tartalmaz, amelyek a 'b' csúcsban találkoznak. Ezért Deg(b) = 3
• A fenti gráf 1 élt tartalmaz, amelyek a 'c' csúcsban találkoznak. Ezért Deg(c) = 1. A c csúcsot függő csúcsnak is nevezik.
• A fenti gráf 2 élt tartalmaz, amelyek a 'd' csúcsban találkoznak. Ezért Deg(d) = 2.
• A fenti gráf 0 élt tartalmaz, amelyek az 'e' csúcsban találkoznak. Innen Deg(a) = 0. Az e csúcsot izolált csúcsnak is nevezhetjük.

2. példa: Ebben a példában egy irányítatlan gráfot fogunk figyelembe venni. Most megtudjuk, hogy a gráf egyes csúcsai milyen fokszámúak.

Megoldás: A fenti irányítatlan gráfban összesen 5 számú csúcs van, azaz a, b, c, d és e. Az egyes csúcsok mértékét a következőképpen írjuk le:

A csúcs foka a = deg(a) = 2

A b csúcs foka = deg(b) = 2

A csúcs foka c = deg(c) = 2

A csúcs foka d = deg(d) = 2

A csúcs foka e = deg(e) = 0

Ebben a gráfban nincs függő csúcs, és az 'e' csúcs egy elszigetelt csúcs.

A csúcs foka az irányított gráfban

Ha a gráf egy irányított gráf, akkor ebben a gráfban minden csúcsnak befelé és kifelé kell lennie. Tegyük fel, hogy van egy irányított gráf. Ezen a grafikonon a következő lépésekkel megtudhatjuk egy csúcs fokon belüli, kívüli és fokát.

Egy csúcs fokán belüli

Egy csúcs fokon belüli foka több élként írható le v-vel, ahol v a terminális csúcs jelzésére szolgál. Más szóval leírhatjuk úgy, hogy számos él jön a csúcsba. A deg szintaxis segítségével^-(v), felírhatjuk egy csúcs in-fokát. Ha meg akarjuk határozni egy csúcs fokon belüli fokát, akkor ehhez meg kell számolnunk a csúcsban végződő élek számát.

Egy csúcson kívüli fokozat

Egy csúcs külső foka több élként írható le v-vel, ahol v a kezdeti csúcs jelzésére szolgál. Más szóval leírhatjuk úgy, hogy számos él jön ki a csúcsból. A deg szintaxis segítségével⁺(v), felírhatjuk egy csúcs külső fokát. Ha meg akarjuk határozni egy csúcs külső fokát, akkor ehhez meg kell számolnunk a csúcsból kiinduló élek számát.

Egy csúcs foka

Egy csúcs fokszámát a deg(v) segítségével jelöljük, ami megegyezik a csúcs belső fokának és egy csúcs külső fokának összeadásával. Egy csúcs fokának szimbolikus ábrázolása a következőképpen írható le:

 Deg(v) = deg-(v) + deg+(v) 

1. példa: Ebben a példában van egy gráfunk, és meg kell határoznunk az egyes csúcsok fokszámát.

Megoldás: Ehhez először megtudjuk egy csúcs fokát, egy csúcs belső fokát, majd egy csúcs külső fokát.

Amint látjuk, a fenti gráf összesen 6 csúcsot tartalmaz, azaz v1, v2, v3, v4, v5 és v6.

Fokozaton:

Egy csúcs fokon belüli foka v1 = deg(v1) = 1

Egy csúcs fokon belüli v2 = deg(v2) = 1

Egy csúcs fokon belüli v3 = deg(v3) = 1

Egy csúcs fokon belüli foka v4 = deg(v4) = 5

Egy csúcs fokon belüli foka v5 = deg(v5) = 1

Egy csúcs fokon belüli foka v6 = deg(v6) = 0

Kilépési fokozat:

Egy csúcs külső foka v1 = deg(v1) = 2

Egy csúcs külső foka v2 = deg(v2) = 3

Egy csúcs külső foka v3 = deg(v3) = 2

Egy csúcs külső foka v4 = deg(v4) = 0

Egy csúcs külső foka v5 = deg(v5) = 2

Egy csúcs külső foka v6 = deg(v6) = 0

Egy csúcs foka

A fent leírt definíció segítségével tudjuk, hogy egy csúcs foka Deg(v) = fok^-(v) + te⁺(v). Most a következő képlet segítségével számoljuk ki:

Egy csúcs foka v1 = deg(v1) = 1+2 = 3

int húrhoz

Egy csúcs foka v2 = deg(v2) = 1+3 = 4

Egy csúcs foka v3 = deg(v3) = 1+2 = 3

Egy csúcs foka v4 = deg(v4) = 5+0 = 5

Egy csúcs foka v5 = deg(v5) = 1+2 = 3

Egy csúcs foka v6 = deg(v6) = 0+0 = 0

2. példa:

Ebben a példában van egy irányított gráfunk 7 csúcsával. Az 'a' csúcs 2 élt tartalmaz, azaz az 'ad'-t és 'ab'-t, amelyek kifelé mennek. Ezért az 'a' csúcs tartalmazza a kimenő fokot, ami 2. Hasonlóképpen az 'a' csúcsnak is van egy 'ga' éle, amely az 'a' csúcs felé közelít. Ezért az 'a' csúcs tartalmazza az in-fokot, ami 1.

Megoldás: A fenti csúcsok be- és kilépési fokát a következőképpen írjuk le:

Fokozaton:

Egy csúcs fokonkénti foka a = deg(a) = 1

Egy csúcs fokonkénti értéke b = deg(b) = 2

Egy csúcs fokon belüli foka c = deg(c) = 2

Egy csúcs fokon belüli d = deg(d) = 1

Egy csúcs fokonkénti e = deg(e) = 1

Egy csúcs fokonkénti f = deg(f) = 1

Egy csúcs fokonkénti értéke g = deg(g) = 0

Kilépési fokozat:

Egy csúcs külső foka a = deg(a) = 2

Egy csúcs külső foka b = deg(b) = 0

Egy csúcs külső foka c = deg(c) = 1

Egy csúcs külső foka d = deg(d) = 1

Egy csúcs külső foka e = deg(e) = 1

Egy csúcs külső foka f = deg(f) = 1

Egy csúcs külső foka g = deg(g) = 2

Az egyes csúcsok foka:

Tudtuk, hogy egy csúcs foka Deg(v) = fok^-(v) + te⁺(v). Most a következő képlet segítségével számoljuk ki:

Egy csúcs foka a = deg(a) = 1+2 = 3

Egy csúcs foka b = deg(b) = 2+0 = 2

Egy csúcs foka c = deg(c) = 2+1 = 3

Egy csúcs foka d = deg(d) = 1+1 = 2

Egy csúcs foka e = deg(e) = 1+1 = 2

Egy csúcs foka f = deg(f) = 1+1 = 2

Egy csúcs foka g = deg(g) = 0+2 = 2

3. példa: Ebben a példában van egy irányított gráfunk, amelynek 5 csúcsa van. Az 'a' csúcs 1 élt, azaz 'ae'-t tartalmaz, amelyek kifelé mennek. Ennélfogva az 'a' csúcs tartalmaz egy kilépési fokozatot, ami 1. Hasonlóképpen, az 'a' csúcsnak is van egy 'ba' éle, amely az 'a' csúcs felé közelít. Ezért az 'a' csúcs tartalmazza az in-fokot, ami 1.

Megoldás: A fenti csúcsok be- és kilépési fokát a következőképpen írjuk le:

Fokozaton

Egy csúcs fokonkénti foka a = deg(a) = 1

Egy csúcs fokonkénti értéke b = deg(b) = 0

Egy csúcs fokon belüli foka c = deg(c) = 2

Egy csúcs fokon belüli d = deg(d) = 1

Egy csúcs fokonkénti e = deg(e) = 1

Kilépési fokozat:

Egy csúcs külső foka a = deg(a) = 1

Egy csúcs külső foka b = deg(b) = 2

Egy csúcs külső foka c = deg(c) = 0

Egy csúcs külső foka d = deg(d) = 1

Egy csúcs külső foka e = deg(e) = 1

Az egyes csúcsok foka:

Tudtuk, hogy egy csúcs foka Deg(v) = fok^-(v) + te⁺(v). Most a következő képlet segítségével számoljuk ki:

Egy csúcs foka a = deg(a) = 1+1 = 2

Egy csúcs foka b = deg(b) = 0+2 = 2

Egy csúcs foka c = deg(c) = 2+0 = 2

Egy csúcs foka d = deg(d) = 1+1 = 2

Egy csúcs foka e = deg(e) = 1+1 = 2

4. példa: Ebben a példában van egy gráfunk, és meg kell határoznunk az egyes csúcsok fokát, fokon belüli és kívüli fokát.

Megoldás: Ehhez először megtudjuk egy csúcs belső fokát, majd egy csúcs külső fokát.

Amint látjuk, a fenti gráf összesen 8 csúcsot tartalmaz, azaz 0, 1, 2, 3, 4, 5 és 6.

Fokozaton:

fordított karakterlánc java-ban

Egy csúcs fokon belüli foka 0 = deg(0) = 1

Egy csúcs fokon belüli foka 1 = fok(1) = 2

Egy csúcs fokonkénti foka 2 = deg(2) = 2

Egy csúcs fokon belüli foka 3 = fok(3) = 2

Egy csúcs fokon belüli foka 4 = fok(4) = 2

Egy csúcs fokon belüli foka 5 = fok(5) = 2

Egy csúcs fokon belüli foka 6 = deg(6) = 2

Kilépési fokozat:

Egy csúcs külső foka 0 = fok(0) = 2

Egy csúcs külső foka 1 = fok(1) = 1

Egy csúcs külső foka 2 = fok(2) = 3

Egy csúcs külső foka 3 = fok(3) = 2

Egy csúcs külső foka 4 = fok(4) = 2

Egy csúcs külső foka 5 = fok(5) = 2

Egy csúcs külső foka 6 = fok(6) = 1

Az egyes csúcsok foka:

Tudtuk, hogy egy csúcs foka Deg(v) = fok^-(v) + te⁺(v). Most a következő képlet segítségével számoljuk ki:

Egy csúcs foka 0 = fok(0) = 1+2 = 3

Egy csúcs foka 1 = fok(1) = 2+1 = 3

Egy csúcs foka 2 = fok(2) = 2+3 = 5

Egy csúcs foka 3 = fok(3) = 2+2 = 4

Egy csúcs foka 4 = fok(4) = 2+2 = 4

Egy csúcs foka 5 = fok(5) = 2+2 = 4

Egy csúcs foka 6 = fok(5) = 2+1 = 3

Grafikon fokozatos sorrendje

Egy gráf fokszámsorrendjének meghatározásához először meg kell határoznunk a gráf minden csúcsának fokszámát. Ezt követően növekvő sorrendben írjuk fel ezeket a fokozatokat. Ezt a sorrendet/sorozatot nevezhetjük a gráf fokszámsorozatának.

Például: Ebben a példában három gráfunk van, amelyeknek 3, 4 és 5 csúcsa van, és az összes gráf fokszámsora 3.

A fenti grafikonon 3 csúcs található. A grafikon sorozatának mértékét a következőképpen írjuk le:

A fenti grafikonon 4 csúcs található. Ennek a grafikonnak a fokozati sorrendjét a következőképpen írjuk le:

A fenti grafikonon 5 csúcs található. Ennek a grafikonnak a fokozati sorrendjét a következőképpen írjuk le: