Grafhomomorfi

Från Wikipedia
Hoppa till: navigering, sök
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[redigera | redigera wikitext]

Givet två grafer och är en avbildning en homomorfi om

dvs, om det finns en båge mellan de två noderna x och y i G ska det finnas en båge mellan och i . Om det finns en homomorfi mellan graferna G och skriver man . Definitionen fungerar även för riktade grafer.

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

För en homomorfi kallas urbilderna 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 vara en retraktion om 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[redigera | redigera wikitext]

  • 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[redigera | redigera wikitext]

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

En k-graffärgning är en grafhomomorfi där är den kompletta grafen med r noder. Om ä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 .

Referenser[redigera | redigera wikitext]

  • Godsil, Chris; Gordon Royle (2001). Algebraic Graph Theory. Springer Verlag. ISBN 0-387-95241-1