     
P 46 (2018/2019) 54
Prečkanje reke
A T
Prečkanje reke spada med tiste vrste nalog, v ka-
terih moramo z majhnim čolnom z enega na drugi
breg reke prepeljati ljudi, živali ali predmete. Pri
tem imamo podane omejitve, koliko oseb, živali
oz. predmetov je lahko hkrati v čolnu ter v kakšni
družbi so lahko. Te vrste nalog navadno srečamo
pri logiki, lahko pa se jih lotimo tudi s pomočjo te-
orije grafov. Ne samo, da tako nalogo rešimo na
drugačen, zanimiv način, najdemo lahko tudi vse
možne rešitve in se prepričamo, katera med njimi
je najkrajša.
Volk, koza in zelje
Mož, ki je obiskal zelo posebno tržnico, se iz nje vrača
z volkom, kozo in zeljem. Na poti domov mora preč-
kati reko, vendar ima za to na razpolago le majhen
čoln, v katerega gre poleg njega samo še ena od stva-
ri, ki jih je kupil na tržnici. A koze ne sme pustiti
same z volkom, ker bi jo volk požrl. Prav tako ne
smeta ostati sama skupaj koza in zelje, saj bi koza
zelje pohrustala. Ali lahko mož vse varno spravi na
drugo stran reke?
Če ste se s tako ali podobno uganko že srečali, to
ni nič presenetljivega. Ljudje se namreč z njo ukvar-
jajo že od srednjega veka dalje. Prvič je bila zapisana
že konec 9. stoletja v latinskem rokopisu Propositio-
nes ad Acuendos Juvenes, ki predstavlja eno najzgo-
dnejših zbirk zabavne matematike. Od tedaj se je
pojavilo veliko različic te uganke. V eni izmed njih
poleg kmeta nastopajo lisica, goska ter vreča fižola,
spet v drugi panter, prašiček in ovsena kaša. Da-
nes jo v različnih preoblekah najdemo v računalni-
ških igricah, pojavila pa se je tudi v priljubljeni risani
seriji Simpsonovi, kjer Homer skuša čez reko prepe-
ljati Maggie, kužka in strup za podgane, ki izgleda
kot bonboni. V vseh raličicah uganke tako nastopajo
trije objekti A,B in C , pri čemer ne A in B ne B in C
ne smeta ostati sama brez nadzora.
Uganko lahko rešimo z naslednjim logičnim pre-
mislekom. Najprej mora mož na drugo stran reke
varno spraviti kozo, saj bo v nasprotnem primeru
volk pojedel kozo oz. bo koza pojedla zelje. Ko se
mož vrne, ima na izbiro, da prepelje na drugo stran
bodisi volka bodisi zelje. Če prepelje na drugo stran
volka in se sam vrne po zelje, bo medtem volk poje-
del kozo. Če pa prepelje zelje in se vrne po volka, bo
koza pohrustala zelje. To težavo lahko reši tako, da
na drugo stran odpelje volka ter s seboj nazaj vzame
kozo. Sedaj lahko prepelje na drugo stran še zelje in
se brez bojazni vrne po kozo. Mož tako reko prečka
sedemkrat v naslednjih korakih:
prepelje kozo,
se sam vrne nazaj,
prepelje volka,
nazaj grede vzame kozo,
prepelje zelje,
se sam vrne nazaj,
prepelje na drugo stran še kozo.
Rešitve uganke tako ni bilo posebej težko poiskati.
A radovedni ugankar se bo vprašal, ali je to edina
rešitev ali nemara celo obstaja rešitev, kjer bi se mož
čez reko peljal manjkrat. Odgovor na ti vprašanji
lahko dobimo s pomočjo teorije grafov.
     
P 46 (2018/2019) 5 5
Rešitve uganke Volk, koza in zelje s pomočjo
teorije grafov
Kako pojmujemo graf, je že bilo pojasnjeno v pre-
teklih številkah Preseka (zanimivo predstavitev upo-
rabe grafov lahko najdemo npr. v izdaji letnika 46).
Spomnimo se, da si pod grafom predstavljamo mno-
žico vozlišč (točk) ter povezav (črt) med njimi. Ozna-
čimo ga z G = (V(G), E(G)), kjer V(G) predstavlja
množico vozlišč, E(G) pa množico povezav grafa G.
Levi graf na sliki 1 predstavlja graf G, za katerega
velja V(G) = {a,b, c, d, e} in E(G) = {ab,ac, bc, bd,
cd,de}. Povezavo ab bi lahko označili tudi z ba,
saj je pomembno le to, da sta vozlišči povezani. Če
sta vozlišči povezani s povezavo, rečemo da sta so-
sednji. V grafu G sta a in b sosednji, rečemo pa
tudi, da je a sosed od b (in b sosed od a), vsi sosedi
vozlišča b pa so a, c in d.
Če vsako povezavo usmerimo od enega vozlišča k
drugemu, govorimo o usmerjenem grafu. Usmerje-
nemu grafu rečemo tudi digraf. Običajna oznaka za
digraf jeD = (V(D),A(D)), kjer je V(D)množica vo-
zlišč, A(D) pa množica usmerjenih povezav digrafa
D. Primer digrafa vidimo desno na sliki 1. Zanj ve-
lja V(D) = {a,b, c, d, e}, množica usmerjenih pove-
zav pa je enaka A(D) = {(a, b), (a, c), (b, c), (c, d),
(d, b), (e, d)}, kjer smo s posebnim zapisom (a, b)
hoteli poudariti usmerjenost povezave med vozliš-
čema a in b; ta povezava je usmerjena od vozlišča
a do vozlišča b. Če bi pisali (b,a), bi to pomenilo
ravno nasprotno usmerjenost.
Spoznajmo še pojem sprehoda v grafu oz.
digrafu. Tega si lahko predstavljamo kot zaporedje
vozlišč, ki nam določa, po kakšnem vrstnem redu
se po povezavah »sprehajamo« od vozlišča do vo-
zlišča. Primera sprehodov v grafu G na sliki 1 sta
abcde in abcdedc. Ker nam v primeru digrafov pu-
ščice nakazujejo, v katero smer je možno prehoditi
povezavo, govorimo o usmerjenih sprehodih. V di-
grafu D sta primera usmerjenih sprehodov abcd in
abcdbc. Opazimo, da ne obstaja usmerjeni sprehod
od vozlišča a do vozlišča e, saj lahko po povezavi
med d in e gremo le v smeri od e proti d, ne pa tudi
obratno.
Sedaj lahko uganko Volk, koza in zelje predsta-
vimo v jeziku teorije grafov. Graf, ki ustreza tej
uganki, bomo tvorili tako, da bo vsako stanje pred-
stavljalo eno vozlišče. Recimo, da so na začetku
vsi (mož, volk, koza in zelje) na levem bregu reke.
To stanje bomo predstavili z vozliščem a. Obratno,
končno stanje, ko so torej vsi na desnem bregu reke,
označimo z b. Premislimo, kakšna stanja so še do-
voljena. Mož seveda ne sme biti sam na enem bregu
reke, saj bi bili preostali na drugem bregu brez nad-
zora. Lahko pa je na enem bregu reke sam volk, pre-
ostali pa se nahajajo na drugem bregu reke. Pri tem
stanje, ko je volk na levem bregu, ostali pa na de-
snem, označimo s c, obratno stanje, ko je volk sam
na desnem bregu, pa z d. Podobno dobimo še sta-
nja e, f , g,h, katerih pomen je razviden iz tabele 1
(v tej tabeli M predstavlja moža, K kozo, Z zelje in
V volka). Ko smo ugotovili vsa možna stanja, v ka-
terih je na enem bregu le en sam, smo seveda tudi
opisali že vsa stanja, ko so na bregu trije. Tako nam
ostanejo le še stanja, v katerih sta dva na enem, dva
pa na drugem bregu. Toda to je možno le, če sta na
enem bregu skupaj mož in koza, na drugem pa volk
in zelje. Ti stanji v tabeli 1 najdemo pod oznakama
i in j. Tako bo imel naš graf 10 vozlišč.
a
b
c
d
e a
b
c
d
e
SLIKA 1.
Graf G (levo) in digraf D (desno)
     
P 46 (2018/2019) 56
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
j MK ZV
i ZV MK
h MKV Z
g Z MKV
f MZV K
e K MZV
d MKZ V
c V MKZ
b MKZV
a MKZV
stanje levi breg desni breg
TABELA 1.
Tabela stanj
Sedaj se lotimo še iskanja povezav. Dve vozlišči
(stanji) bomo povezali le, če je glede na omejitve
iz naloge možen prehod iz enega stanja v drugega.
Tako je npr. možen prehod iz stanja a v stanje i, saj
lahko mož prepelje kozo na desni breg, volk in zelje
pa ostaneta na levem bregu. Seveda je možen tudi
obraten prehod, torej iz stanja i v stanje a, saj se
lahko mož in koza vrneta na levi breg. Zato bomo v
grafu narisali povezavo med vozliščema a in i. Ne
moremo pa npr. povezati vozlišč a in f , saj bi to po-
menilo, da se je koza sama peljala s čolnom. To se-
veda ni možno, saj lahko s čolnom upravlja le mož.
Vozlišča a tudi ne moremo povezati z vozliščem b,
saj na čolnu ni prostora, da bi se vsi štirje prepe-
ljali hkrati. Hitro lahko ugotovimo, da je vozlišče
a mogoče povezati le z vozliščem i. Nato se lotimo
premišljevanja, s katerim vozliščem lahko povežemo
vozlišče b, sledi premislek glede vozlišča c itd. Tako
sistematično pridemo do vseh povezav v grafu, ki je
prikazan na sliki 2.
Da bi poiskali rešitev uganke, je torej potrebno
najti sprehod med vozliščema a in b. Iz grafa hitro
razberemo, da je takih sprehodov dejansko zelo ve-
liko (eden je npr. sprehod aifchedgfchejb).
Najkrajša sprehoda pa sta le dva. To sta sprehoda
aifchejb in aifgdejb. Oba sta dolžine 7 (dolžino
sprehoda dobimo tako, da preštejemo število pove-
zav sprehoda), kar ustreza najmanjšemu številu vo-
a i f
c h
e j b
g d
SLIKA 2.
Graf uganke Volk, koza in zelje
ženj, ki jih mora opraviti mož, da vse prepelje na
drugo stran reke. Rešitvi, ki smo jo dobili v prej-
šnjem razdelku, ustreza sprehod aifgdejb.
Misijonarji in ljudožerci
Trije misijonarji in trije ljudožerci morajo prečkati
reko. Na razpolago imajo majhen čoln, v katerem
sta lahko hkrati največ dve osebi. Če so na kateri-
koli strani reke prisotni misijonarji (pri čemer je mi-
šljeno, da se lahko nahajajo na samem bregu ali še
v čolnu), jih mora biti več ali enako število kot ljudo-
žercev. V nasprotnem primeru ljudožerci misijonarje
pojedo. Kako lahko vseh šest ljudi varno prečka reko?
Nalogo lahko rešimo z naslednjimi koraki.
En ljudožerec in en misijonar prečkata reko.
Misijonar se vrne na prvotno stran reke.
Dva ljudožerca prečkata reko.
Eden od njiju se vrne.
Dva misijonarja prečkata reko.
Vrneta se en ljudožerec in en misijonar.
Dva misijonarja prečkata reko.
En ljudožerec se vrne na prvotno stran reke.
Dva ljudožerca prečkata reko.
En ljudožerec se vrne na prvotno stran reke po
zadnjega ljudožerca.
Oba ljudožerca se pridružita vsem preostalim ose-
bam na drugi strani reke.
Spet nas bo zanimalo, ali poleg te rešitve obstaja
še kakšna. Ali morda obstaja rešitev, kjer bi bilo po-
trebno manjše število prevozov kot 11, kolikor je po-
trebnih v zgornji rešitvi?
     
P 46 (2018/2019) 5 7
Rešitev s pomočjo grafa
Po zgledu prejšnje naloge bi lahko misijonarje ozna-
čili npr. z A,B,C , ljudožerce pa z X,Y ,Z ter s po-
močjo teh oznak zapisali vsa možna stanja. Ker pa
misijonarjev ni treba ločiti med sabo in prav tako ne
ljudožerev, saj je pomembno le njihovo število na
posameznem bregu (glede na besedilo naloge se pri
tem štejejo tudi potniki, ki so ob bregu na priveza-
nem čolnu), bo za zapis vseh stanj zadostoval za-
pis s pomočjo urejenih parov. Tako bo urejeni par
(m,k) predstavljal stanje, ko se na levem bregu reke
nahaja m misijonarjev in k ljudožercev. Stanj na de-
snem bregu reke nam ni treba posebej opisovati, saj
vemo, da mora biti skupno število misijonarjev in
ljudožercev v vsakem trenutku enako 3. Ker velja
0 ≤m ≤ 3 in 0 ≤ k ≤ 3, obstaja 16 možnih urejenih
parov (m,k). Toda nekatere od njih je potrebno iz-
ločiti, npr. par (1,3), saj v tem primeru število ljudo-
žercev na levem bregu presega število misijonarjev.
Prav tako je treba izločiti par (2,1), saj to pomeni, da
sta na desnem bregu dva ljudožerca, misijonar pa le
en. Opazimo, da so torej dovoljeni le pari (m,k), ki
zadoščajo naslednjim pogojem:
0 ≤m ≤ 3,
0 ≤ k ≤ 3,
m = k ali m = 0 ali m = 3.
Za boljše razumevanje si jih lahko predstavimo z
diagramom na sliki 3, kjer so vsa možna stanja pred-
stavljena s točkami, pri čemer so dovoljena stanja
tudi obkrožena.
Sedaj premislimo, med katerimi dovoljenimi sta-
nji je mogoče prehajati glede na omejitev, da se s
čolnom lahko peljeta največ dve osebi. Če je prehod
iz enega stanja v drugega možen, bomo v grafu, kjer
vozlišča predstavljajo stanja, ustrezni vozlišči pove-
zali. Povežemo lahko npr. vozlišči (3,3) in (3,2), saj
se lahko en ljudožerec pelje iz levega na desni breg,
ali pa tudi obratno. Vozlišče (3,3) lahko povežemo
še z (2,2), kar bi v primeru sprehoda po tej povezavi
od (3,3) do (2,2) pomenilo, da sta se en misijonar
in en ljudožerec peljala z levega na desni breg. Če
pa bi se po omenjeni povezavi sprehodili v smeri od
(2,2) do (3,3), bi to pomenilo, da sta se ljudože-
rec in misijonar peljala z desnega na levi breg. Pri
m
k
0 1 2 3
0
1
2
3
SLIKA 3.
Diagram (dovoljenih) stanj
iskanju vseh vozlišč, ki so sosednja z danim vozli-
ščem (m,k), nam pomaga premislek, da bo prevoz
čolna z levega na desni breg zmanjšal vrednosti m
in k. Števili m in k se skupaj zmanjšata za največ
2, saj lahko gresta hkrati na čoln največ dva človeka.
Tako so kandidati za sosede vozlišča (m,k) vozli-
šča (m−1, k−1), (m,k−2), (m−2, k), (m−1, k) in
(m,k − 1), pri čemer posamezna možnost ne pride
v poštev, če je v urejenem paru prvo število manjše
od drugega ali pa je katero od števil negativno. Tako
dobimo graf, prikazan na sliki 4.
(0,0)
(0,1)
(0,2)
(0,3)
(3,0)
(3,1)
(3,2)
(3,3)
(2,2)
(1,1)
SLIKA 4.
Graf uganke Misijonarji in ljudožerci
     
P 46 (2018/2019) 58
Cilj naloge je poiskati usmerjeni sprehod iz vozli-
šča (3,3) do vozlišča (0,0). Morda nam pritegne po-
zornost kratek usmerjeni sprehod (3,3)(2,2)(1,1)
(0,0). Toda tako zaporedje vozlišč nam da tri pove-
zave (prva je povezava(3,3)(2,2), druga (2,2)(1,1)
in tretja (1,1)(0,0)), ki vse ustrezajo vožnjam čolna
z levega na desni breg, kar seveda ne more biti reši-
tev. V prejšnji nalogi smo se lahko po povezavah
sprehajali poljubno, saj so vozlišča ustrezala tako
stanjem na levem kot na desnem bregu reke. V tokra-
tnem grafu pa vozlišča predstavljajo le stanja na le-
vem bregu. Kako torej poiskati sprehod od vozlišča
(3,3) do vozlišča (0,0), da bo upoštevana izmenič-
nost voženj čolna z levega na desni breg in obratno?
Poiskali bomo usmerjeni sprehod, kjer bomo pazili
na ustrezno usmeritev povezav. Opazimo namreč
lahko naslednje: če v grafu »vertikalno« povezavo
usmerimo od spodaj navzgor (taka je npr. povezava
med vozliščema (0,0) in (0,2)), to pomeni povečanje
števila ljudožercev na levem bregu, zato taka pove-
zava predstavlja prevoz (ljudožercev) z desnega na
levi breg. Če »vodoravno« povezavo usmerimo od
leve proti desni (taka je npr. povezava od (0,2) do
(2,2)), to ustreza povečanju števila misijonarjev na
levem bregu, kar ponovno pomeni vožnjo čolna z de-
snega na levi breg. Po podobnem premisleku o preo-
stalih možnih usmeritvah pridemo do ugotovitve, da
prevozom z desnega na levi breg ustrezajo usmeri-
tve:
↑ (od spodaj nazgor),
→ (od leve proti desni) in
ր (od spodaj levo do zgoraj desno),
prevozom z levega na desni breg pa ustrezajo usme-
ritve:
↓ (od zgoraj navzdol),
← (od desne proti levi) in
ւ (od zgoraj desno do spodaj levo).
S pomočjo tega po krajšem premisleku najdemo us-
merjeni sprehod
(3,3)(2,2)(3,2)(3,0)(3,1)(1,1)(2,2)(0,2)(0,3)
(0,1)(0,2)(0,0)
na sliki 5, ki ustreza rešitvi, ki smo jo že navedli v
razdelku Misijonarji in ljudožerci.
(0,0)
(0,1)
(0,2)
(0,3)
(3,0)
(3,1)
(3,2)
(3,3)
(2,2)
(1,1)
SLIKA 5.
Ena od možnih rešitev
Spet nas bo zanimalo, ali je to edina rešitev ali
nemara obstaja še krajša. Do odgovora pridemo s
pomočjo grafa na sliki 4, v katerem bomo za lažjo
razlago vsa vozlišča grafa razporedili v tri množice:
L = {(0,0), (0,1), (0,2), (0,3)},
S = {(1,1), (2,2)},
D = {(3,0), (3,1), (3,2), (3,3)}.
SLIKA 6.
Preostale rešitve uganke
     
P 46 (2018/2019) 5 9
Ker ni nobene povezave med vozliščem iz množice
D in vozliščem iz množice L, mora iskana usmer-
jena pot od vozlišča (3,3) do vozlišča (0,0), ki bo
predstavljala rešitev naloge, nujno vsebovati vozli-
šče iz množice S. Če bi se v vozlišče (2,2) premaknili
iz vozlišča (3,3) ali (3,2), se moramo v naslednjem
koraku premakniti v vozlišče (3,2) ali (3,3). Tako
hitro vidimo, da mora iskani usmerjeni sprehod po
tem, ko zapusti vozlišča iz D, nujno iti preko vozli-
šča (1,1), edini možni način za to pa je preko vozli-
šča (3,1). Edini možni način, da iz (1,1) pridemo do
nekega vozlišča iz L, je, da se iz (1,1) premaknemo v
(2,2) in nato v (0,2). Tako bo iskani usmerjeni spre-
hod zagotovo vseboval zaporedje (3,1)(1,1)(2,2)
(0,2). Od (3,3) do (3,1) je možno priti na dva raz-
lična načina: preko zaporedja (3,3)(3,1)(3,2)(3,0)
(3,1) ali (3,3)(2,2)(3,2)(3,0)(3,1). Prav tako ob-
stajata le dva različna načina, kako iz vozlišča (0,2)
doseči vozlišče (0,0). Tako ugotovimo, da obstajajo
natanko štiri različne rešitve uganke. Eno od rešitev
smo že videli na sliki 5, preostale prikazuje slika 6.
Vse štiri rešitve zahtevajo 11 voženj čolna.
Nalogi, ki smo si ju ogledali, najdemo tudi na sple-
tni strani www.nauk.si/materials/418/out/
index.html#state=1, kjer je še več zanimivih
ugank. Morda koga zamika, da se s pomočjo teorije
grafov loti še katere.
Literatura
[1] River crossing puzzle, dostopno na
en.wikipedia.org/wiki/River_crossing_
puzzle.
[2] Fox, goose and bag of beans puzzle, dostopno
na en.wikipedia.org/wiki/Fox,_goose_
and_bag_of_beans_puzzle.
[3] Prečkanje reke, dostopno na www.nauk.si/
materials/418/out/index.html#state=1.
[4] Robert Fraley, Kenneth L. Cooke in Pe-
ter Detrick, Graphical Solution of Diffi-
cult Crossing Puzzles, Mathematics Ma-
gazine, 39 (1966), 151–157, dostopno na
https://www.jstor.org/stable/2689307?
seq=1#metadata_info_tab_contents.
×××
Naloge na
Plemljevi
maturi
M R
Akademik prof. dr. Josip Plemelj (1873–1967),
svetovno znani matematik, prvi rektor ljubljanske
univerze, je obiskoval osemrazredno klasično gi-
mnazijo v Ljubljani in na njej uspešno maturiral v
šolskem letu 1893/94. Pot do njegove mature pa ni
bila gladka, ker se v zadnji razred zaradi incidenta
(podrobnosti so opisane v [3]) ni mogel vpisati. Kot
privatist je opravljal izpite za prvo polletje osmega
razreda na gimnaziji v Novem mestu, za drugo pol-
letje pa na gimnaziji v Ljubljani, kjer je tudi matu-
riral.
Gimnazije so na koncu šolskega leta objavile po-
ročilo o svojem delu. Letna poročila ljubljanske kla-
sične gimnazije, ki jo je obiskoval Plemelj, so bila
tiskana, napisana pa so bila v nemščini. V poročilih
so bili objavljeni seznami profesorjev in dijakov po
razredih, seznami vsebin predmetov, potrebnih uč-
benikov, učil, poljudnih predavanj, šolska statistika,
pa tudi maturitetne naloge. Na začetku poročil je bil
daljši znanstveni prispevek kakega profesorja, v po-
ročilu za šolsko leto 1894/95 npr. o lomu svetlobe
v Zemljini atmosferi z upoštevanjem spremenljivega
lomnega količnika avtorja Matevža Voduška.
Kot je razvidno iz letnih poročil [1, 2] ljubljanske
gimnazije, so potekali pisni maturiteni izpiti v po-
letnem roku od 11. do 16. junija, ustni izpiti pa so
se začeli 9. julija in končali 14. julija 1894. Za ta