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 ) {\displaystyle G:=(V,E)} és G ′ := ( V ′ , E ′ ) {\displaystyle G':=(V',E')} gráfok. Egy f : V → V ′ {\displaystyle f:V\rightarrow V'} függvény gráfhomomorfizmus, ha

{ u , v } ∈ E ⟹ { f ( u ) , f ( v ) } ∈ E ′ {\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 G → G ′ {\displaystyle G\rightarrow G'} szimbólumsorozattal is. Ha a két gráf nem homomorf, az jelölhető a következőképpen: G ↛ G ′ {\displaystyle G\not \rightarrow G'}

Elemi tulajdonságok

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