Brodnikov problem

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search

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