Degeneráltság (gráfelmélet)

A Wikipédiából, a szabad enciklopédiából
A „k-mag” ide irányít át – nem tévesztendő össze egy gráf magjával.
Egy 2-degenerált gráf: minden csúcsnak legfeljebb kettő, tőle balra eső szomszédja van, tehát bármely részgráf jobbszélső csúcsának fokszáma legfeljebb kettő lehet. A kettőnél kisebb fokszámú csúcsok ismételt törlésével kapott 2-mag az ábrán színezve látható.

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),[1] szélesség (width)[2] és kapcsoltság (linkage),[3] lényegét tekintve pedig megegyezik a színezési számmal (coloring number)[4] vagy Szekeres–Wilf-számmal (Szekeres and Wilf (1968) után). A k-degenerált gráfokat nevezik k-induktív gráfoknak (k-inductive graphs) is.[5] 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.[6] 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[szerkesztés]

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ő,[7] az Apollóniusz-hálózatoké pedig három.

A véletlen skálafüggetlen hálózatok Barabási–Albert-modelljének[8] 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.[9]

Definíciók és ekvivalenciák[szerkesztés]

A G gráf (Erdős & Hajnal 1966) á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 (Lick & White 1970) ú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.[10] 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.[11] 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[szerkesztés]

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[12] és véletlen gráfok evolúciójának leírására vezették be;[13] léteznek alkalmazásai a bioinformatika[1][14] és különböző hálózatok vizuális megjelenítése területén.[15] 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[szerkesztés]

(Matula & Beck 1983) 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 (wd) 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[0], D[1], ... 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[szerkesztés]

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.[16] A gráf vastagsága szintén konstans faktorra található az arboricitástól, így a degeneráltságtól is.[17]

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.[18]

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.[19]

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.[20]

A (Lee 2017) á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ő.[21]

Végtelen gráfok[szerkesztés]

Bár általában véges gráfok degeneráltságáról és színezési számáról beszélünk, (Erdős & Hajnal 1966) 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; (Erdős & Hajnal 1966) á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[szerkesztés]

  1. ↑ a b (Bader & Hogue 2003).
  2. ↑ (Freuder 1982).
  3. ↑ (Kirousis & Thilikos 1996).
  4. ↑ (Erdős & Hajnal 1966).
  5. ↑ (Irani 1994).
  6. ↑ (Matula & Beck 1983)
  7. ↑ (Lick & White 1970).
  8. ↑ (Barabási & Albert 1999).
  9. ↑ (Jensen & Toft 2011), 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.
  10. ↑ (Matula 1968); (Lick & White 1970), Proposition 1, page 1084.
  11. ↑ (Chrobak & Eppstein 1991).
  12. ↑ (Seidman 1983).
  13. ↑ (Bollobás 1984); (Łuczak 1991);(Dorogovtsev, Goltsev & Mendes 2006).
  14. ↑ (Altaf-Ul-Amin et al. 2003); (Wuchty & Almaas 2005).
  15. ↑ (Gaertler & Patrignani 2004); (Alvarez-Hamelin et al. 2005).
  16. ↑ (Chrobak & Eppstein 1991); (Gabow & Westermann 1992); (Venkateswaran 2004); (Asahiro et al. 2006); (Kowalik 2006).
  17. ↑ Dean, Hutchinson & Scheinerman (1991).
  18. ↑ (Erdős & Hajnal 1966); (Szekeres & Wilf 1968).
  19. ↑ (Moody & White 2003).
  20. ↑ (Robertson & Seymour 1984).
  21. ↑ (Burr & Erdős 1975).

Fordítás[szerkesztés]

  • Ez a szócikk részben vagy egészben a Degeneracy (graph theory) című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk[szerkesztés]

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Degeneráltság_(gráfelmélet)&oldid=26538883”