Gráfizomorfizmus
Megjelenés
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élda
[szerkesztés]![]() |
![]() |
|
Elemi tulajdonságok
[szerkeszté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ók
[szerkeszté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.