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

7. A feladatok megoldása

7. A feladatok megoldása

2. Ez nem lehetséges. Képzeljük el, hogy mindegyik tudós felad mindegyik levelezőtársának egy-egy levelet! Mivel mind a hét 7 tudós 3-3 másiknak küld levelet, így összesen 21 levelet adnak fel. Másrészt azonban ilyenkor bármely két tudós között 0 vagy 2 levél lesz úton, így a levelek száma páros. Az ellentmondás azt mutatja, hogy nem lehet pont 7 a tagok száma.

5. Kicsit több is elérhető: a bal oldali ábra egy szabályos ötszög, a jobb oldali egy szabályos háromszög minden szimmetriájával rendelkezik.

16. ábra.

6. A kör első csúcsát 10 különböző módon választhatjuk, a másodikat 3, a harmadikat és a negyediket már csak 2-2-féleképpen: vissza soha nem mehetünk, de az előzőnél korábbi csúcshoz nem is tudunk visszajutni, hiszen nincs 5-nél rövidebb kör. Az utolsónak kapott csúcs ugyanezért nem lehet szomszédos a legelsővel.

Könnyen ellenőrizhető, hogy bármelyik csúcsról bármelyik másikra is akarunk menni, azt megtehetjük legfeljebb két élen (és egy közbenső csúcson) át, ezért most is biztos befejezhetjük a kört még két éllel (és egy új csúccsal). Csak egy lehetőség van a befejezésre, mert ha kettő is lenne, akkor az a kettő egymásba fűzve egy 4 hosszú kört alkotna. A lehetőségek száma tehát 10 · 3 · 2 · 2 = 120 .

Nem érdemes megkülönböztetni két kört, ha ugyanazokat a csúcsokat és éleket máshonnan indulva, de ugyanabban a sorrendben, vagy éppen ellenkező sorrendben járja végig. Ebben az értelemben az ötszögek száma, az előző eredménynek csak a 10-ede, azaz 12.

Vajon hány hatszöge van a Petersen gráfnak? Milyen hosszúságú körök vannak még benne?

8. Az nyilvánvaló, hogy a dodekaéder bármely térbeli szimmetriája egyben a dodekaéder-gráf automorfizmusa is. Jelöljük a dodekaéder egy csúcsát A -val, szomszédait és azok szomszédait pedig az ábra szerint. Az A csúcs térbeli szimmetriával átvihető bármelyik másik A ' csúcsba ( 20 lehetőség). Bárhogy is osztjuk ki A ' szomszédai között a B ' , C ' , D ' jeleket, mindig található a dodekaédernek olyan további forgási, esetleg síkra tükrözési szimmetriája, hogy végeredményképp A az A ' -be B a B ' , C a C ' -be, D a D ' -be képződjék ( 6 lehetőség, összesen 120). Akár a dodekaédert, akár a dodekaéder-gráfot tekintjük, B , C és D képe már egyértelműen meghatározza, hogy melyik csúcsba képződjön B C , B D , C B , C D , D B és D C , majd ezekre alapozva fokozatosan az összes többi csúcs képe is meghatározható.

17. ábra.

10. 42.

11. Megmutatjuk, hogy nincs ilyen gráf 17 és 18 csúccsal sem.

Először 17 csúccsal próbálkozunk. Az indexek megválasztásában van egy kis szabadságunk. Ezt használjuk föl a következőképpen. B 1 -nek még három szomszédja van B -n kívül. Ezek csakis azok közül a csúcsok közül kerülhetnek ki, amelyek jelében index is van, hiszen csak azoknak nem ismerjük már minden szomszédját. Nem jöhet szóba B 2 és B 3 , mert nem engedhetünk meg a B B 1 B i B 3 hosszú kört. Nem lehet a szomszédok között két C i , mondjuk C 1 és C 2 , mert az a négy hosszú C C 1 B 1 C 2 C kört eredményezné. Hasonló okból két D i , két E i csúcs sem lehet, tehát B 1 -nek egy-egy szomszédja van a C i , a D i és az E i csúcsok közül. Ezeket fogjuk C 1 -gyel, D 1 -gyel és E 1 -gyel jelölni. B 2 -nek nem lehet B -n kívül más közös szomszédja B 1 -gyel, mert az 4 hosszúságú kört adna, ezért feltehetjük, hogy B 2 szomszédai C 2 , D 2 és E 2 , végül B 3 szomszédai C 3 , D 3 és E 3 .

18. ábra.

Tegyük egy szabályos háromszög egyik oldalának belsejére a C 1 , C 2 és C 3 pontokat, egy másikra D 1 -et, D 2 -t és D 3 -at, a harmadikra E 1 -et E 2 -t és E 3 -at. Mindegyik pontot két másikkal kell még összekötni, a másik két oldal egy-egy pontjával. Ha elindulunk az egyik, mondjuk a C k csúcsról az egyik forgásirányba egy él mentén, majd mindig továbbmegyünk, akkor egy C k D l E m C n utat járunk be. Látni fogjuk, hogy a k , l , m , n indexek nem adhatók meg úgy, hogy ne leljünk rá egy ötnél rövidebb körre. Azonos indexű pontok nem következhetnek egymás után, mert azok az ugyanolyan indexű B i ponttal alkotnának 3 hosszúságú kört. Egyik pont két szomszédja sem lehet egymással azonos indexű, mert akkor az ugyanolyan indexű B i ponttal ezek egy 4 hosszúságú kört alkotnának. Emiatt az l és az m index meghatározza k -t: ez csak az l -től és m -től is különböző egyetlen megmaradó index lehet. De l és m pontosan ugyanígy határozza meg k -t is: C k = C n , azaz C k D l E m C n maga egy 3 hosszúságú kör.

Nézzük 18 csúcs esetét! Az előző megoldáshoz hasonlóan szeretnénk találni egy 4 tagú C k D l E m C n típusú utazást, amely biztosan eredményez rövid körutat.

A 18. csúcsot F -fel jelöljük. F -nek a B i , a C i , a D i és az E i csúcshármasok mindegyikében egy-egy szomszédja van, a B i -k közti szomszédja legyen B 1 . A C i , a D i és az E i csúcshármasok indexelését ugyanúgy végezzük el, mint az előző esetben. Csak egy változás lesz: a B 1 csúcsból összesen csak két él indul a C i , D i , E i csúcshármasok felé, tehát egy csúcsnak, mondjuk egynek az E i -k közül nem jut index. Ezt a szigetet jelölje E 1 * . B 1 szomszédai tehát F , C 1 és D 1 ; B 2 szomszédai C 2 , D 2 és E 2 ; B 3 szomszédai C 3 , D 3 és E 3 . E 1 * és F között van él, mert E 1 * -nak csak így lehet a foka 4.

E 2 és F között már nem lehet él, így a C i és a D i csúcshármasok között is van egy-egy szomszédja. Legyen ez a két csúcs C m és D n . Ezek közül legalább az egyiknek nem szomszédja F , mert egyébként F C m E 2 D n F négy hosszúságú körút lenne. Feltehetjük, hogy C m és F közt nincs él. Ekkor viszont van szomszédja a D i csúcshármasban, mondjuk D k . Így D k C m E 2 D n az ígért négy tagú utazás, amelybe nem írhatók úgy be a számok, hogy ne kapjunk ötnél rövidebb kört.

19 csúcsú 4-reguláris gráf létezik. E gráfot először N. Robertson adta meg, ábrája itt látható.

19. ábra.

Más betűzéssel az alábbi táblázat adja meg a gráfot ( 19 = 3 + 4 + 3 · 4 ):

B 1 B 2 B 3 B 4 A 1 C 1 C 10 C 7 C 4 A 2 C 5 C 2 C 11 C 8 A 3 C 9 C 6 C 3 C 12

Az A i csúcsok a velük egy sorban álló csúcsokkal szomszédosak, a B i csúcsok a velük egy oszlopban levőkkel, illetve még B 1 a B 3 -mal és B 2 a B 4 -gyel. Ezen kívül a C 1 , C 2 , C 3 , , C 12 , C 1 sorozatban egymást követő csúcsok a gráfban is szomszédosak.

12. Lásd az 1., 3, 4., 9. feladatokat és megoldásukat az 1. fejezetben.

13. Az ötszögek száma: 3250 · 57 · 56 2 10 = 58 094 400 , míg a hatszögeké: 3250 · 57 · 56 2 · 55 12 = 2 662 660 000 .

14. 24 (lásd [2] III.6./9. feladat).

15. Számoljuk meg a csúcsokat az egyik csúcsból kiindulva, mindig az összes szomszédot is megszámolva.

16. Ha g páratlan, akkor a g bőségű Moore gráf átmérője g - 1 2 , ha g páros, akkor az átmérő g 2 .

18. (i) Indirekten okoskodunk. Tegyük fel, hogy a és b legalább ( g + 1 ) távolságra lévő csúcsok. Töröljük a -t és b -t! Így a szomszédaiból és b szomszédaiból is eggyel kevesebb él indul, mint eredetileg. Állítsuk párba a szomszédait b szomszédaival, és a pár két tagját kössük össze éllel. Így újra r -reguláris lesz a gráf. Mivel a és b között nem volt ( g + 1 ) -nél rövidebb út, így az új gráfban az eltűnt a bármely szomszédja, és b bármely szomszédja között a régi éleket használva csak legalább ( g - 1 ) hosszú úton lehet eljutni egymásba.

Ha kiderülne, hogy új gráfunk bősége legalább g , akkor ellentmondást kapnánk, eredeti gráfunk nem lehetett a legkisebb.

Tekintsük az új gráf egyik legrövidebb körét! Ha ez nem tartalmaz új élt, akkor benne volt az eredeti gráfban is, így hossza legalább g . Ha pontosan egy új élt tartalmaz, akkor az új élen kívüli része az eredeti gráfban összeköti a és b egy-egy szomszédját. Ez a rész legalább ( g - 1 ) élből áll, tehát az új éllel együtt legalább g hosszúságú a kör. Ha viszont legalább két élt tartalmaz, akkor vagy megint tartalmaz az előzőhöz hasonlóan egy a - és egy b -szomszédot összekötő G -beli utat vagy tartalmaz legalább egy olyan G -beli utat, mely a két szomszédját köti össze egymással és még legalább egy olyat is, amely b két szomszédját köti össze. Egy-egy ilyen út legalább ( g - 2 ) hosszúságú, hiszen G bősége legalább g volt. 2 + 2 ( g - 2 ) //<// g viszont nem lehetséges, így az új gráf bősége legalább g .

(ii) Két esetet különböztetünk meg aszerint, hogy r páros vagy páratlan.

1. eset: r = 2 l . Töröljünk egy tetszőleges x csúcsot és szomszédait állítsuk párokba, a párok tagjait kössük össze éllel. Ekkor egy kevesebb csúcsú r -reguláris gráfot kapunk, melyben tehát kell legyen legfeljebb ( g - 1 ) hosszúságú kör. Ez nyilván tartalmaz legalább egy új élt. Kettő vagy több új él nem lehet benne, mert az új élek közti részek x két szomszédját kötik össze, így mindegyik ilyen rész legalább ( g - 2 ) hosszúságú. Tehát pontosan egy új él van a legfeljebb ( g - 1 ) hosszúságú körben. Ezt az új élt visszacserélve az x -ből a két szomszédjához menő két élre, G -ben egy legfeljebb g hosszúságú kört kapunk.

2. eset: r = 2 l + 1 Feltehetjük, hogy g ? 4 , hiszen a g = 2 és g = 3 esetek triviálisak: az elsőben G két csúcsból áll, köztük r párhuzamos éllel, míg a másodikban G az ( r + 1 ) csúcsú teljes gráf.

Hagyjunk el egy tetszőleges ( x , y ) élt és állítsuk párba x maradék 2 l szomszédját egymás között és y maradék szomszédait is egymás között. Az előző esethez hasonlóan az új gráfban egy legfeljebb ( g - 1 ) hosszúságú kört véve, az eredeti gráfban találhatunk egy g hosszúságú kört.

(iii) Ez már következik (i)-ből a 15. feladat állítása miatt.