Page 97 - vol1

Az izomorf gráf fogalmának az elméleti háttere

Egy gráf síkgráf, ha az éleinek nincsen - a végpontoktól különböző - közös
pontjuk (vagyis az élei nem metszik egymást). A következő ábrán egy nem síkgáf
illetve ennek síkgráffá való átalakítása látható:

Az ábrán látható két gráf valójában egymással ekvivalens, pontosabban
úgy mondjuk, hogy izomorf.

Két gráf Izomorf gráf, ha van olyan egyértelmű megfeleltetés
melyet izomorfizmusnak hívunk, hogy két csúcs szomszédos G- ben akkor és
csak akkor, ha a megfelelőik szomszédosak H- ban. Gyakorlatilag ez azt jelenti,
hogy a gráfot úgy tekintjük, mintha gumiból lenne, és ennek a csúcsait
tetszőlegesen eltolhatjuk, az éleket tetszőlegesen megnyújthatjuk, és az így
kapott gráf valójában nem különbözik az eredeti gráftól, úgy mondjuk, hogy
azzal izomorf. Három ilyen izomorf gráf az alábbiakban látható:

Ezek szerint könnyen belátható, hogy egy adott gráffal végtelen sok izomorf gráf
létezik.

Azt, hogy egy adott gráf milyen más gráffal izomorf, nem mindig látható az első
ránézésre. Az izomorfizmus megállapításánál figyelembe kell vennünk, hogy
csak két azonos csúcsszámmal rendelkező gráf lehet izomorf, de csak akkor, ha

97