Degenerace (teorie grafů) - Degeneracy (graph theory)

"K-core" přeadresuje tady. The jádro grafu je jiný koncept.
2-degenerovaný graf: každý vrchol má nejvýše dva sousedy nalevo, takže pravý vrchol jakéhokoli podgrafu má stupeň nanejvýš dva. Jeho 2-jádro, podgraf zbývající po opakovaném mazání vrcholů stupňů menších než dva, je zastíněno.

v teorie grafů, a k-degenerovat graf je neorientovaný graf ve kterém má každý podgraf vrchol stupeň nejvíce k: to znamená, že se nějaký vrchol v podgrafu dotýká k nebo méně okrajů podgrafu. The zvrhlost grafu je nejmenší hodnota k pro které to je k-degenerovat. Degenerace grafu je měřítkem toho, jak řídký to je a je v neustálém faktoru jiných měřítek sparsity takový jako arboricita grafu.

Degenerace je také známá jako k- počet čísel,[1] šířka,[2] a vazba,[3] a je v podstatě stejný jako číslo zbarvení[4] nebo Číslo Szekeres-Wilf (pojmenoval podle Szekeres a Wilf  (1968 )). k- byly také nazývány generované grafy k-indukční grafy.[5] Degeneraci grafu lze vypočítat lineární čas algoritmem, který opakovaně odstraňuje vrcholy minimálního stupně.[6] The připojené komponenty které zůstanou po všech vrcholech stupňů menší než k které byly odstraněny, se nazývají k-jádra grafu a degenerace grafu je největší hodnota k tak, že má k-jádro.

Příklady

Každý konečný les má buď izolovaný vrchol (dopad na žádné hrany) nebo listový vrchol (dopad na přesně jednu hranu); stromy a lesy jsou proto 1 zvrhlé grafy. Každý 1 zdegenerovaný graf je les.

Každý konečný rovinný graf má vrchol stupně pět nebo méně; proto je každý rovinný graf 5 degenerovaný a degenerace jakéhokoli rovinného grafu je nejvýše pět. Podobně každý vnější rovinný graf má degeneraci nanejvýš dva,[7] a Apollonské sítě mít degeneraci tři.

The Barabási – Albertův model pro generování náhodný sítě bez měřítka[8] je parametrizován číslem m tak, že každý vrchol, který je přidán do grafu, má m dříve přidané vrcholy. Z toho vyplývá, že jakýkoli podgraf takto vytvořené sítě má maximálně vrchol stupně m (poslední vrchol v podgrafu, který byl přidán do grafu) a sítě Barabási – Albert jsou automaticky m-degenerovat.

Každý k-pravidelný graf má degeneraci přesněk. Silněji se degenerace grafu rovná jeho maximálnímu stupni vrcholů právě tehdy, když alespoň jeden z připojené komponenty grafu je pravidelný maximálního stupně. U všech ostatních grafů je degenerace přísně menší než maximální stupeň.[9]

Definice a rovnocennosti

Číslo zbarvení grafu G byl definován Erdős & Hajnal (1966) být nejméně κ, pro které existuje uspořádání vrcholů G ve kterém má každý vrchol méně než κ sousedů, kteří jsou dříve v pořadí. Je třeba jej odlišit od chromatické číslo z G, minimální počet barev potřebných k vybarvení vrcholů tak, aby žádné dva sousední vrcholy neměly stejnou barvu; pořadí, které určuje číslo zbarvení, poskytuje příkaz k vybarvení vrcholů G číslem zbarvení, ale obecně může být chromatické číslo menší.

Degenerace grafu G byl definován Lick & White (1970) jako nejméně k takové, že každý indukovaný podgraf z G obsahuje vrchol s k nebo méně sousedů. Definice by byla stejná, pokud jsou namísto indukovaných podgrafů povoleny libovolné podgrafy, protože neindukovaný podgraf může mít pouze stupně vrcholů, které jsou menší nebo stejné jako stupně vrcholů v podgrafu indukované stejnou sadou vrcholů.

Dva koncepty čísla zbarvení a degenerace jsou ekvivalentní: v každém konečném grafu je degenerace jen o jeden menší než číslo zbarvení.[10] Pokud má graf uspořádání s barevným číslem κ, pak v každém podgrafu H vrchol, ke kterému patří H a je poslední v pořadí, má maximálně κ - 1 sousedů v H. V opačném směru, pokud G je k-generovat, pak objednávka s číslem zbarvení k + 1 lze získat opakovaným nalezením vrcholu proti maximálně k sousedé, stěhování proti z grafu, seřazení zbývajících vrcholů a přidání proti do konce objednávky.

Třetí, ekvivalentní formulace je to G je k-degenerovat (nebo má maximálně číslo zbarvení k + 1) právě tehdy, pokud jsou hrany G lze orientovat do formy a směrovaný acyklický graf s překonat nejvíce k.[11] Taková orientace může být vytvořena orientací každého okraje směrem k dřívějšímu z jeho dvou koncových bodů v pořadí barevného čísla. V opačném směru, pokud je orientace s převahou k je uvedena objednávka s číslem zbarvení k + 1 lze získat jako a topologické uspořádání výsledného směrovaného acyklického grafu.

k-Jádra

A k- skóre grafu G je maximální připojený podgraf G ve kterém mají všechny vrcholy alespoň stupeň k. Ekvivalentně je to jeden z připojené komponenty podgrafu G vytvořeno opakovaným mazáním všech vrcholů stupňů menších než k. Pokud není prázdný k-core tedy existuje, jasně, G má alespoň degeneraci ka degenerace G je největší k pro který G má k-jádro.

Vrchol má hrubost pokud patří k a- skóre, ale ne žádnému -jádro.

Koncept a k-core bylo zavedeno ke studiu shlukovací struktury sociální sítě[12] a popsat vývoj náhodné grafy.[13] Bylo také použito v bioinformatika,[14] vizualizace sítě,[15] Struktura internetu,[16] šíření hospodářských krizí,[17] identifikace vlivných rozmetadel,[18] struktura mozkové kůry[19] nebo odolnost sítí v ekologie.[20] Rozšíření k- byly vyvinuty také jádrové struktury ve vážených sítích.[21] Přehled tématu, který zahrnuje hlavní koncepty, důležité algoritmické techniky i některé aplikační domény, lze najít v Malliaros a kol. (2019).

Perkolace bootstrapu je náhodný proces studovaný jako model epidemie[22] a jako model pro odolnost proti chybám pro distribuované výpočty.[23] Skládá se z výběru náhodné podmnožiny aktivních buněk z a mříž nebo jiný prostor, a poté zvážit k- jádro z indukovaný podgraf této podskupiny.[24] V perkolaci k-core nebo bootstrap na slabě propojených sítích lze propojení považovat za externí pole při přechodu.[25]

Algoritmy

Tak jako Matula & Beck (1983) popsat, je možné najít vrcholové uspořádání konečného grafu G který optimalizuje číslo zbarvení objednávky v lineární čas, pomocí a fronta na kbelík opakovaně najít a odstranit vrchol nejmenšího stupně. Degenerace je pak nejvyšším stupněm jakéhokoli vrcholu v okamžiku, kdy je odstraněna. Nechat n počet uzlů v grafu.

Podrobněji algoritmus postupuje následovně:

  • Inicializovat výstupní seznam L.
  • Vypočítat číslo dproti pro každý vrchol proti v G, počet sousedů z proti které ještě nejsou v L. Zpočátku jsou tato čísla pouze stupně vrcholů.
  • Inicializovat pole D takhle D[i] obsahuje seznam vrcholů proti které ještě nejsou v L pro který dproti = i.
  • Inicializovat k na 0.
  • Opakovat n časy:
    • Naskenujte buňky pole D[0], D[1], ... dokud nenajdete i pro který D[i] je neprázdné.
    • Soubor k na maximum (k,i)
    • Vyberte vrchol proti z D[i]. Přidat proti na začátek L a odstranit jej z D[i].
    • Pro každého souseda w z proti ještě ne v L, odečíst jeden z dw a pohybovat se w do buňky D odpovídající nové hodnotě dw.

Na konci algoritmu k obsahuje degeneraci G a L obsahuje seznam vrcholů v optimálním pořadí pro číslo zbarvení. The i-jádra G jsou předpony L skládající se z vrcholů přidaných k L po k first takes a value greater than or equal toi.

Inicializace proměnných L, dproti, D, a k lze snadno provést v lineárním čase. Nalezení každého postupně odstraněného vrcholu proti a nastavení buněk D obsahující sousedy proti čas potřebný k hodnotě dproti v tomto kroku; ale součet těchto hodnot je počet okrajů grafu (každá hrana přispívá k termínu v součtu pro pozdější ze svých dvou koncových bodů), takže celkový čas je lineární.

Vztah k dalším parametrům grafu

Pokud graf G je orientován acyklicky s vyšším stupněm k, pak mohou být jeho hrany rozděleny na k lesy výběrem jedné doménové struktury pro každou odchozí hranu každého uzlu. To znamená, že arboricita z G se nanejvýš rovná její degeneraci. V opačném směru, an n-vertexový graf, do kterého lze rozdělit k lesy mají nanejvýš k(n - 1) hrany, a proto má vrchol stupně nejvýše 2k- 1 - tedy degenerace je menší než dvojnásobek arboricity. Jeden může také vypočítat v polynomiálním čase orientaci grafu, která minimalizuje překonání, ale nemusí být acyklická. Okraje grafu s takovou orientací lze rozdělit stejným způsobem na k pseudolesy a naopak jakýkoli oddíl okrajů grafu do k pseud lesy vedou k překročeník orientace (výběrem orientace outgree-1 pro každý pseudoforest), takže minimální outgree takové orientace je pseudoarboricita, což se opět nanejvýš rovná degeneraci.[26] The tloušťka je také v neustálém faktoru arboricity, a tedy i degenerace.[27]

A k-degenerovaný graf má nanejvýš chromatické číslo k + 1; to dokazuje jednoduchá indukce počtu vrcholů, která je přesně jako důkaz šestibarevné věty pro planární grafy. Protože chromatické číslo je horní hranicí řádu maximální klika, druhý invariant je také nanejvýš degenerací plus jedna. Použitím a chamtivé zbarvení algoritmus na objednávce s optimálním číslem vybarvení, jeden může barva grafu A k-degenerovat graf pomocí maximálně k + 1 barvy.[28]

A kgraf spojený s vrcholem je graf, který nelze rozdělit na více než jednu komponentu odstraněním méně než k vrcholy, nebo ekvivalentně graf, ve kterém může být každá dvojice vrcholů spojena k cesty vrchol-disjunkt. Protože tyto cesty musí opustit dva vrcholy páru přes disjunktní hrany, a kgraf spojený s vrcholem musí mít alespoň degeneraci k. Pojmy související s k-jádra, ale na základě konektivity vrcholů byla studována v teorii sociálních sítí pod jménem strukturální soudržnost.[29]

Pokud má graf šířka stromu nebo šířka cesty nejvíce k, pak se jedná o podgraf a chordální graf který má perfektní objednávka eliminace ve kterém má každý vrchol nanejvýš k dřívější sousedé. Degenerace se proto nanejvýš rovná šířce stromu a nanejvýš rovná šířce cesty. Existují však grafy s omezenou degenerací a neomezenou šířkou stromu, například mřížkové grafy.[30]

The Burr – Erdőův dohad souvisí s degenerací grafu G do Ramseyovo číslo z G, nejméně n tak, že jakékoli dvoubarevné zbarvení an n-vrchol kompletní graf musí obsahovat jednobarevnou kopii G. Konkrétně jde o domněnku pro jakoukoli pevnou hodnotu k, Ramseyovo číslo k-degenerate grafy rostou lineárně v počtu vrcholů grafů.[31] Domněnku prokázal Lee (2017).

Nekonečné grafy

Ačkoli pojmy degenerace a zbarvení čísla jsou často zvažovány v kontextu konečných grafů, původní motivace pro Erdős & Hajnal (1966) byla teorie nekonečných grafů. Pro nekonečný graf Glze definovat číslo zbarvení analogicky k definici konečných grafů jako nejmenší základní číslovka α takové, že existuje a dobře objednávající vrcholů G ve kterém má každý vrchol méně než α sousedů, kteří jsou dříve v pořadí. Nerovnost mezi barvením a chromatickými čísly platí i v tomto nekonečném prostředí; Erdős & Hajnal (1966) uvádějí, že v době zveřejnění jejich příspěvku to bylo již dobře známé.

Degenerace náhodných podmnožin nekonečna mříže byl studován pod jménem bootstrap perkolace.

Viz také

Poznámky

  1. ^ 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: „Je snadné vidět, že col (G) = Δ (G) + 1 právě tehdy G má Δ (G) -regular component. "V zápisu používaném Jensenem a Toftem, col (G) je degenerace plus jedna a Δ (G) je maximální stupeň vrcholu.
  10. ^ Matula (1968); Lick & White (1970), Tvrzení 1, strana 1084.
  11. ^ Chrobak & Eppstein (1991).
  12. ^ Seidman (1983).
  13. ^ Bollobás (1984); Luczak (1991);Dorogovtsev, Goltsev & Mendes (2006).
  14. ^ Bader & Hogue (2003); Altaf-Ul-Amin a kol. (2003); Wuchty & Almaas (2005).
  15. ^ Gaertler & Patrignani (2004); Alvarez-Hamelin a kol. (2006).
  16. ^ Carmi a kol. (2007).
  17. ^ Garas a kol. (2010).
  18. ^ Kitsak a kol. (2010).
  19. ^ Lahav a kol. (2016).
  20. ^ Garcia-Algarra a kol. (2017).
  21. ^ Garas, Schweitzer a Havlin (2012).
  22. ^ Balogh a kol. (2012).
  23. ^ Kirkpatrick a kol. (2002).
  24. ^ Adler (1991).
  25. ^ Gross, B; Sanhedrai, H; Shekhtman, L; Havlin, S (2020). "Propojení mezi sítěmi fungují jako externí pole v perkolačních přechodech prvního řádu". Fyzický přehled E. 101 (2). arXiv:1905.07009. doi:10.1103 / PhysRevE.101.022316.
  26. ^ Chrobak & Eppstein (1991); Gabow & Westermann (1992); Venkateswaran (2004); Asahiro a kol. (2006); Kowalik (2006).
  27. ^ Dean, Hutchinson a Scheinerman (1991).
  28. ^ Erdős & Hajnal (1966); Szekeres & Wilf (1968).
  29. ^ Moody & White (2003).
  30. ^ Robertson & Seymour (1984).
  31. ^ Burr & Erdős (1975).

Reference