# Brodnikov problem

### Iz Wikipedije, proste enciklopedije

Brodníkov problém je znan problem iz teorije grafov in uganka. Brodnik mora na nasprotni breg reke spraviti kozo, volka 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.

  Ta matematični članek je škrbina. Slovenski Wikipediji lahko pomagate tako, da ga dopolnite z vsebino.

Vzpostavljeno iz »http://sl.wikipedia.org../../../b/r/o/Brodnikov_problem.html«

Kategorije: Matematične škrbine | Teorija grafov | Uganke

##### Views

- Članek
- Pogovor
- Trenutna redakcija

##### občestvo

- Portal občestva
- Pod lipo
- Stik z nami

##### podpora

- Pomoč
- Denarni prispevki

##### Iskanje