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.

Definíció

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

$\{u,v\}\in E⟹\{f(u),f(v)\}\in E^{\prime }$.

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 $G\to G^{\prime }$ szimbólumsorozattal is. Ha a két gráf nem homomorf, az jelölhető a következőképpen: $G\to ̸G^{\prime }$

Elemi tulajdonságok

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