Feladat: F.2632 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Baboss Cs. ,  Bánkövi Johanna ,  Beke T. ,  Benczúr A. ,  Bereczky Á. ,  Binder Zsuzsanna ,  Csűrös M. ,  Cynolter G. ,  Eckert B. ,  Gács A. ,  Hajdú G. ,  Hajnal Z. ,  Kecskés K. ,  Keleti T. ,  Majoros L. ,  Mátrai Katalin ,  Rimányi R. ,  Szabó 484 P. ,  Szalay Gy. ,  Szepesi Zsuzsanna ,  Tasi Andrea ,  Tasnádi T. 
Füzet: 1987/november, 373 - 374. oldal  PDF file
Témakör(ök): Euler-féle poliédertétel alkalmazásai, Kombinatorikai leszámolási problémák, Feladat
Hivatkozás(ok):Feladatok: 1987/április: F.2632

Hányféleképpen lehet az ábrán látható gráfot önmagára úgy leképezni, hogy csúcs csúcsba, él pedig élbe menjen át?
 
 


A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

I. megoldás. Jelöljük a gráf négy harmadfokú pontját az ábrán látható módon A, B, C és D-vel. Legyen E1 az A és C-vel, E2 pedig a B és D-vel összekötött másodfokú pont.

 
 

Az olyan leképezést, amely egy gráf csúcsait csúcsokba, éleit élekbe képezi le, a gráf izomorfiájának nevezzük. Az ilyen izomorfiának nyilván megvannak a következő tulajdonságai:

1. Különböző csúcsokat különböző csúcsokba visz, különben a kép-gráfnak  kevesebb csúcsa volna, mint az eredetinek.

2. Különböző éleket különböző élekbe visz, ez következik az előző tulajdon
 ságból.

3. "Nem-élt'' is "nem-élbe'' visz (ha két pont nincs összekötve, akkor képeik
 sem lehetnek összekötve, különben a kép-gráfnak több éle volna, mint az
 eredetinek.)

4.Fokszámtartó (a pontnak és képének foka megegyezik).

5.Ha egy e él egy d és egy d'-fokú pontot köt össze, akkor e képe is egy
  d és egy d'-fokú pontot köt össze.

6. Ha egy pontnak k szomszédja van, s ezek rendre d1,d2,...,dk-fokúak,
 akkor a pont képének is k szomszédja van, s ezek is rendre d1,d2,...,dk-
 fokúak.
 Mármost 4. miatt A képe a mi gráfunkban csak A, B, C vagy D lehet.
 

5. miatt az AD él képe csak AD vagy BC lehet, mert csak ez a két él köt össze harmadfokú pontokat.
6. miatt E1 képe csak E1 vagy E2 lehet, mert csak e két olyan másodfokú pont van, amelynek mindkét szomszédja harmadfokú.
E három észrevétel alapján megmutatjuk, hogy gráfunk izomorfiáit egyértelműen meghatározza az, hogy mi az A képe.
 
I. eset. A képe önmaga. Ekkor az AD él képe is A-ból induló él, tehát az AD él képe is önmaga, így D képe is önmaga. E1 képe szomszédja A képének, azaz A-nak, így E1 képe nem lehet E2. Tehát E1 képe is önmaga. 1. miatt E2 képe már nem lehet E1, így E2 képe is önmaga. C képe szomszédja E1 képének, azaz E1-nek, tehát C képe A vagy C. De A már "foglalt'', így 1. miatt C képe is önmaga. A CD él is helyén marad (2. miatt nem mehet át a már foglalt AD élbe), így D képe is önmaga. Végül nyilván helyén marad az A és B között futó háromélű út és a C és D között futó háromélű út is. Ez az izomorfia tehát azonosság (minden pont helyben marad).
 

II. eset. A képe D. Ekkor az AD él helyben marad ugyan (BC-be nem mehet), de megfordul: D képe A lesz. E1 képe szomszédja A képének, D-nek, így E1 képe E2. 1. miatt E2 képe nem lehet E2, tehát E2 képe csak E1 lehet. C képe szomszédja E1 képének, tehát E2-nek, így C képe vagy D vagy B. De D már foglalt, így 1. miatt C képe B. A BC él is megfordul tehát: B képe C. Végül helyet cserél az A és B, illetve a D és C között futó háromélű út is. Az izomorfiát tehát most is egyértelműen meghatározza A képe. (A kapott leképezés valóban izomorfia.)
 

III. eset. A képe B. Ekkor az AD él képe csak a BC él lehet, így D képe C. E1 képe szomszédja A képének, azaz B-nek, így csak E2 lehet. E2 képe tehát csak E1 lehet (E2 már foglalt). C képe szomszédja E1 képének, E2-nek, tehát C képe vagy B, vagy D. De B már foglalt, így 1. miatt C képe D. B képe már csak A lehet. Az A és B között futó háromélű út most "megfordul'', a két belső pontja helyet cserél, és ugyanez történik a C és D között futó háromélű úttal is. A kapott leképezés tehát izomorfia, és A képe egyértelműen meghatározza.
 

IV. eset. A képe C. Ekkor az AD él képe a BC él, így D képe B. E1 képe szomszédja A képének, C-nek, így nem lehet E2, csak E1. E2 képe 1. miatt nem lehet E1, csak E2, így E1 és E2 önmagukba mennek át. De ekkor C képe szomszédja E1-nek, tehát csak C vagy A lehet, ám C már foglalt, így C képe A. Hasonlóan B képe D. A C és D közt futó háromélű út most átmegy az A és B közt futó háromélű útba, és viszont. Így ismét egyértelműen meghatározott izomorfiát kaptunk.
A gráfnak tehát négy izomorfiája van.
 

II. megoldás. Tekintsük a harmadfokú A,B,C és D pontokat. Ezek között hat, harmadik harmadfokú pontot nem érintő út halad: két él, két kétélű út és két háromélű út. Nyilvánvaló, hogy a két él, a két kétélű út, illetve a két háromélű út csak egymással cserélhető ki. A gráf tehát ugyanúgy viselkedik, mint egy négycsúcsú teljes gráf, amelynek AB és CD éle fehér, AC és BD éle fekete, AD és BC éle pedig kék.
A leképezés során most nyilván azt írjuk elő, hogy minden él színe egyezzék meg a kép-él színével, azaz AB képe csak AB vagy CD, AC képe csak AC vagy BD, AD képe pedig csak AD vagy BC lehet. Ha tehát rögzítjük A képét, akkor ez meghatározza, hogy mi lesz az A-ból induló három különböző színű él képe, s így B, C és D képe is egyértelműen meghatározott. Így négy leképezést kapunk, és könnyen ellenőrizhető, hogy mind a négy leképezés valóban izomorfia (lásd a táblázatot).
 

AABACADBCDAABACADBCDBBABDBCADCCCDCACBDABDDCDBDACBA