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 G=(N,B) och G'=(N',B') är en avbildning f:G \to G' en homomorfi om

(x,y) \in B \Rightarrow (f(x), f(y)) \in B'

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'. Om det finns en homomorfi mellan graferna G och G' skriver man G \to G'. 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[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 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[redigera | redigera wikitext]

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