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).

Graf »brodnikovega problema«

Č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

abc₁d₁e₁fg

Brodnik mora v obeh primerih opraviti vsaj 7 voženj in se mora vsaj trikrat vrniti na začetni breg (b,d,f/b,d₁,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/d₁). Kozo mora pri tem prepeljati vsaj trikrat (a,d,g/a,d₁,g), da koza preživi.