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 ( után). A k-degenerált gráfokat nevezik k-induktív gráfoknak (k-inductive graphs) is.. Egy gráf degeneráltsága lineáris időben 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.
Példák Minden erdő rendelkezik izolált csúccsal (egyetlen éllel sem érintkezik) vagy levél csúccsal (pontosan egy éllel érintkezik); ezért a fák és erdők mind 1-degenerált gráfok.
Minden véges síkbarajzolható gráfnak van 5 vagy kisebb fokszámú csúcsa, ezért minden síkbarajzolható gráf 5-degenerált, és bármely síkbarajzolható gráf degeneráltsága legfeljebb 5. Hasonlóan, a külsíkgráfok degeneráltsága legfeljebb kettő,. az Apollóniusz-hálózatoké pedig három.
A véletlen skálafüggetlen hálózatok Barabási–Albert-modelljének. jellemzője az m paraméter, ami megadja, hogy a gráfhoz adott minden csúcshoz m korábban hozzáadott csúcs kapcsolódik. Ebből következik, hogy az így kialakított hálózat bármely részgráfjában van legfeljebb m fokszámú csúcs (a részgráfban a gráfhoz legutoljára hozzáadott csúcs), tehát a Barabási–Albert-hálózatok automatikusan m-degeneráltak.
A k-reguláris gráfok degeneráltsága pontosan k. Ennél erősebb állítás is tehető: egy gráf degeneráltsága pontosan akkor egyezik meg a csúcsok maximális fokszámával, ha legalább egy összefüggő komponense a maximális fokszámmal reguláris. Bármely más gráf esetében a degeneráltság kisebb a maximális fokszámnál., p. 78: "It is easy to see that col(G) = Δ(G) + 1 if and only if G has a Δ(G)-regular component." In the notation used by Jensen and Toft, col(G) is the degeneracy plus one, and Δ(G) is the maximum vertex degree.
Definíciók és ekvivalenciák A G gráf által definiált „színezési száma” az a legkisebb κ, amire létezik a G csúcsainak olyan rendezése, hogy minden csúcsnak kevesebb mint κ, a rendezésben előtte álló szomszédja van. Nem tévesztendő össze G kromatikus számával, ami a minimális számú szín, amivel ki lehet színezni a gráfot úgy, hogy nincs két szomszédos, azonos színű csúcs; a színezési számhoz tartozó rendezés ugyan megad egy sorrendet, amivel végre lehet hajtani színezési számnyi színnel a gráf előbb említett módon történő színezését, de ennél általában a kromatikus szám értéke kisebb.
A G gráf degeneráltságát úgy határozta meg, mint a legkisebb k érték, amire G minden feszített részgráfja tartalmaz k vagy annál kevesebb szomszéddal rendelkező csúcsot. A definícióban feszített részgráfok helyett tetszőleges részgráfok is megengedhetők, hiszen a részgráf csúcsai kisebb vagy egyenlő fokszámúak lehetnek, mint ugyanazon csúcshalmaz feszített részgráfjának csúcsai.
A színezési szám és a degeneráltság koncepciója egyenértékű: bármely véges gráf degeneráltsága eggyel kevesebb a színezési számnál.; , Proposition 1, page 1084. Hiszen, ha egy gráf rendelkezik κ színezési számú rendezéssel, akkor minden H részgráfjában a rendezésben utolsó, H-hoz tartozó csúcsnak legfeljebb κ − 1 H-beli szomszédja van. Megfordítva, ha G k-degenerált, akkor egy k + 1 színezési számú rendezés előállítható egy legfeljebb k csúccsal rendelkező v csúcs ismételt megkeresésével, a v a gráfból eltávolításával, a megmaradt csúcsok rendezésével és a v a rendezés végéhez adásával.
Egy harmadik, ekvivalens megfogalmazás szerint G pontosan akkor k-degenerált (avagy legfeljebb k + 1 a színezési száma), ha G olyan irányított körmentes gráffá orientálható, melynek ki-foka legfeljebb k.. Egy ilyen irányítás elérhető, ha minden él irányát úgy választjuk meg, hogy a színezési számhoz tartozó rendezésben korábbi csúcs felé mutasson. Megfordítva, ha adott egy k kifokú irányítás, egy k + 1 színezési számú rendezés előállítható az irányított körmentes gráf topologikus rendezésével.
k-magok Egy G gráf k-magja olyan maximális összefüggő részgráf, melyben minden csúcs foka legalább k. Ezzel ekvivalens megfogalmazás, hogy a G gráf valamely összefüggő komponense, amit a k-nál alacsonyabb fokszámú csúcsok ismételt törlésével kapunk. Ha a gráfban létezik egy nem üres k-mag, akkor G degeneráltsága nyilvánvalóan legalább k, és G degeneráltsága pontosan egyezik azzal a legnagyobb k-val, amire G-nek van k-magja.
Egy csúcs k-értéke (coreness) , ha beletartozik egy -magba, de nem tartozik bele egyetlen -magba sem.
A k-mag fogalmát ismeretségi hálózatok klaszterezési szerkezetének tanulmányozására. és véletlen gráfok evolúciójának leírására vezették be;; ;. léteznek alkalmazásai a bioinformatika; . és különböző hálózatok vizuális megjelenítése területén.; . Alkalmasak gráfok sűrű komponenseinek megkeresésére, gráfok megjelenítésére, klikkek keresésére (mivel egy k-klikk éppen egy k−1-mag).
Algoritmusok leírja, hogy lehetséges a véges G gráf olyan csúcsrendezését lineáris időben előállítani, ami a rendezés színezési számát optimalizálja; egy bucket típusú („vödör”) elsőbbségi sort használva, amely ismételten megkeresi és eltávolítja a legalacsonyabb fokszámú csúcsot.
Az algoritmus működése részletesen: Inicializáljuk az L kimeneti listát. A G-beli v csúcsokhoz számítsunk ki egy-egy dv értéket, a v azon szomszédainak számát, melyek még nem találhatók meg L-ben. Kezdetben ezek egyszerűen a csúcsok fokszámai. Inicializálunk egy D tömböt úgy, hogy D[i] tartalmazza azon v csúcsok listáját, melyek még nem találhatók meg L-ben, melyhez dv = i. Inicializáljuk k értékét 0-ra. Ismételjük a következőt n alkalommal: Vizsgáljuk át a tömb elemeit, D, D, ... amíg el nem érünk egy olyan i-hez, amire D[i] nem üres. Állítsuk k értékét max(k,i)-re Válasszunk ki egy v csúcsot D[i]-ből. Adjuk hozzá v-t az L elejéhez és távolítsuk el D[i]-ből. A v minden olyan w szomszédjához, mely még nem tagja L-nek, vonjunk ki egyet dw-ből és mozgassuk w-t D-nek a dw értékének megfelelő elemébe.
Az algoritmus futásának végén k tartalmazza G degeneráltságát, L pedig a csúcsok a színezési szám szerinti optimális rendezéshez szükséges listáját. A G i-magjai az L prefixumai, melyek azokból a csúcsokból állnak, melyeket azután adtunk L-hez, hogy k először az i-nél nagyobb vagy egyenlő értéket vett fel.
Az L, dv, D és k változók inicializálása lineáris időben megoldható. Az egyenként eltávolított v csúcsok megtalálásának és a D elemeibe a v szomszédainak beírásának ideje dv adott lépésnél felvett értékével arányos; azonban ezen értékek összege a gráf éleinek számával egyezik meg (minden él a későbbi végpontjával járul hozzá a végösszeghez), ezért a teljes idő mégis lineáris.
Kapcsolata más gráfparaméterekkel Ha egy G gráfot körmentesen orientálunk k kifokkal, akkor élei szétoszthatók k erdőbe úgy, hogy minden csúcs kifelé irányú éléhez egy erdőt választunk. Így a G arboricitása legfeljebb degeneráltságával egyezik meg. Megfordítva, egy n-csúcsú gráf, ami k erdőbe felosztható, legfeljebb k(n − 1) éllel rendelkezik, ezért van olyan csúcsa, aminek fokszáma legfeljebb 2k− 1 – tehát degeneráltsága kevesebb az arboricitás kétszeresénél. Polinom időben kiszámítható a gráf olyan irányítása is, ami a kifokot minimalizálja, de nem feltétlenül körmentes. Az ilyen irányítású gráf élei hasonló módon szétoszthatók k pszeudoerdőbe, és megfordítva, egy gráf éleinek k pszeudoerdőbe való szétosztásával egy k-kifokú orientációt kapunk (mindig kifok−1 orientációt választva az egyes pszeudoerdőkhöz), ezért az ilyen irányítás minimum kifoka megegyezik a pszeudoarboricitással, ami pedig legfeljebb a degeneráltság értékével egyezhet meg.; ; ; ; . A gráf vastagsága szintén konstans faktorra található az arboricitástól, így a degeneráltságtól is.
Egy k-degenerált gráf kromatikus száma legfeljebb k + 1; ez a csúcsok számából kiinduló teljes indukcióval egyszerűen belátható, a síkgráfok hatszín-tételével megegyező módon. Mivel a kromatikus szám a maximális elemszámú klikk rendjének felső korlátja, ezért ez utóbbi szintén legfeljebb a degeneráltság plusz egy értéket veheti fel. Egy optimális színezési számú rendezésen mohó színezéssel egy k-degenerált gráf kiszínezhető legfeljebb k + 1 szín használatával.; .
Egy k-szorosan csúcsösszefüggő gráfnak több mint k csúcsa van, és kevesebb mint k csúcs eltávolítása után minden esetben összefüggő marad; vagy ezzel ekvivalens megfogalmazásban, bármely csúcspárjához található k db, a két csúcsot összekötő csúcsdiszjunkt útvonal. Mivel ezek az utak a csúcspár mindkét tagját diszjunkt éleken kell elhagyják, ezért egy k-szorosan csúcsösszefüggő gráf degeneráltsága legalább k. A k-magokhoz hasonló, de csúcsösszefüggőségen alapuló fogalmakat az ismeretségi hálózatok elméletében strukturális kohézió néven vizsgálják..
Ha egy gráf favastagsága vagy útszélessége legfeljebb k, akkor egy olyan merev körű gráf részgráfja, melynek egy perfekt eliminációs rendezésében minden csúcsnak legfeljebb k korábbi szomszédja van. Ezért a degeneráltság legfeljebb a favastagság, illetve legfeljebb az útszélesség értékével egyezhet meg. Léteznek azonban korlátos degeneráltságú, de korlátlan favastagságú gráfok, ilyenek például a rácsgráfok..
A által bizonyított Burr–Erdős-sejtés összeköti G gráf degeneráltságát a G-hez tartozó Ramsey-számmal, ami a legnagyobb n, amire egy n-csúcsú teljes gráf olyan két színnel történő élszínezésének tartalmaznia kell a G egyszínű kópiáját. A sejtés szerint bármely rögzített k értékre a k-degenerált gráfok Ramsey-száma a csúcsok számával lineárisan nő..
Végtelen gráfok Bár általában véges gráfok degeneráltságáról és színezési számáról beszélünk, eredeti motivációja a végtelen gráfok területén volt. Egy G végtelen gráf színezési számát a véges gráfokéhoz hasonlóan lehet definiálni: a legkisebb α kardinális szám, melyre létezik G'' csúcsainak olyan jólrendezése, melyben a csúcsoknak α-nál kevesebb, a rendezésben előttük szereplő szomszédja van. A színezési és kromatikus számok közötti egyenlőtlenség ebben a végtelen esetben is igaznak bizonyult; állítása szerint a cikk megjelentetésének idejében ez már közismert tény volt.
A végtelen hálók véletlen részhalmazainak degeneráltságát bootstrap perkoláció néven vizsgálták.
Jegyzetek
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Fordítás
További információk K-mag dekompozíció gráf-adatfolyam alapján (tanulmány)
Kategória:Gráfinvariánsok Kategória:Gráfalgoritmusok