|
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 | MathML |
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 |
|
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 , , és -vel. Legyen az és -vel, pedig a és -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 él egy és egy -fokú pontot köt össze, akkor képe is egy és egy -fokú pontot köt össze.
6. Ha egy pontnak szomszédja van, s ezek rendre -fokúak, akkor a pont képének is szomszédja van, s ezek is rendre - fokúak. Mármost 4. miatt képe a mi gráfunkban csak , , vagy lehet. 5. miatt az él képe csak vagy lehet, mert csak ez a két él köt össze harmadfokú pontokat. 6. miatt képe csak vagy 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 képe.
I. eset. képe önmaga. Ekkor az él képe is -ból induló él, tehát az él képe is önmaga, így képe is önmaga. képe szomszédja képének, azaz -nak, így képe nem lehet . Tehát képe is önmaga. 1. miatt képe már nem lehet , így képe is önmaga. képe szomszédja képének, azaz -nek, tehát képe vagy . De már "foglalt'', így 1. miatt képe is önmaga. A él is helyén marad (2. miatt nem mehet át a már foglalt élbe), így képe is önmaga. Végül nyilván helyén marad az és között futó háromélű út és a és között futó háromélű út is. Ez az izomorfia tehát azonosság (minden pont helyben marad). II. eset. képe . Ekkor az él helyben marad ugyan (-be nem mehet), de megfordul: képe lesz. képe szomszédja képének, -nek, így képe . 1. miatt képe nem lehet , tehát képe csak lehet. képe szomszédja képének, tehát -nek, így képe vagy vagy . De már foglalt, így 1. miatt képe . A él is megfordul tehát: képe . Végül helyet cserél az és , illetve a és között futó háromélű út is. Az izomorfiát tehát most is egyértelműen meghatározza képe. (A kapott leképezés valóban izomorfia.) III. eset. képe . Ekkor az él képe csak a él lehet, így képe . képe szomszédja képének, azaz -nek, így csak lehet. képe tehát csak lehet ( már foglalt). képe szomszédja képének, -nek, tehát képe vagy , vagy . De már foglalt, így 1. miatt képe . képe már csak lehet. Az és között futó háromélű út most "megfordul'', a két belső pontja helyet cserél, és ugyanez történik a és között futó háromélű úttal is. A kapott leképezés tehát izomorfia, és képe egyértelműen meghatározza. IV. eset. képe . Ekkor az él képe a él, így képe . képe szomszédja képének, -nek, így nem lehet , csak . képe 1. miatt nem lehet , csak , így és önmagukba mennek át. De ekkor képe szomszédja -nek, tehát csak vagy lehet, ám már foglalt, így képe . Hasonlóan képe . A és közt futó háromélű út most átmegy az és 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ú és 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 és éle fehér, és éle fekete, és é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 képe csak vagy , képe csak vagy , képe pedig csak vagy lehet. Ha tehát rögzítjük képét, akkor ez meghatározza, hogy mi lesz az -ból induló három különböző színű él képe, s így , és 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).
|
|