Egy csúcs foka (gráfelmélet)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. június 28-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Egy gráfcsúcs foka ( valenciája ) a csúcsra eső gráfélek száma . _ A fokszámításnál az élhurkot kétszer vesszük figyelembe. [egy] $G$ $x$

Egy csúcs fokát általában vagy -vel jelöljük . A G gráf csúcsainak maximális és minimális fokát Δ( G ), illetve δ( G ) jelöljük. ábrán. 1, a maximális fok 5, a minimum 0. Egy szabályos gráfban minden csúcs foka azonos, tehát ebben az esetben a gráf fokáról beszélhetünk . $d(x)$ $\deg(v)$

A kézfogás lemma

A gráf hatványainak összegének képletével $G=(V,E)$

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

azaz bármely gráf csúcsainak fokszámainak összege egyenlő az élei számának kétszeresével. Ráadásul a képletből az következik, hogy bármely gráfban a páratlan fokú csúcsok száma páros. Ezt az állítást (és magát a képletet) kézfogási lemma néven ismerjük . Az elnevezés egy jól ismert matematikai feladatból ered: be kell bizonyítani, hogy bármely csoportban páros azoknak a száma, akik páratlan számú emberrel kezet fogtak.

Csúcsok fokozati sorrendje

Egy irányítatlan gráf csúcsfokozata egy nem növekvő sorozat . [2] Az ábrán látható grafikonhoz. 1, ennek alakja (5, 3, 3, 2, 2, 1, 0). A csúcsfokozatok sorrendje a gráfinvariáns , tehát az izomorf gráfoknál is ugyanaz . A csúcsfokozatok sorrendje azonban nem egyedi jellemzője a gráfoknak: bizonyos esetekben a nem izomorf gráfok is ugyanazzal a sorozattal rendelkeznek.

A foksorrend-probléma az, hogy meg kell találni néhány vagy az összes gráfot egy adott nem növekvő természetes számsorozattal (a nulla fokot ebben az esetben figyelmen kívül hagyhatjuk, mivel a számuk megváltozik izolált csúcsok hozzáadásával vagy eltávolításával). Az olyan sorozatot, amely egy gráf fokozatainak sorozata , grafikus sorozatnak nevezzük . A fokok összegének képletéből az következik, hogy bármely páratlan összegű sorozat (például 3, 3, 1) nem lehet egy gráf fokszámsorozata. Ennek fordítva is igaz: ha egy sorozatnak páros összege van, az egy multigráf hatványsorozata . Egy ilyen gráf felépítése meglehetősen egyszerű módon történik: a páratlan fokú csúcsokat párokba kell kombinálni , hurkokat kell hozzáadni a fennmaradó kitöltetlen csúcsokhoz.

Egy egyszerű gráfot adott sorozattal nehezebb megvalósítani . Az Erdős-Gallay tétel kimondja, hogy egy d i nem növekvő sorozat ( i = 1,…, n esetén) csak akkor lehet egyszerű gráfsorozat , ha az összege páros és az egyenlőtlenség

\sum _{{i=1}}^{{k}}d_{i}\leq k(k-1)+\sum _{{i=k+1}}^{n}\min(d_{ i},k)\quad \ k\in \{1,\dots ,n-1\}\,.

Például a sorozat (3, 3, 3, 1) nem lehet egyszerű gráfsorozat; az Erdős-Gallai egyenlőtlenséget csak 1-gyel egyenlő k esetén teljesíti, k 2-vel vagy 3-mal egyenlőre nem.

A Havel-Hakimi-kritérium szerint, ha egy nem növekvő sorozat ( d 1 , d 2 , …, d n ) egy egyszerű gráf fokozatainak sorozata, akkor ( d 2 − 1, d 3 − 1, …, d d 1 +1 − 1, d d 1 +2 , d d 1 +3 , …, d n ) egy egyszerű gráf valamilyen fokozatsorozata. Ez a tény lehetővé teszi, hogy egy polinomiális algoritmust hozzunk létre egy egyszerű gráf megtalálásához egy adott megvalósítható sorozattal.

Hasonlítsuk össze a gráf él nélküli csúcsainak kezdeti számsorát a szükséges fokokkal. Ez a szekvenciatranszformáció meghatároz legalább egy gráfcsúcsot, az összes ráeső élt, és egy csúcskészletet új, szükséges fokkomplementerekkel. A fennmaradó csúcsokat nem növekvő fokkomplementerek szerint rendezve egy egyszerű gráf nem növekvő fokszámsorát kapjuk. A transzformációt megismételve és legfeljebb n-1- szer rendezve megkapjuk a teljes gráfot.

A gráfok számbavételének területéhez tartozik az adott sorozatban található gráfok számának megtalálásának vagy becslésének problémája .

Privát értékek

A 0 fokú csúcsot izoláltnak nevezzük .
Az 1. fokú csúcsot terminálisnak ( eng. end vertex ), függőnek ( eng. pendant vertex ) vagy gráflevélnek ( eng. leaf vertex ) nevezzük. Az ilyen csúcsba beeső élt függőnek ( angol terminális (pendant) edge, end-edge ) nevezzük. ábrán. 3, a függő él {3,5}. Hasonló terminológiát használnak a fák tanulmányozása során általában és adatszerkezetként .
Az n - rendű gráf n -1 fokú csúcsát domináns csúcsnak nevezzük .

Általános tulajdonságok

Ha egy gráf minden csúcsának azonos k foka van, akkor a gráfot k fokú k szabályos vagy reguláris gráfnak nevezzük . Ebben az esetben magának a gráfnak k foka van .
Euler-útvonal akkor és csak akkor létezik egy irányítatlan, összefüggő gráfban, ha a gráfnak 0 vagy 2 páratlan fokú csúcsa van. Ha a gráf 0 páratlan fokú csúcsot tartalmaz, az Euler-út egy ciklus.
A digráf egy álerdő[ ismeretlen kifejezés ] csak akkor, ha az egyes csúcsok külső foka legfeljebb 1. A funkcionális gráf egy pszeudoerdő speciális esete, amelyben az összes csúcs külső foka egyenlő 1-gyel.
Brooks tétele szerint bármely gráf kromatikus száma , kivéve a klikket vagy a páratlan ciklust, nem haladja meg csúcsainak maximális mértékét (Δ). Viizing tétele szerint egyetlen gráf kromatikus indexe sem haladja meg a Δ + 1 értéket.
A k -degenerált gráf olyan gráf, amelyben minden részgráfnak legfeljebb k fokos csúcsa van .

Lásd még

Irányított gráfok csúcsainak be és ki - foka
Fokozat-eloszlás

Jegyzetek

↑ Distel, 5. o
↑ Distel, 278. o

Források

Distel, Reinhard (2005), Graph Theory (3. kiadás), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4 , < http://diestel-graph-theory.com/index. html > .
Erdős, P. & Gallai, T. (1960), Gráfok előírt fokszámú pontokkal , Matematikai Lapok T. 11: 264-274 , < http://www.renyi.hu/~p_erdos/1961-05.pdf > .
Hakimi, S. L. (1962): Egész számok halmazának realizálhatóságáról lineáris gráf csúcsainak fokaiként. I, Journal of the Society for Industrial and Applied Mathematics, 10. kötet: 496–506 .
Sirksma, Hirard & Hoohefen, Khan (1991), A grafikus egész számsorozat hét kritériuma , Journal of Graph Theory 15. kötet (2): 223–231 , DOI 10.1002/jgt.3190150209 .