Gráfizomorfizmus
matematikai fogalom a gráfelméletben
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óSzerkesztés
Legyenek és gráfok. Egy bijektív függvény gráfizomorfizmus, ha
- .
Ilyenkor azt mondjuk, hogy és izomorf.
PéldaSzerkesztés
|
Elemi tulajdonságokSzerkesztés
- 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ókSzerkesztés
- Pyber László: Babai és a gráf-izomorfizmus probléma (magyar nyelven). Érintő (Bolyai János Matematikai Társulat), 2017. március 1.