KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem B. 4052. (January 2008)

B. 4052. A path P1,P2,...,Pk in a simple graph is said to be a fan if the degree of every point Pi is i. What is the maximum number of points that a fan may have in a simple graph on n points?

Suggested by G. Mészáros

(4 pont)

Deadline expired on 15 February 2008.


Sorry, the solution is available only in Hungarian. Google translation

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.


Statistics:

83 students sent a solution.
4 points: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 points:12 students.
2 points:4 students.
1 point:9 students.
0 point:11 students.
Unfair, not evaluated:3 solutions.
Unfair, not evaluated:1 solution.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley