„Fokszám (gráfelmélet)” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
Nincs szerkesztési összefoglaló |
Syp (vitalap | szerkesztései) Nincs szerkesztési összefoglaló |
||
55. sor:
Ha egy gráf minden csúcsának fokszáma ''k'', [[reguláris gráf|''k''-reguláris gráf]]nak hívjuk. Azt az összefüggő gráfot, aminek pontosan 0 vagy 2 páratlan fokszámú csúcsa van, [[Euler-kör|Euler-gráf]]nak mondjuk. (Ezek pontosan azok a gráfok, amiket meg lehet rajzolni egyetlen vonallal.)
==Fokszámsorozat==
[[File:Conjugate-dessins.svg|thumb|200px|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''<sub>1</sub> ≥ ''d''<sub>2</sub> ≥ … ≥ ''d''<sub>''n''</sub>). Egy <math>d_1 \geq d_2,\geq \dots \geq d_n</math> 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==
| |||