Grafhomomorfi

Ej att förväxla med grafhomeomorfi.

En grafhomomorfi är inom matematik en strukturbevarande avbildning, en homomorfi, mellan grafer. Mer specifikt avbildar den närliggande noder till närliggande noder.

Definition och begrepp

Givet två grafer $G=(N,B)$ och $G^{\prime }=(N^{\prime },B^{\prime })$ är en avbildning $f:G\to G^{\prime }$ en homomorfi om

$(x,y)\in B\Rightarrow (f(x),f(y))\in B^{\prime }$

dvs, om det finns en båge mellan de två noderna x och y i G ska det finnas en båge mellan $f(x)$ och $f(y)$ i $G^{\prime }$. Om det finns en homomorfi mellan graferna G och $G^{\prime }$ skriver man $G\to G^{\prime }$. Definitionen fungerar även för riktade grafer.

Om det finns en grafhomomorfi $f:G\to H$ sägs G vara H-färgbar. Om det även gäller att det finns en grafhomomorfi $g:H\to G$ sägs graferna G och H vara homomorfiskt ekvivalenta. En homomorfi från G till G kallas för grafendomorfi.

För en homomorfi $f:G\to H$ kallas urbilderna $f^{-1}(y)$ för alla y i H för f:s fibrer. Fibrerna till f bildar en partition av G:s noder, om det inte finns några loopar i H.

Om H är en delgraf till G sägs en homomorfi $f:G\to H$ vara en retraktion om $f(x)=x$ för alla x i H. En graf är en kärna om det inte finns någon retraktion till en äkta delgraf av grafen.

Egenskaper

• En sammansättning av grafhomomorfier är en grafhomomorfi.
• Grafhomomorfier bevarar komponenter.
• Mängden av alla endomorfier till en given graf bildar en monoid.
• En grafhomomorfi som är bijektiv och vars invers också är en homomorfi är en grafisomorfi. Om homomorfin även är en endomorfi sägs den vara en grafautomorfi.
• Varje graf har en kärna som delgraf som är bestämd upp till isomorfi.
• Två grafer är homomorfiskt ekvivalenta om och endast om deras kärnor är isomorfa.

Exempel

Exempel på två färgningar av samma graf. Vänstra bilden kan ses som en homomorfi till $K_2$ och den högra till $K_4$. Noder med samma färg avbildas till samma nod i den kompletta grafen.

En k-graffärgning är en grafhomomorfi $f:G\to K_r$ där $K_r$ är den kompletta grafen med r noder. Om $f:G\to H$ är en homomorfi följer det att det kromatiska talet för G är högst det kromatiska talet för H.

Exempelvis så finns det för varje bipartit graf G en homomorfi $f:G\to K_2$.

Referenser

• Mall:Bokref