Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 3949. feladat (2006. november)

B. 3949. Az n milyen pozitív egész értékeire van olyan egyszerű gráf, amelynek minden csúcsa legfeljebb n-edfokú és minden 1\lei\len esetén i darab i-edfokú csúcsa van?

Javasolta: Mészáros Gábor, Kemence

(4 pont)

A beküldési határidő 2006. december 15-én LEJÁRT.


Megoldás. A fokszámok n(n+1)/2 összege, lévén az élek számának kétszerese, páros szám kell legyen. Ezért szükséges, hogy az n szám 4-gyel osztva 0 vagy 3 maradékot adjon. Megmutatjuk, hogy ez a feltétel egyben elégséges is. Az n=3, illetve az n=4 esetben ilyen gráfot láthatunk a mellékelt ábrán. Már csak azt kell megmutatni, hogy ha valamely n-re találtunk egy megfelelő Gn gráfot, akkor n értékét 4-gyel növelve, tudunk konstruálni egy megfelelő Gn+4 gráfot. Ezt pedig úgy tehetjük meg, ha a először a Gn gráf mellé felvesszük a Kn+1, Kn+2, Kn+3 és Kn+4 teljes gráfokat rendre n+1, n+2, n+3, illetve n+4 csúcson úgy, hogy az öt gráf csúcshalmazai páronként diszjunktak legyenek, majd pedig a Kn+1 és Kn+4 gráfok összesen 2n+5 csúcsát egy-egy új él segítségével összepárosítjuk a Kn+2 és Kn+3 gráfok összesen 2n+5 csúcsával. (Tulajdonképpen már a G4 gráfot is megkaphatjuk ilyen módon a 0 szögpontú G0 üres gráfból.)


Statisztika:

89 dolgozat érkezett.
4 pontot kapott:Aczél Gergely, Ágoston Tamás, Anda Roland, Aujeszky Tamás, Bartha Zsolt, Blázsik Zoltán, Blutman Kristóf László, Bock Lilla, Bodor Bertalan, Bogár 560 Péter, Csaba Ákos, Cseh Ágnes, Cséke Balázs, Éles András, Fonyó Dávid, Gévay Gábor, Gresits Iván, Grósz Dániel, Győrffy Lajos, Herber Máté, Honner Balázs, Károlyi Gergely, Kiss 243 Réka, Kiss 902 Melinda Flóra, Kornis Kristóf, Korom-Vellás Judit, Kunos Ádám, Kunovszki Péter, Kurgyis Eszter, Mészáros András, Nagy 314 Dániel, Paál Gergely, Papp 648 Pál András, Peregi Tamás, Salát Zsófia, Sárkány Lőrinc, Sümegi Károly, Szalkai Balázs, Szalóki Dávid, Szűcs Gergely, Tallián György, Tossenberger Anna, Tóth 222 Barnabás, Tóth 666 László Márton, Tóth 796 Balázs, Török Balázs, Vajsz Tibor, Varga 171 László, Wolosz János.
3 pontot kapott:17 versenyző.
2 pontot kapott:18 versenyző.
1 pontot kapott:5 versenyző.

A KöMaL 2006. novemberi matematika feladatai