Gráfhomomorfizmus

A Wikipédiából, a szabad enciklopédiából

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 | forrásszöveg szerkesztése]

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

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

Elemi tulajdonságok[szerkesztés | forrásszöveg szerkesztése]

  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.