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 és gráfok. Egy bijektív függvény gráfizomorfizmus, ha . Ilyenkor azt mondjuk, hogy és izomorf.
Példa
100px210px
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 gráf automorfizmusai a permutációcsoportjának egy részcsoportját alkotják.
További információk
Lásd még Gráfhomomorfizmus Gráfizomorfizmus-probléma GI bonyolultsági osztály Gráfautomorfizmus
Kategória:Gráfelmélet Kategória:Gráfalgoritmusok