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ó
Legyenek és
gráfok. Egy
bijektív függvény gráfizomorfizmus, ha
.
Ilyenkor azt mondjuk, hogy és
izomorf.
Példa
![]() | ![]() |
|
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
- 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
🔥 Top keywords: Kezdőlap2024-es labdarúgó-Európa-bajnokságSpeciális:KeresésLabdarúgó-Európa-bajnokság2020-as labdarúgó-Európa-bajnokságGattyán GyörgyÁdám MartinKylian MbappéTisztelet és Szabadság Párt2024-es labdarúgó-Európa-bajnokság (selejtező)ColdplayMagyar Péter (jogász)Magyar labdarúgó-válogatottFrancia labdarúgó-válogatottApák napjaAgymanók 2.Romelu LukakuSárkányok házaSpeciális:Friss változtatások2024-es európai parlamenti választás MagyarországonLibik GyörgyPuskás Ferenc (labdarúgó)Antoine GriezmannMagyarországLabdarúgó-világbajnokságBelga labdarúgó-válogatottAz Európai Unió tagállamaiGrúzia2016-os labdarúgó-Európa-bajnokság2024. évi nyári olimpiai játékokJúnius 17.Chris MartinFIFA-világranglistaSzoboszlai DominikRomán labdarúgó-válogatottVitézy Dávid2024-es magyarországi önkormányzati választásCristiano RonaldoZichyújfalu