Brodnikov problem
Brodníkov problém je znan problem iz teorije grafov in uganka. Brodnik mora na nasprotni breg reke spraviti volka, kozo in zelje. Pri tem lahko v čolnu pelje le eno od obeh živali ali le zelje. Poleg tega ne sme na istem bregu pustiti koze same z volkom (23) ali koze same z zeljem (34).
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b8/Ferryman_problem.svg/530px-Ferryman_problem.svg.png)
Če na grafu označimo brodnika z 1, volka z 2, kozo s 3 in zelje s 4, ter s črkami povezave med stanji na začetnem bregu, ki predstavljajo brodnikove prehode prek reke, dobimo dve rešitvi:
- abcdefg
- abc1d1e1fg
Brodnik mora v obeh primerih opraviti vsaj 7 voženj in se mora vsaj trikrat vrniti na začetni breg (b,d,f/b,d1,f). Najprej mora vedno prepeljati kozo (a), (24). Enkrat tam pusti samega volka, drugič pa zelje (2/4). Dvakrat se pelje nazaj sam (b,f) in pri tem dvakrat pusti kozo samo na nasprotnih bregovih(124/3), enkrat pa se pripelje nazaj s kozo (d/d1). Kozo mora pri tem prepeljati vsaj trikrat (a,d,g/a,d1,g), da koza preživi.