Gráfizomorfizmus

A gráfizomorfizmusok gráfok közötti bijektív struktúratartó leképezések, értve ezalatt azt, hogy a függvény és az inverz függvény egyaránt szomszédos csúcsokat szomszédos csúcsokra képez le. Az általuk meghatározott ekvivalenciarelációt gráfizomorfiának nevezzük.

Definíció

Legyenek ${\displaystyle G:=(V,E)}$ és ${\displaystyle G':=(V',E')}$ gráfok. Egy ${\displaystyle f:V\rightarrow V'}$ bijektív függvény gráfizomorfizmus, ha

${\displaystyle \{u,v\}\in E\Leftrightarrow \{f(u),f(v)\}\in E'}$.

Ilyenkor azt mondjuk, hogy ${\displaystyle G}$ és ${\displaystyle G'}$ izomorf.

Példa

${\displaystyle G=(V,E)}$	${\displaystyle G'=(V',E')}$	${\displaystyle f:V\rightarrow V'}$
		${\displaystyle f(a)=1}$ ${\displaystyle f(b)=6}$ ${\displaystyle f(c)=8}$ ${\displaystyle f(d)=3}$ ${\displaystyle f(g)=5}$ ${\displaystyle f(h)=2}$ ${\displaystyle f(i)=4}$ ${\displaystyle f(j)=7}$

Elemi tulajdonságok

• Gráfizomorfizmusok kompozíciója és inverze is gráfizomorfizmus; gráfok izomorfiája tehát ekvivalenciareláció.
• Egy gráf önmagával való izomorfizmusait automorfizmusoknak hívjuk. Egy ${\displaystyle (V,E)}$ gráf automorfizmusai a ${\displaystyle V}$ permutációcsoportjának egy részcsoportját alkotják.

További információk

• Pyber László: Babai és a gráf-izomorfizmus probléma (magyar nyelven). Érintő (Bolyai János Matematikai Társulat), 2017. március 1.

Lásd még

• Gráfhomomorfizmus
• Gráfizomorfizmus-probléma
• GI bonyolultsági osztály
• Gráfautomorfizmus