Grafhomologi

I algebraisk topologi och grafteori beskriver grafhomologi homologigrupperna i en graf , där grafen betraktas som ett topologiskt utrymme . Det formaliserar idén om antalet "hål" i grafen. Det är ett specialfall av en enkel homologi , eftersom en graf är ett specialfall av ett förenklat komplex. Eftersom en finit graf är ett 1-komplex (dvs. dess "ytor" är hörnen - som är 0-dimensionella och kanterna - som är 1-dimensionella), är de enda icke-triviala homologigrupperna den 0:e gruppen och den 1:e gruppen.

Den 1:a homologigruppen

Den allmänna formeln för den första homologigruppen i ett topologiskt utrymme X är:

$$H_{1}(X):=\ker \partial _{1}{\big /}\operatörsnamn {im} \partial _{ 2}$$

Exemplet nedan förklarar dessa symboler och begrepp i detalj på en graf.

Exempel

Låt X vara en riktad graf med 3 hörn {x,y,z} och 4 kanter {a: x→y, b: y→z, c: z→x, d: z→x}. Den har flera cykler :

• En cykel representeras av slingan a+b+c. Här representerar plustecknet det faktum att alla kanter färdas i samma riktning. Eftersom additionsoperationen är kommutativ representerar +-tecknet det faktum att slingorna a+b+c, b+c+a och c+a+b alla representerar samma cykel.
• En andra cykel representeras av slingan a+b+d.
• En tredje cykel representeras av slingan c−d. Här representerar minustecknet det faktum att kanten d förflyttas bakåt.

Om vi ​​skär planet längs slingan a+b+d, och sedan skär vid c och "limmar" vid d, får vi ett snitt längs slingan a+b+c. Detta kan representeras av följande relation: (a+b+d) + (cd) = (a+b+c). För att formellt definiera denna relation definierar vi följande kommutativa grupper:

• ₀₀ C är den fria abelska gruppen som genereras av uppsättningen av hörn {x,y,z}. Varje element i C kallas en 0-dimensionell kedja .
• C1 är den fria abelska gruppen som genereras av uppsättningen riktade kanter {a,b,c,d} _. Varje element i C ₁ kallas en 1-dimensionell kedja . De tre cyklerna som nämns ovan är 1-dimensionella kedjor, och förhållandet (a+b+d) + (cd) = (a+b+c) gäller faktiskt i gruppen C ₁ .

₀₀₀ De flesta element i C ₁ är inte cykler, till exempel a+b, 2a+5b-c, etc. är inte cykler. För att formellt definiera en cykel definierar vi först gränser . Gränsen för en kant betecknas med $\partial _{1}$ och definieras som dess mål minus dess källa, så $\partial _{1}(a)=yx,~\partial _{1}(b)=zy,~\partial _{1}(c)=\partial _{1}(d)=xz .$ Så $\partial _{1}$ är en mappning från gruppen C ₁ till gruppen C . Eftersom a,b,c,d är generatorerna av C _{1 sträcker sig} denna $\partial _{1}$ naturligt till en grupphomomorfism från C ₁ till C . I denna homomorfism, $\partial _{1}(a+b+c)=\partial _{1}(a)+\partial _{1}(b)+\partial _{1}(c)=(yx) +(zy)+(xz)=0$ . På liknande sätt mappar ${\displaystyle \partial _{1}} vilken cykel som helst i$ C ₁ till nollelementet i C . Med andra ord, uppsättningen cykler i C ₁ genererar nollutrymmet (kärnan) för $\partial _{1}$ . I detta fall har kärnan i $\partial _{1}$ två generatorer: en motsvarar a+b+c och den andra till a+b+d (den tredje cykeln, cd, är en linjär kombination av de två första). Så ker $\partial _{1}$ är isomorf till Z ² .

I ett allmänt topologiskt utrymme skulle vi definiera högre dimensionella kedjor. I synnerhet C ₂ vara den fria abelska gruppen på uppsättningen av 2-dimensionella objekt. Men i en graf finns inga sådana objekt, så C ₂ är en trivial grupp. Därför är bilden av den andra gränsoperatorn, $\partial _{2}$ också trivial. Därför:

$$H_{1}(X)=\ker \partial _{1}{\big /}\operatörsnamn { im} \partial _{2}\cong \mathbb {Z} ^{2}/\mathbb {Z} ^{0}=\mathbb {Z} ^{2}$$

Detta motsvarar det intuitiva faktum att grafen har två "hål". Exponenten är antalet hål.

Allmänt fall

Ovanstående exempel kan generaliseras till en godtyckligt kopplad graf G = ( V , E ). Låt T vara ett spännande träd av G . Varje kant i E \ T motsvarar en cykel; dessa är exakt de linjärt oberoende cyklerna. Därför är den första homologigruppen H ₁ i en graf den fria abelska gruppen med | E \ T | generatorer. Detta nummer är lika med | E |-| V |+1; så:

$$H_{1}(X)\cong \mathbb {Z} ^{|E|-|V|+1}.$$

I en frånkopplad graf, när C är uppsättningen av anslutna komponenter, visar en liknande beräkning:

$$H_{1}(X)\cong \mathbb {Z} ^{|E|-|V|+|C|}.$$

I synnerhet är den första gruppen trivial om och endast om X är en skog .

Den 0:e homologigruppen

Den allmänna formeln för den 0:e homologigruppen i ett topologiskt utrymme X är:

$$H_{0}(X):=\ker \partial _{0}{\big /}\operatörsnamn {im} \partial _{1}$$

Exempel

₀₀ Vi återgår till grafen med 3 hörn {x,y,z} och 4 kanter {a: x→y, b: y→z, c: z→x, d: z→x}. Kom ihåg att gruppen C genereras av uppsättningen av hörn. Eftersom det inte finns några (−1)-dimensionella element är gruppen C ₋₁ trivial, och därför är hela gruppen C en kärna av motsvarande gränsoperator: $\ker \partial _{0 }=C_{0}$ = den fria abelska gruppen genererad av {x,y,z}.

Bilden av $\partial _{1}$ innehåller ett element för varje par av hörn som är gränser för en kant, dvs den genereras av skillnaderna {y−x, z−y, x−z }. För att beräkna kvotgruppen är det bekvämt att tänka på alla element i $\operatorname {im} \partial _{1}$ som "motsvarande noll". Det betyder att x, y och z är ekvivalenta - de är i samma ekvivalensklass för kvoten. Med andra ord, $H_{0}(X)$ genereras av ett enda element (vilket hörn som helst kan generera det). Så det är isomorft till Z .

Allmänt fall

Ovanstående exempel kan generaliseras till vilken ansluten graf som helst . Med utgångspunkt från vilken vertex som helst är det möjligt att komma till vilken annan vertex som helst genom att lägga till ett eller flera uttryck som motsvarar kanter (t.ex. med början från x kan man komma till z genom att lägga till yx och zy). Eftersom elementen i $\operatorname {im} \partial _{1}$ alla är ekvivalenta med noll, betyder det att alla hörn i grafen är i en enda ekvivalensklass, och därför $H_{0}(X)$ är isomorf till Z .

I allmänhet kan grafen ha flera sammankopplade komponenter . Låt C vara mängden komponenter. Då är varje ansluten komponent en ekvivalensklass i kvotgruppen. Därför:

$$H_{0}(X)\cong \mathbb {Z} ^{|C|}.$$

Den kan genereras av vilken | C |-tuppel av hörn, en från varje komponent.

Minskad homologi

Ofta är det bekvämt att anta att den 0:e homologin för en sammankopplad graf är trivial (så att om grafen innehåller en enda punkt är alla dess homologier triviala). Detta leder till definitionen av den reducerade homologin . För en graf är den reducerade 0:e homologin:

$${\tilde {H_{0}}}(X)\cong \mathbb {Z} ^{|C|-1}.$$

Denna "reduktion" påverkar endast den 0:e homologin; de reducerade homologierna med högre dimensioner är lika med standardhomologierna.

Homologier med högre dimensioner

En graf har bara hörn (0-dimensionella element) och kanter (1-dimensionella element). Vi kan generalisera grafen till ett abstrakt förenklat komplex genom att lägga till element av en högre dimension. Sedan generaliseras begreppet grafhomologi av begreppet enkel homologi .

Exempel

I exemplet ovan kan vi lägga till en tvådimensionell "cell" innesluten mellan kanterna c och d; låt oss kalla det A och anta att det är orienterat medurs. Definiera C ₂ som den fria abelska gruppen genererad av uppsättningen av tvådimensionella celler, som i detta fall är en singelton {A}. Varje element i C ₂ kallas en 2-dimensionell kedja .

₀ Precis som gränsoperatorn från C ₁ till C , som vi betecknar med ${\displaystyle \partial _{1}} ,$ finns det en gränsoperator från C ₂ till C ₁ , som vi betecknar med $\ partiell _{2}$ . Speciellt är gränsen för den 2-dimensionella cellen A de 1-dimensionella kanterna c och d, där c är i "korrekt" orientering och d är i en "omvänd" orientering; därför: $\partial _{2}(A)=cd$ . Sekvensen av kedjor och gränsoperatorer kan presenteras enligt följande:

$$C_{2}\xrightarrow {\partial _{2}} C_{1}\xrightarrow {\partial _{1}} C_{0}$$

Tillägget av den 2-dimensionella cellen A innebär att dess gräns, cd, inte längre representerar ett hål (den är homotopisk till en enda punkt). Därför har gruppen av "hål" nu en enda generator, nämligen a+b+c (den är homotopisk till a+b+d). Den första homologigruppen definieras nu som kvotgruppen :

$$H_{1}(X):=\ker \partial _{1}{\big /}\operatörsnamn {im} \partial _{ 2}$$

Här är $\ker \partial _{1}$ gruppen av 1-dimensionella cykler, som är isomorf till Z ² , och $\operatorname {im} \partial _ {2}$ är gruppen av 1-dimensionella cykler som är gränser för 2-dimensionella celler, som är isomorf till Z . Följaktligen är deras kvot H ₁ isomorf till Z . Detta motsvarar det faktum att X nu har ett enda hål. Tidigare. bilden av $\partial _{2}$ var trivialgruppen , så kvoten var lika med $\ker \partial _{1}$ . Antag nu att vi lägger till ytterligare en orienterad 2-dimensionell cell B mellan kanterna c och d, så att $\partial _{2}(B)=\ partiell _{2}(A)=cd$ . Nu C ₂ den fria abelska gruppen genererad av {A,B}. Detta ändrar inte H ₁ - det är fortfarande isomorft till Z (X har fortfarande ett enda 1-dimensionellt hål). Men nu C ₂ den tvådimensionella cykeln AB, så $\partial _{2}$ har en icke-trivial kärna. Denna cykel genererar den andra homologigruppen, motsvarande det faktum att det finns ett enda tvådimensionellt hål:

$$H_{2}(X):=\ker \partial _{2}\cong \mathbb {Z}$$

Vi kan fortsätta och lägga till en 3-cell - ett solidt 3-dimensionellt objekt (kallat C) avgränsat av A och B. Definiera C ₃ som den fria abelska gruppen genererad av {C}, och gränsoperatorn $\partial _{3}:C_{3}\to C_{2}$ . Vi kan orientera C så att $\partial _{3}(C)=AB$ ; Observera att gränsen för C är en cykel i C ₂ . Nu är den andra homologigruppen:

$$H_{2}(X):=\ker \partial _{2}{\big /}\operatörsnamn {im} \partial _ {3}\cong {0}$$

motsvarande att det inte finns några tvådimensionella hål (C "fyller hålet" mellan A och B).

Allmänt fall

I allmänhet kan man definiera kedjor av vilken dimension som helst. Om den maximala dimensionen för en kedja är k , får vi följande sekvens av grupper:

$$C_{k}\xrightarrow {\partial _{k}} C_{k-1}\cdots C_{1}\xrightarrow {\partial _{1}} C_{0}$$

Det kan bevisas att varje gräns för en ( k +1)-dimensionell cell är en k -dimensionell cykel. Med andra ord, för alla k , $\operatorname {im} \partial _{k+1}$ (gruppen av gränser för k +1 element) ingår i ${ \displaystyle \ker \partial _{k}}$ (gruppen av k -dimensionella cykler). Därför är kvoten ${\displaystyle \ker \partial _{k}{\big /}\operatörsnamn {im} \partial _{k+1}} väldefinierad$ , och den definieras som den k -th homologigruppen:

$$H_{k}(X):=\ker \partial _{k}{\big /}\operatörsnamn {im} \partial _{k+1}$$