Dostanete strom, označte co nejvíc vrcholů tak, aby žádné dva označené nebyly spojeny hranou. (Nápověda: Pro každý podstrom spočitejte dvě maxima: jedno pro případ, kdy kořen podstromu je označený, druhé když není.)
Dostanete strom, najděte v něm nejdelší cestu. Pozor, cesty ve stromech mohou vést jak "svisle" (mezi předkem a potomkem) nebo „napříč“ (mezi dvěma různými větvemi).
Zjistěte, zda zadaný neorientovaný graf je acyklický. Jak je to pro orientované grafy?