Feladat: F.3209 Korcsoport: 18- Nehézségi fok: átlagos
Megoldó(k):  Bárány Kristóf ,  Csirmaz Előd ,  Gueth Krisztián ,  Gyenes Zoltán ,  Győri Nikolett ,  Harangi Viktor ,  Horváth Gábor ,  Juhász András ,  Lippner Gábor ,  Pap Júlia ,  Pogány Ádám ,  Sarlós Ferenc ,  Szabadka Zoltán ,  Székelyhidi Gábor ,  Terpai Tamás ,  Tóth Ádám ,  Végh A. László 
Füzet: 1998/szeptember, 352. oldal  PDF file
Témakör(ök): Indirekt bizonyítási mód, Konstruktív megoldási módszer, Gráfok összefüggősége, Feladat
Hivatkozás(ok):Feladatok: 1998/január: F.3209

Egy n csúcsú összefüggő gráf minden élére egy valós számot írtunk, ezt nevezzük az él értékének. A gráf bármely útjának súlya legyen a benne előforduló legnagyobb értékű él értéke. A gráf bármely x, y csúcsára jelölje f(x,y) az x-ből y-ba vezető legkisebb súlyú út súlyát. Bizonyítsuk be, hogy az f függvény legfeljebb n-1 különböző értéket vesz föl.

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Tegyük fel indirekt módon, hogy van n különböző függvényérték. Egy függvényérték egy pontpárhoz, egy képzeletbeli élhez tartozik. Egy n pontú fának mindig n-1 éle van, tehát n képzeletbeli él között biztos van kör, azaz:
Léteznek olyan A1, A2, ..., Ak, Ak+1=A1 pontok, hogy az f(Ai;Ai+1) értékek (i=1, ..., k) mind különbözők. Azt is feltehetjük, hogy közülük f(A1;Ak) a legnagyobb. Ez azt jelenti, hogy bármilyen úton haladunk is A1 és Ak között, biztosan átmegyünk egy legalább x=f(A1;Ak) értékű élen. Most tegyük fel a következőt: Mivel x1=f(A1;A2)<x=f(A1;Ak), létezik olyan A1A2 út, amely legfeljebb x1 értékű éleken halad. Hasonlóan, mivel x2=f(A2;A3)<x, van egy olyan A2A3 út, amely legfeljebb x2 értékű éleken halad, stb; végül van egy olyan Ak-1Ak út, amely legfeljebb xk-1 értékű éleken halad. Ezen utakat egymás után fűzve kapunk egy olyan A1Ak sétát, amelynek minden éle kisebb értékű, mint x.
Most a következőt tesszük. Egy lépésben, ha van olyan A pont, amelyet többször is érint a séta, akkor az első és utolsó érintés közti részt elhagyjuk belőle. Ezt folytatva nyilván egy olyan A1Ak úthoz fogunk jutni, amely csak x-nél kisebb értékű éleket tartalmaz, és ez ellentmond annak, hogy f(A1;Ak)=x. Ezzel az állítást igazoltuk.

 Lippner Gábor (Fazekas M. Főv. Gyak. Gimn., 12. o.t.)