Gráfhomomorfizmus

Gráfhomomorfizmus alatt gráfok közötti struktúratartó leképezéseket értünk. A struktúratartás azt jelenti, hogy a függvény szomszédos csúcsokat szomszédos csúcsokra képez le.

Legyenek ${\displaystyle G:=(V,E)}$ és ${\displaystyle G':=(V',E')}$ gráfok. Egy ${\displaystyle f:V\rightarrow V'}$ függvény gráfhomomorfizmus, ha

${\displaystyle \{u,v\}\in E\Longrightarrow \{f(u),f(v)\}\in E'}$.

Nem követeljük meg tehát, hogy f injektív legyen. Ha G-ből G'-be van homomorfizmus, azt szokás jelölni a ${\displaystyle G\rightarrow G'}$ szimbólumsorozattal is. Ha a két gráf nem homomorf, az jelölhető a következőképpen: ${\displaystyle G\not \rightarrow G'}$

1. Homomorfizmusok kompozíciója is homomorfizmus.
2. Ha az ${\displaystyle f}$ függvény invertálható és az inverz függvény is homomorfizmus, akkor ${\displaystyle f}$ gráfizomorfizmus.