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ó szerkesztés

Legyenek   és   gráfok. Egy   függvény gráfhomomorfizmus, ha

 .

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   szimbólumsorozattal is. Ha a két gráf nem homomorf, az jelölhető a következőképpen:  

Elemi tulajdonságok szerkesztés

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