Kiss Gergely 10.o
FMG


Az 1-es csúcsból mint gyökérből lelógatom a fát.

Minden csúcsra definiálok egy rekurzív függvényt: ha az ő által felfüggesztett fát vennént a teljes gráfnak és ő lenne az 1-es csúcs, akkor hány utast tudna felvenni. Ezt így számolom:
  - Lemegyek minél több gyerekébe(ezt limitálhatja az aktuáls csúcsban lévő utasok száma) és rekurzívan végrehajtom a műveletet.
  - Ha még maradt utas az aktuális csúcsban, akkor minél több egyszerű "oda-visszákat" csinálok vele és a gyerekeivel (aktuális -> egyik gyerek -> aktuális -> egyik gyerek...).
  - Az aktuális csúcsban végeztünk, és felszedtük a lehető legtöbb utast a részfából.

Az 1-es csúcs kivételes eset, mert amikor az egész bejárás végén visszatérünk az 1-esbe, akkor a megkérkezéskor nem veszünk fel utast, tehát lehet üres az állomás. (Én ezt így értelmeztem és ez egy helyes értelmezése a leírásnak.)
Ezért az 1-es csúcshoz "odaképzelek" mégegy utast, és a végdő válasz f(1) - 1.


A rekurzió azért helyes, mert bármelyik csúcsból nézve átrendezhetjük úgy az utazások sorrendjét, hogy először az alatta lévő csúcsokat látogatjuk, aztán a elette lévőeket. Ez nem változtat a végeredményen.