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. 4052. feladat (2008. január)

B. 4052. Egy egyszerű gráfban ugróiskolának nevezünk egy olyan P1,P2,...,Pk utat, amelyben minden i-re a Pi csúcs fokszáma i. Legfeljebb hány csúcsa lehet egy ugróiskolának egy n csúcsú gráfban?

Javasolta: Mészáros Gábor

(4 pont)

A beküldési határidő 2008. február 15-én LEJÁRT.


Megoldás: Jelölje a kérdéses számot f(n). Könnyen ellenőrizhető, hogy f(1)=0, f(2)=1, f(3)=f(4)=2 és f(5)=3. Tegyük fel, hogy a gráfban van egy P1,P2,...,Pk ugróiskola, ahol k\ge4. Pk az út csúcsai közül P1-gyel, P2-vel és saját magával nem lehet összekötve, vagyis a gráfnak kell legyen még legalább 3 további csúcsa. Ez azt mutatja, hogy n\ge6 esetén f(n)\len-3. A továbbiakban megmutatjuk, hogy n\ge6 esetén f(n)\gen-3 is fennáll, vagyis k\ge3 esetén van olyan k+3 szögpontú egyszerű Gk gráf, amely tartalmaz k csúcsú ugróiskolát.

Vegyünk fel ehhez egy P_1P_2\ldots P_k utat, és 3\lei,j\lek, i\nej, k+3\lei+j esetén kössük össze a Pi és a Pj csúcsokat (amennyiben eddig még nem voltak összekötve) egy éllel. Az így kapott Hk egyszerű gráfban jelölje d(i) a Pi csúcs fokát. Nyilván d(1)=1 és d(2)=2. Ha i\ge3, akkor k+3-i\lej\lek, i\nej esetén Pi össze van kötve Pj-vel, vagyis d(i)\ge(i-2)-1=i-3. Másrészt azon az i-2 darab Pj csúcson kívül, amelyre k+3-i\lej\lek teljesül, Pi legfeljebb két további csúccsal lehet összekötve a P_1P_2\ldots P_k út mentén, vagyis d(i)\le(i-2)+2=i. összefoglalva, i\ge3 esetén 0\lei-d(i)\le3. Ha felveszünk három további csúcsot, és 3\lei\lek esetén a Pi csúcsot ezek közül i-d(i) darabbal összekötjük, olyan k+3 csúcsot tartalmazó Gk egyszerű gráfot kapunk, amelyben P1,P2,...,Pk ugróiskola.

Megállapíthatjuk tehát, hogy n\ge6 esetén f(n)=n-3.


Statisztika:

82 dolgozat érkezett.
4 pontot kapott:Aczél Gergely, Ágoston Tamás, Bálint Dániel, Balla Attila, Bencs 111 Ferenc, Bodor Bertalan, Börcsök Bence, Cséke Balázs, Csere Kálmán, Czeller Ildikó, Dudás 002 Zsolt, Éles András, Farkas Márton, Fonyó Dávid, Frankl Nóra, Gele Viktória, Gévay Gábor, Gőgös Balázs, Grósz Dániel, Kalina Kende, Kiss 243 Réka, Kiss 902 Melinda Flóra, Kiss 991 Mátyás, Konkoly 001 Csaba, Kovács 729 Gergely, Kovács Kristóf, Kristóf Panna, Marák Károly, Mészáros András, Mihálykó Ágnes, Nagy 648 Donát, Palincza Richárd, Peregi Tamás, Perjési Gábor, Réti Dávid, Salát Zsófia, Szabó 124 Zsolt, Szabó 895 Dávid, Szalkai Balázs, Szőke Nóra, Tóth 369 László Márton, Véges Márton, Zelena Réka.
3 pontot kapott:12 versenyző.
2 pontot kapott:4 versenyző.
1 pontot kapott:9 versenyző.
0 pontot kapott:11 versenyző.
Nem versenyszerű:3 dolgozat.

A KöMaL 2008. januári matematika feladatai