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ó
szerkesztésLegyenek é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- Homomorfizmusok kompozíciója is homomorfizmus.
- Ha az függvény invertálható és az inverz függvény is homomorfizmus, akkor gráfizomorfizmus.