Feladat: F.3209 Korcsoport: 18- Nehézségi fok: átlagos
Füzet: 1998/január, 41. 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 megoldásai: 1998/szeptember: F.3209

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.

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.