Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

2. Utazások az Ötörvény szigetvilágban

2. Utazások az Ötörvény szigetvilágban

4. feladat Az Ötörvény szigetvilágban kompok bonyolítják le a forgalmat (a kompok oda-vissza közlekednek). Mindegyik szigetről 3 másikra megy komp. A járatok úgy vannak kialakítva, hogy ha valaki körutazásra vágyik, akkor bármelyik szigetről indulva, mindig legalább 5 szigetet meg kell látogatnia (a kiindulási és egyben érkezési szigettel együtt), ha egyszer sem akar ugyanazzal a járattal visszafelé is utazni. Legalább hány szigetből áll Ötörvény szigetvilága?

A feladat megoldása előtt elmagyarázzuk a cikk címét, a „reguláris gráfok” kifejezést. Gráfról akkor beszélünk, ha vannak bizonyos „dolgok” – az előző feladatokban a tudósok, az utóbbiban a szigetek – és csak az érdekel minket, hogy ezek közül melyek állnak kapcsolatban egymással. A feladatokban a kapcsolatot a levelezés, illetve a kompjárat jelentette. A „dolgokat” a gráf csúcsainak nevezzük és ha két dolog között kapcsolat van, akkor azt mondjuk, hogy a két csúcs szomszédos vagy azt, hogy él köti össze őket. A szóhasználatot az magyarázza, hogy a poliéderek is tekinthetők gráfnak, ha valamely probléma kapcsán lapjaikról megfeledkezve csak csúcsaikkal és az élek hálózatával törődünk. Bizonyos kérdések esetén érdemes megengedni, hogy két csúcs között több él is fusson, vagy hasznos lehet olyan éleket bevezetni, amelynek két végpontja ugyanaz a csúcs. Egyszerűnek mondunk egy gráfot, ha nincsenek benne ilyen kettős- és hurokélek. Előfordulhat, hogy két „dolog” között egyirányú a kapcsolat, akkor irányítani kell a gráf éleit, hogy kifejezzék ezt a tulajdonságot. Ebben a cikkben irányítatlan egyszerű gráfokra vonatkozó kérdéseket vizsgálunk.

A gráfelmélet alapvető fogalma a fok. Egy csúcs foka a hozzá tartozó élek száma. Egyszerű gráfnál ez a csúcs szomszédainak számával egyezik meg. Akkor reguláris a gráf, ha minden csúcs foka ugyanaz a szám. A 4. feladat olyan gráfokról szól, amelyben minden csúcs foka 3. Körnek nevezzük a gráf csúcsainak és éleinek egy olyan c 1 e 1 c 2 e 2 c 3 e 3 c n e n c n + 1 sorozatát, amelyben az e i él a c i , c i + 1 csúcsok között fut, benne minden él különböző, továbbá az első és utolsó csúcs megegyezik egymással ( c 1 = c n + 1 ). A körben előforduló élek száma ( n ), a kör hossza. Az n hosszú kört n -szögnek is mondjuk. A gráf bősége[9] a legrövidebb körének hossza. Van olyan gráf is, amelyben nincsen kör, tehát bősége nem értelmezett.

A 4. feladat a gráfelmélet nyelvén így fogalmazható: „legalább hány csúcsa van egy 3-reguláris, 4-nél nagyobb bőségű gráfnak?”. Lássuk a megoldást!

Legyen a gráf egy tetszőleges csúcsa A , szomszédai B , C és D . B -nek, C -nek és D -nek még két-két további szomszédja van: B 1 , B 2 , C i , C j , D k , D l . Ezek között nem lehetnek sem a korábbiakkal, sem egymással azonos csúcsok, mert különben találhatnánk a gráfban egy legfeljebb 4 hosszúságú kört.

Megoldható-e a probléma ezzel a 10 csúccsal, további csúcsok hozzávétele nélkül? Próbáljuk meg! Nem húzhatunk élt B 1 és B 2 , se C i és C j , sem D k és D l között, ha nem akarunk 3 hosszúságú kört létrehozni. A B 1 csúcsból a C i , C j csúcsok közül csak legfeljebb egyhez mehet él, egyébként a B 1 , C i , C , C j csúcsok (a közöttük húzott élekkel) 4 hosszúságú kört alkotnának. Ugyanezen okból B 1 -ből a D k , D l csúcsoknak is csak egyikéhez mehet él. B 1 -nek csak úgy lehet 3 a foka, ha a C i , C j csúcsok egyikével és a D k , D l csúcsok egyikével is szomszédos. Az i , j , k , l indexeket váltsuk fel az 1, 2 számokkal úgy, hogy B 1 szomszédai C 1 és D 1 legyenek, a másik két csúcsot pedig jelölje C 2 és D 2 ! B 2 sem C 1 -gyel, sem D 1 -gyel nem lehet szomszédos, mert B 1 és B 2 a két közös szomszédjukkal ( B és C 1 vagy D 1 ) egy 4 hosszúságú kör csúcsait alkotnák. B 2 szomszédai tehát C 2 és D 2 lesznek. A C 1 , C 2 , D 1 , D 2 csúcsok foka jelenleg 2, így még egy-egy élt, összesen kettőt kell közöttük húzni. C 1 szomszédja sem C 2 ( C C 1 C 2 C ), sem D 1 nem lehet ( B 1 C 1 D 1 B 1 ), marad D 2 . Végül C 2 -ből már csak D 1 -hez húzhatunk élt. Az ábrán gyorsan áttekinthetjük, hogy a kapott gráfban nincs 5-nél rövidebb kör.

4. ábra.

A 4. feladat kérdésére tehát a válasz 10. A megoldásban kicsit többet is kaptunk ennél. Kiderült, hogy ha egy 3-reguláris gráfnak 10 csúcsa van és nincs benne 5-nél rövidebb kör, akkor a gráf csúcsait megjelölhetjük az A , B , C , D , B 1 , B 2 , C 1 , C 2 , D 1 , D 2 szimbólumokkal úgy, hogy két csúcs között pontosan akkor legyen él, ha a 4. ábrán ugyanolyan módon jelölt csúcsok között van él. Tehát az optimális 10-es csúcsszám csak olyan gráfok esetén valósulhat meg, amely gráfelméleti szempontból (tehát a csúcsok száma, és a közöttük futó élek rendszere alapján) megkülönböztethetetlenek egymástól, azaz izomorfak. Tehát lényegében – azaz izomorfia erejéig – csak egyetlen ilyen gráf van: ez a Petersen-gráf.

5. feladat Rajzoljuk le a Petersen-gráfot úgy, hogy az ábrának

a) 108 ° -os;

b) 120 ° -os forgási szimmetriája legyen!

6. feladat Hány ötszög (5 hosszúságú kör) van a Petersen-gráfban?

7. feladat Az Ötörvény Utazási Iroda prospektusában felsorolták a 10 sziget nevét, leírták, hogy mely szigetek közt jár komp és egy kis térképet is mellékeltek, amelyre berajzolták a szigeteket, sőt, a kompjáratokat is jelölték. Sajnos, a nyomda hibája folytán a térképre nem kerültek rá a szigetek nevei. Hányféleképpen feleltethető meg a 10 név a 10 szigetnek úgy, hogy a térképen jelölt és a prospektusban felsorolt kompjáratok egyezzenek?

A feladat arra kérdez rá, hogy hányféleképpen izomorf önmagával a Petersen-gráf. Egy gráf önmagával való izomorfizmusát, a gráf automorfizmusának is nevezik, ez a geometriai szimmetria-fogalom gráfelméleti változata.

Az A jelet a 10 sziget bármelyikére írhatjuk, a B , C , D jeleket hatféleképpen rendezhetjük el A szomszédai között. B 1 megválasztására még két lehetőségünk marad, de azután B 2 , majd C 1 , C 2 , D 1 és D 2 helye már egyértelműen adódik. Tehát 120-féleképpen feleltethető meg a 10 név a 10 szigetnek, azaz 120 automorfizmusa van a Petersen-gráfnak.

Hasonlítsuk össze a Petersen-gráfot a dodekaéder-gráffal! Mindkettő 3-reguláris 5 bőségű gráf, de a Petersen-gráfnak csak feleannyi csúcsa van, mint a másiknak, amellett, hogy ugyanannyi (12) ötszöget tartalmaz, mint a dodekaéder, és ugyanannyi (120) szimmetriája is van. A tömörségnek azonban ára van: a Petersen-gráfhoz nem illeszthetők „lapok”, nem lehet térbeli poliéder élhálózataként megvalósítani.

5. ábra.

8. feladat Bizonyítsuk be, hogy a dodekaéder-gráf bármely automorfizmusa megvalósítható a dodekaéder térbeli szimmetriájaként. Mutassuk meg, hogy a dodekaédernek 120 szimmetriája van!

Kiss Emil könyvünkben található cikkének elolvasása után érdemes elgondolkodni azon, hogy a dodekaéder és a Petersen-gráf szimmetria-csoportja megegyezik-e egymással.



[9] Lovász a „kerület” szót használja erre a fogalomra.