Degeneration (grafteori) - Degeneracy (graph theory)

En 2-degenererad graf: varje hörn har högst två grannar till vänster, så den högra hörnet av någon subgraf har högst två. Dess 2-kärna, subgrafen som återstår efter att upprepade gånger tagit bort hörn med grad mindre än två, är skuggad.

I grafteori , en k -degenerate graf är en oriktad graf där varje subgraf har en vertex grad som mest k : det vill säga några vertex i subgraf berör k eller färre av subgraf kanter. Den degenerering av ett diagram är det minsta värdet på k för vilket den är k -degenerate. Degenerering av en graf är ett mått på hur gles den är, och är inom en konstant faktor för andra sparsity mått såsom arboricity av en graf.

Degeneration är också känt som k -core -nummer , bredd och koppling , och är i huvudsak samma som färgnummer eller Szekeres -Wilf -nummer (uppkallat efter Szekeres och Wilf  ( 1968 )). k -genererade grafer har också kallats k -induktiva grafer . Degenerationen av en graf kan beräknas i linjär tid av en algoritm som upprepade gånger tar bort minsta graders hörn. De anslutna komponenterna som är kvar efter att alla hörn med grad mindre än k har tagits bort kallas grafens k -kärnor och degenerationen hos en graf är det största värdet k så att den har en k -core.

Exempel

Varje ändlig skog har antingen en isolerad topp (infall utan kanter) eller en bladpunkt (infall till exakt en kant); därför är träd och skogar 1-degenererade grafer. Varje 1-degenererad graf är en skog.

Varje ändlig plan graf har en toppunkt med grad fem eller mindre; Därför är varje plan graf 5-degenererad, och degenerationen för varje plan graf är högst fem. På samma sätt har varje yttre plan graf degenerering högst två, och de apollonska nätverken har degeneration tre.

Den modell Barabási-Albert för generering slumpskalfria nät är parametriseras av ett nummer m , så att varje vertex som läggs till grafen har m tidigare adde hörn. Därav följer att varje undergraf av ett nätverk som bildas på detta sätt har en toppunkt på högst m (den sista topppunkten i subgrafen som har lagts till i grafen) och Barabási – Albert -nätverk är automatiskt m -genererade.

Varje k -regelbunden graf har degeneration exakt  k . Mer starkt är degenerationen av en graf lika med dess maximala toppunktsgrad om och endast om minst en av de anslutna komponenterna i grafen är regelbunden med maximal grad. För alla andra grafer är degenerationen strikt mindre än maxgraden.

Definitioner och ekvivalenser

Färgningsnumret för en graf G definierades av Erdős & Hajnal (1966) som det minst κ för vilket det finns en ordning av hörn för G där varje hörn har färre än κ grannar som är tidigare i ordningen. Det bör skiljas från kromatiska antal av G behövde det minsta antalet färger för att färga hörnen så att inga två angränsande hörn har samma färg; den ordning som bestämmer färgnumret ger en order om att färga hörnen på G med färgnumret, men i allmänhet kan det kromatiska talet vara mindre.

Degenerationen av en graf G definierades av Lick & White (1970) som den minsta k så att varje inducerad subgraf av G innehåller en toppunkt med k eller färre grannar. Definitionen skulle vara densamma om godtyckliga subgrafer är tillåtna istället för inducerade subgrafer, eftersom en icke-inducerad subgraf bara kan ha vertexgrader som är mindre än eller lika med vertex-graderna i subgrafen inducerade av samma vertex-uppsättning.

De två begreppen färgning av nummer och degeneration är likvärdiga: i alla ändliga diagram är degenerationen bara en mindre än färgnumret. För att, om en graf har en beställning med färgning nummer κ sedan i varje subgraf H vertex som tillhör H och ligger sist i beställningen har som mest κ - 1 grannar i H . I den andra riktningen, om G är k -genererat, kan en ordning med färgnummer k  + 1 erhållas genom att upprepade gånger hitta en toppunkt v med högst k grannar, ta bort v från grafen, ordna de återstående hörnen och lägga till v till slutet av beställningen.

En tredje, ekvivalent formulering är att G är k -genererat (eller har färgnummer högst k  + 1) om och endast om kanterna på G kan orienteras för att bilda en riktad acyklisk graf med högst k grader . En sådan orientering kan bildas genom att orientera varje kant mot den tidigare av dess två slutpunkter i ett färgnummer. I den andra riktningen, om en orientering med utgång k ges, kan en ordning med färgnummer k  + 1 erhållas som en topologisk ordning av den resulterande riktade acykliska grafen.

k -Kärnor

En k -poäng i en graf G är en maximalt ansluten subgraf av G där alla hörn har grad åtminstone k . På motsvarande sätt är det en av de anslutna komponenterna i subgrafen till G som bildas genom att upprepade gånger radera alla hörn med en grad mindre än k . Om en icke -tom k -core existerar, så har G uppenbarligen åtminstone k , och degenerationen av G är den största k för vilken G har en k -core.

En toppunkt har likhet om den tillhör en -core men inte till någon -core. ${\ displaystyle u}$ ${\ displaystyle c}$${\ displaystyle c}$${\ displaystyle (c+1)}$

Begreppet k -core introducerades för att studera klusterstrukturen för sociala nätverk och för att beskriva utvecklingen av slumpmässiga grafer . Det har också tillämpats inom bioinformatik , nätverksvisualisering , internetstruktur, spridning av ekonomiska kriser, identifiering av inflytelserika spridare, hjärnbarkstruktur eller motståndskraft för nätverk inom ekologi . Förlängningar av k -core -strukturer i viktade nätverk har också utvecklats. En undersökning av ämnet, som täcker huvudbegreppen, viktiga algoritmiska tekniker samt vissa applikationsdomäner, kan hittas i Malliaros et al. (2019) .

Bootstrap -perkolering är en slumpmässig process som studeras som en epidemimodell och som en modell för feltolerans för distribuerad dator . Den består av att välja en slumpmässig delmängd av aktiva celler från ett galler eller annat utrymme och sedan överväga k -poängen för den inducerade delgrafen för denna delmängd. I k-core- eller bootstrap-perkolering på svagt sammankopplade nätverk kan sammankopplingarna betraktas som ett externt fält vid övergången.

Algoritmer

Som Matula & Beck (1983) beskriver är det möjligt att hitta en toppunktsordning av ett ändligt diagram G som optimerar färgningens antal för ordningen, i linjär tid , genom att använda en skopkö för att upprepade gånger hitta och ta bort toppunkten i minsta grad . Degenerationen är då den högsta graden av någon toppunkt i det ögonblick den tas bort. Låt n antalet noder i diagrammet.

Mer detaljerat fortsätter algoritmen enligt följande:

• Initiera en utgångslista L .
• Beräkna ett antal d _v för varje vertex v i G , antalet grannar till v som inte redan är i L . Ursprungligen är dessa siffror bara hörnens grader.
• Initiera en array D så att D [ i ] innehåller en lista över hörnen v som inte redan finns i L för vilka d _v  =  i .
• Initiera k till 0.
• Upprepa n gånger:
  • Skanna matriscellerna D [0], D [1], ... tills du hittar ett i för vilket D [ i ] inte är fritt.
  • Ställ in k till max ( k , i )
  • Välj en toppunkt v från D [ i ]. Lägg till v i början av L och ta bort det från D [ i ].
  • För varje granne w av v som inte redan finns i L , subtrahera en från d _w och flytta w till cellen D som motsvarar det nya värdet av d _w .

I slutet av algoritmen innehåller k degenerationen av G och L innehåller en lista med hörn i en optimal ordning för färgnumret. De I- -kärnornas sammansättning av G är prefixen av L bestående av hörnen lagts till L efter k först tar ett värde större än eller lika med  i .

Initiering av variablerna L , d _v , D och k kan enkelt göras i linjär tid. Att hitta varje successivt borttagen toppunkt v och justera cellerna i D som innehåller grannarna till v tar tid som är proportionellt mot värdet av d _v vid det steget; men summan av dessa värden är antalet kanter på grafen (varje kant bidrar till termen i summan för den senare av dess två slutpunkter) så den totala tiden är linjär.

Relation till andra grafparametrar

Om en graf G är orienterad acykliskt med utgång k , kan dess kanter delas upp i k -skogar genom att välja en skog för varje utgående kant av varje nod. Således är arboriciteten hos G högst lika med dess degenerering. I den andra riktningen har en n -vertexgraf som kan delas upp i k -skogar högst k ( n  -1) kanter och har därför en toppunkt på högst 2 k -1 -alltså är degenerationen mindre än dubbelt så stor arboricitet. Man kan också beräkna i polynomtid en orientering av en graf som minimerar utgången men inte krävs för att vara acyklisk. Kanterna av en graf med en sådan orientering kan fördelas på samma sätt in i k pseudoforests , och omvänt en delning av en diagrammets kanter till k pseudoforests leder till en outdegree- k orientering (genom att välja en outdegree-en orientering för varje pseudoforest) , så minsta graden av en sådan orientering är pseudoarboriciteten , som återigen högst är lika med degenerationen. Den tjocklek är också inom en konstant faktor av arboricity, och därför också av degenerationen.

En k -genererad graf har högst kromatiskt tal k  + 1; detta bevisas genom en enkel induktion av antalet hörn som är exakt som beviset på sexfärgs satsen för plana grafer. Eftersom kromatiskt tal är en övre gräns i storleksordningen för den maximala klicken , är den senare invarianten också högst degeneration plus en. Genom användning av en girig färgande algoritmen på en beställning med optimal färgnummer, kan man plotta färg en k -degenerate graf med användning högst k  + 1 färger.

En k -vertex-ansluten graf är en graf som inte kan delas upp i mer än en komponent genom borttagning av färre än k- hörn, eller motsvarande en graf där varje par hörnpar kan anslutas med k- vertex-disjoint-banor. Eftersom dessa vägar måste lämna parets två hörn via osammanhängande kanter måste en k -vertex -ansluten graf ha degenerering åtminstone k . Begrepp relaterade till k -kärnor men baserade på vertex -anslutning har studerats i sociala nätverksteorin under namnet strukturell sammanhållning .

Om en graf har trebredd eller banbredd som högst k , så är det en undergraf av en ackordgraf som har en perfekt elimineringsordning där varje toppunkt har högst k tidigare grannar. Därför är degenerationen högst lika med trädbredden och högst lika med banbredden. Det finns dock grafer med begränsad degeneration och obegränsad trädbredd, till exempel rutdiagram .

Den Burr-Erdős gissningar hänför degenereringen av en graf G till Ramsey antal av G , det minst n så att varje två-kant-färgning av en n -vertex komplett graf måste innehålla en monokromatisk kopia av G . Specifikt är gissningen att för alla fasta värden för k växer Ramsey -antalet k -genererade grafer linjärt i antalet hörn i graferna. Gissningen bevisades av Lee (2017) .

Oändliga grafer

Även om begrepp om degeneration och färgnummer ofta betraktas i samband med ändliga grafer, var den ursprungliga motivationen för Erdős & Hajnal (1966) teorin om oändliga grafer. För en oändlig graf G , kan man definiera färgnumret analogt med definitionen för ändliga grafer, som det minsta kardinalnumret α så att det finns en välordnad ordning av hörnen för G där varje hörn har färre än α-grannar som är tidigare i beställningen. Ojämlikheten mellan färgning och kromatiska siffror gäller också i denna oändliga miljö; Erdős & Hajnal (1966) konstaterar att det redan vid tidpunkten för publicering av deras tidning var välkänt.

Nedbrytningen av slumpmässiga delmängder av oändliga gitter har studerats under namnet bootstrap percolation .

Se även

• Grafteori
• Nätverksvetenskap
• Perkolationsteori
• Kär -periferistruktur
• Cerecedas gissning

Anteckningar

Referenser