Feladat: F.2899 Korcsoport: 14-15 Nehézségi fok: könnyű
Megoldó(k):  Csorba Péter ,  Csörnyei Marianna ,  Dőtsch András ,  Faragó Gergely ,  Futó Gábor ,  Imreh Csanád ,  Kis Gábor 
Füzet: 1992/október, 299 - 300. oldal  PDF  |  MathML 
Témakör(ök): Fagráfok, erdők, faváz, Kombinatorikai leszámolási problémák, Permutációk, Feladat
Hivatkozás(ok):Feladatok: 1992/március: F.2899

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.

I. megoldás. Jelöljük a városokat A,B,C,D és E-vel. A négy szakasznak 4⋅2=8 végpontja van. Mindegyik végpont valamelyik városhoz tartozik, ezért lesz olyan város, amelyikből egynél több vasútvonal-szakasz indul ki. Ennek megfelelően három esetet különböztetünk meg.

 
 

1. ábra
 

1. Egy városból ‐ ábránkon ez a város A ‐ négy vasútvonal indul ki. Mivel A szerepét bármelyik város játszhatja, 5 ilyen vasúthálózat lehetséges.
2. Egy városból ‐ a 2. ábrán ez az A ‐ három vasútvonal indul ki.
 
 

2. ábra
 

E három szakasz A-tól különböző 3 végpontja közül valamelyik össze van kötve az ötödik várossal, ezért lesz egy olyan város is, amelyikből két szakasz indul ki. Azt a várost, amelyikből 3 vasútvonal indul ki, 5-féleképpen választhatjuk ki az 5 város közül, azt amelyikből 2 vonal indul ki 4-féleképpen, és a megmaradó 3-ból 3-féleképpen választható ki, hogy melyik lesz az előző mondatban említett ,,ötödik'' város. Ez 5⋅4⋅3=60 eset.
3. Mindegyik városból legfeljebb 2 vasútvonal indul ki. Ezt az esetet rajzoltuk meg a 3. ábrán.
 
 

3. ábra
 

Ha egy ilyen vasúthálózat szakaszait egymáshoz csatlakozóan bejárjuk, az öt várost egy permutációjuk sorrendjében érintjük. Ezek száma 5!=120, de a vasúthálózat szempontjából pl. az ABCDE és az EDCBA hálózatok azonosak; ezért a különböző lehetőségek száma most 12⋅5!=60.
Összesen tehát 5+60+60=125 vasúthálózatot találtunk.
Megjegyzés. A feladat (és a megoldás) megfogalmazható a gráfelmélet terminológiájával is. Problémánk azt jelenti, hogy hányféle 5 szögpontú fa lehetséges, vagy általánosan: hányféle n szögpontú fa létezik.
 

II. megoldás. A feladat általános megoldása megtalálható Reiman István: A geometria és határterületei c. könyvének 318‐319. oldalán. Az úgynevezett Cayley formula szerint az n csúcsú fák száma nn-2.