|
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 és -vel. A négy szakasznak 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 ‐ négy vasútvonal indul ki. Mivel szerepét bármelyik város játszhatja, ilyen vasúthálózat lehetséges. 2. Egy városból ‐ a 2. ábrán ez az ‐ három vasútvonal indul ki.
2. ábra három szakasz -tól különböző 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 vasútvonal indul ki, -féleképpen választhatjuk ki az város közül, azt amelyikből vonal indul ki -féleképpen, és a megmaradó -ból -féleképpen választható ki, hogy melyik lesz az előző mondatban említett ,,ötödik'' város. Ez eset. 3. Mindegyik városból legfeljebb 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 , de a vasúthálózat szempontjából pl. az és az hálózatok azonosak; ezért a különböző lehetőségek száma most Összesen tehát 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 szögpontú fa lehetséges, vagy általánosan: hányféle 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 csúcsú fák száma . |
|