Grafhomomorfi

Från Wikipedia
Hoppa till navigering Hoppa till 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