En grafmorfisme eller grafhomomorfisme er en applikation mellem to grafer ( orienteret eller ikke orienteret ), der respekterer strukturen af disse grafer. Med andre ord skal billedet af en graf i en graf respektere de nærhedsforhold, der findes i .
Hvis og er to grafer, hvor vi betegner hjørnerne V (G) og V (H) og kanterne E (G) og E (H), er en applikation, der sender hjørnerne af G til dem af H, en morfisme af grafer hvis: , . Mere simpelt er en morfisme af grafer, hvis billedet af en hvilken som helst kant af G er en kant af H. Hvis der er en morfisme af G i H, siger vi klassisk, at G "projicerer" ind i H.
Denne definition er gyldig for begge grafer, der er orienteret som ikke-rettet . Det strækker sig til hypergrafier , orienteret eller ej.
Hvis der er en homomorfisme fra både G til H og en fra H til G, siger vi, at G og H er homomorfe ækvivalente (men dette betyder ikke, at de er isomorfe).
Der er ingen generel regel, der styrer antallet af homomorfismer mellem to grafer, som kan variere fra 0 til .
Graferne, der er knyttet til grafernes homomorfier, danner en kategori i betydningen af kategoriteori .
Vi siger om homomorfisme, at det er en injektion (henholdsvis overkastelse ), hvis det er injektiv (henholdsvis overvejende).
Hvis en homomorfisme er både injektions- og surjectiv, dvs. bijektiv , og dens omvendte også er en homomorfisme, så siger vi, at f er en isomorfisme.
En isomorfisme af en graf i sig selv kaldes en automorfisme.
Det er undertiden interessant at studere homomorfismerne i en graf i sig selv. Vi definerer derfor begrebet kernen graf . En graf siges at være kerne, når enhver homomorfisme af denne graf i sig selv er en isomorfisme. Enhver graf er homomorphically ækvivalent med en enkelt kerne graf (defineret op til isomorfi) .
Notationen angiver sættet af homomorfismer og er antallet af sådanne homomorfier, det vil sige kardinaliteten af . Vi bruger notationerne til injektion, til overjektion og til bijection.
Et meget klassisk problem i grafteorien er at bestemme, om en graf G kan farves med et bestemt antal n farver. Dette problem svarer til at spørge, om grafen G projekterer i den komplette graf . Dette er grunden til, at problemet med at vide, om en graf G projicerer i en graf H undertiden kaldes "H-farvning" -problemet. Dette problem kaldes også undertiden H-CSP-problemet, når H kan være en hypergraf . H ses derefter som begrænsningsgrafen forbundet med et CSP-problem .
En egenskab ved homomorfisme direkte fra definitionen vedrører eksistensen af en sti: begrænsningen af strukturen tvinger enhver kant af den originale graf til at eksistere i billedet.
Hvis vi er på toppen, og vi går forbi højderyggen , kan vi gøre den samme sti i billedet ved højderyggen ; vi opnår ved induktion, at enhver sti til findes ved stien til billederne i .
Dette indebærer for eksempel, at hvis G projicerer ind i H, er masken af G større end H.
En udvidelse af problemet blev foreslået i 2006: ved at knytte et toppunkt til et toppunkt på , betaler vi en pris, som vi betegner , og vi kan derefter definere omkostningerne ved en homomorfisme ved at sætte de omkostninger, der gives af hver forening af enten:
Målet er at afgøre, om der er en homomorfisme, hvis omkostninger ikke overstiger en grænse .
Blandt de andre variationer af problemet kan man angive en liste over tilladte billeder for hvert toppunkt . Denne variant generaliserer problemet med listefarvning.
En anden udvidelse af problemet består i at se på multihomomorfier mellem to grafer, det vil sige i de følgende applikationer: såsom Sættet af multihomomorfier mellem to grafer kan ses som et element i kategorien delvist ordnede sæt.