| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén egy k-degenerált gráf olyan irányítatlan gráf, melynek bármely részgráfjában található legfeljebb k fokszámú csúcs: tehát a részgráf valamely csúcsa a részgráfnak k vagy kevesebb élével érintkezik. Adott gráf degeneráltsága az a legkisebb k érték, melyre a gráf k-degenerált. A gráf degeneráltsága a gráf ritkaságának a mértéke, és konstans faktor távolságra található más gráf-ritkasági mértékektől, például a gráf arboricitásától. A degeneráltság további megnevezései a k-mag szám (k-core number), szélesség (width) és kapcsoltság (linkage), lényegét tekintve pedig megegyezik a színezési számmal (coloring number) vagy Szekeres–Wilf-számmal (Szekeres and Wilf után). A k-degenerált gráfokat nevezik k-induktív gráfoknak (k-inductive graphs) is. Egy gráf degeneráltsága számítható a minimális fokszámú csúcsokat ismételten eltávolító algoritmus segítségével. A k-nál kisebb fokszámú csúcsok ismételt eltávolításával kapott összefüggő komponensek a gráf k-magjai, és a gráf degeneráltsága a legnagyobb k érték, amire rendelkezik k-maggal. (hu)
- A matematika, azon belül a gráfelmélet területén egy k-degenerált gráf olyan irányítatlan gráf, melynek bármely részgráfjában található legfeljebb k fokszámú csúcs: tehát a részgráf valamely csúcsa a részgráfnak k vagy kevesebb élével érintkezik. Adott gráf degeneráltsága az a legkisebb k érték, melyre a gráf k-degenerált. A gráf degeneráltsága a gráf ritkaságának a mértéke, és konstans faktor távolságra található más gráf-ritkasági mértékektől, például a gráf arboricitásától. A degeneráltság további megnevezései a k-mag szám (k-core number), szélesség (width) és kapcsoltság (linkage), lényegét tekintve pedig megegyezik a színezési számmal (coloring number) vagy Szekeres–Wilf-számmal (Szekeres and Wilf után). A k-degenerált gráfokat nevezik k-induktív gráfoknak (k-inductive graphs) is. Egy gráf degeneráltsága számítható a minimális fokszámú csúcsokat ismételten eltávolító algoritmus segítségével. A k-nál kisebb fokszámú csúcsok ismételt eltávolításával kapott összefüggő komponensek a gráf k-magjai, és a gráf degeneráltsága a legnagyobb k érték, amire rendelkezik k-maggal. (hu)
|
