i
i
“444-Pisanski-naslov” — 2009/6/10 — 9:55 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 7 (1979/1980)
Številka 4
Strani 226–236
Tomaž Pisanski:
NAJCENEJŠE DREVO
Ključne besede: matematika, računalništvo, kombinatorika, teorija
grafov, najcenejše drevo, Primov postopek, omrežja.
Elektronska verzija: http://www.presek.si/7/444-Pisanski.pdf
c© 1980 Društvo matematikov, fizikov in astronomov Slovenije
c© 2009 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
NAJCENEJšE DREVO
Pred kratkim so zgrad ili novo šo lo . Le po so j o op r emi li. Ko pa
s o postavil i zadnjo klo p v u čiln i c o , j e zmanjka l o den a r ja , ok2
li ca pa je b i l a še neu rejen a. Ravnatel j s i je v obupu puli l
redke lase na glavi, s a j se je neusmiljeno bli žal dan sve čane
otvoritve nove š ol e , okr og š ole pa še kup i blata ! šo l i pri pada
ve liko dv orišče. Le kdo bi ga hi t ro in le po ur ed il - pa še
br e z pl a čila ?
Na pomoč s o p r iskoč i l i u če n c i ! Na s est an ku šo lsk e skup nost i so
se d ogovori li, da bodo s ami ur ed i li d v or išče . Napra v i l i so na-
č rt (S lika 1) .
Skle n i l i s o, da bodo posej al i tra vo. Pos t avili bodo spomenik -
s kulptu r o , ki j e na lans ki o b či n ski razst avi - še v s t ari š ol i
STR. VRATA
ISPOME- INIK
IGRIŠČE ZA KOŠARKO
ŠOLSKO
POSLOPJE
VRATA NA DVORIŠČE
L. --I
GL
. VR.~A::.T.:.::A=-- -------...J..--------.
Slika 1: N ačrt šo l sk ega dvori šča , ki 5 0 ga izdel ali u čenci na ses t a nku
šo l s ke s kupnosti.
226
o
- dob i la pr vo nag rado. Kasneje bodo ur ed il i igr~ sce za ko šar -
ko . Sta r i hra s t bo kot n al a š č za plezanje. Pos ta vi l i bodo t ud i
telovadno orodje : dva droga in kroge. V bli žini zgradbe bo s k~
pina klopi. Za dostop na dvor išče bodo uporabi li že obstoječa
glavna i n stran ska vr a t a i n vrata iz š o l s k e g a poslop ja na dvo -
rišče .
Z de lom so pohite l i i n t rava je že zače la poganj at i. Ne na do ma
s o se učenc i spomni li, da niso za črta l i stezic . Stezice so nuj
no potrebne, saj bo drugače tra va kma l u uniče na. Ker je pese k
dra g, pa t udi de lo je napo rno, so se dogo voril i, da bodo s t e z i
ce nape lja l i , ka r s e da v a rčno . Ne pot reb ni m k r iž išče m S 2 bodo
izogni l i, ker je ureditev križ išč še pos e be j teža vna.
Poveza t i morajo spomeni k, telovadno orodje, hrast, s kupino kl Q
pi i n košarkarsko i g ri š č e z g la vn imi in s t r a ns k i mi vrat i ter s
šolsk im pos lopjem . Pr i te m mora jo seveda varčevat i s pes kom i n
s voj imi močm i . Opaz i l i so , da nal oga ni lahka, zato so jo pre-
pustili matematičnemu krožku , ki že vrsto l et uspešno de luje
na š ol i .
o
o
Sl i ka 2: Pr v i načr t šo lskega d vori šča , ki so ga i zdel al i kr ožka r j i v s re do
po pouku.
227
Matemati ki so se sestali v s r edo po pouku . Pred s e bo j so i me l i
jasno in uporabno nalogo. D okon č ati morajo n ačrt. Naloga j e bi
la zelo nen avadna in ni so š e s r eča l i podobne. Zat o so se je 1Q
t ili z vso pre vidnos t jo. Na j pr ej s o sli ko poeno s t av ili . Odmi-
s l i 1i s o si vse , kar j e za re ševanje nebistv enega . Nar is a1 i s o
nov na č rt (Sli ka 2). Obje kte na načrtu s o t a kole označil i :
za por ed na
števil ka ozna ka ob je kt
1 H hra st
2 I igriš če za košar ko
3 SV str an ska vrata
4 TO t elovadno or odj e
5 S spomen ik
fi SK sk upi na klopi
7 GV glavna vrata
8 Š šola (vrata na dvori-
šče)
Tehle os em obj ek t ov je t reba med seboj povezati. Povezali jih
bodo seveda z ravnimi črtami, saj je ravna č r t a kr aj ša od kri-
ve. Izbranim ob jektom s o krožkarji re kli točk e , ste zicam , oz i -
r om a čr ta m med njimi pa p ove z av e . č e bi pove zali vsa k pa r to č k
s s te z ico, bi potrebovali 8 . 7/2 = 28 povezav. Eden od kr ožka r:
jev je rek e l : "Seved a, č e bi imeli n t očk, bi potrebovali
n (n - 1) /2 povezav, toliko kot je v n - k o ~n i k u stranic in dia-
gonal ". Jasno je bilo , da vseh 28 s t e z ic ne bodo potrebovali .
č e bi n amr eč z ač rtali ste zic i od str ans kih vrat do t elov adnega
orod ja in od t am napre j d o igri š č a za koš ar ko , teda j ne potre-
buj ejo s te z i c e od stra ns kih vrat do košar kar skega igr i š č a!
(Slika 3 )
Sli ka 3:
228
Nekatere od 28 možnih
s te zic so odveč. ~SV 1
V dnevn ik matematičnegakrožka s o zapisali: Koliko (najmanj)
povezav p o tr e bu j e mo, da pove žemo 8 to čk v skupino? Koliko pov~
z av potrebujemo , da pove že mo n to čk?
Po preizkušanju so se zedinili in svojo ugotovitev zabelež ili:
Potrebu jemo 7 pove zav in v splošnem , če ž e l i mo povezati n točk ,
potrebu jemo n -l povezav. (Če bo čas, bomo to tudi dokazali .)
Obogateni z novim spoznanjem so se pogumno l ot i l i načrtovanja
"si stema stezic" na šo l s kem dvorišču . Načrt, ki so ga dobili,
prikaz uje s lika 4.
Z načrtom pa niso bi l i zadovo ljni. Opazili so , da n i najbo ljši .
če bi stezico od stranskih vrat (SV) do košarkarskega igrišča
(1) nadomest i li s krajšo stezi co od te lovadnega orodja ( TO) do
spomenika (S), bi prihrani li pesek in de lo . Na loga, ki so jo
reševali, je bila težja, kot so sprva menili . Zato so krožkar -
j i pok lical i na pomo č mentorja. Ko so ga seznan i li s prob le -
mom, jim je povedal, da pravijo matemat ik i struktu ram, sestav -
ljenim iz točk in povezav grafi . če nos ijo povezave vrednosti
(npr. do lžine, cene, kapa c itete), pa jih imenujejo vrednostni
S1i ka 4: S istem sedmih stezi c , ki
povezuje točke, vendar pa
ni najbo ljši.
22 9
g r a fi al i omrežja . Krož karje so začel i grafi zanimati. Mentor
jim je naročil, naj si v š ols ki knji žni ci ogleda j o s t ar e š t e -
vilke Pre s eka in naj poiš čejo vse prispevke v zve zi z grafi.
Sam pa je obl j ubi l , da s e bo poz animal o re šitvi tega problema .
Do gov orili so se za sestanek naslednji dan , sa j j e bil o le ma-
l o ča s a na razpolag o .
Na če t rtkov se st anek je pr eds ednik kr ožka pr i nes e l s s e boj ko-
pico Prese kov. Našli so prece j pr i s pevkov , v kat e r i h j e mog o č e
zas l ed it i grafe .
Nas l ov č l a n k a Letni k St r an
SIM Pl /4 175
Problem iz igre SIM P2/1 43
Labirint P3/ 1 in ov i t e k
P3/3 ovitek
Uporovna vezja P3/4 186
Naloge P4/1 in 48
P4/2 100
Problem o barvanju kart P5/2 73
Nekaj o grafih in
njihovi uporabi P6/1 24
~1 a t e m a t i ka in š a h P6/ 2 71
Mento r pa je v m atema t ični knj i žni c i na J ad r ans ki 19 v L jublj~
ni nabral nekaj knj i g o grafih. Kr ož karj i so se ta koj poglobi-
li v študij grafov. Graf j e p o vezan , č e j e mog o če iz poljubne
točke v njem priti po pove zavah v vsa ko dru go toč ko. Seveda so
jih povezani grafi najbolj zanimali. Sošol ci s o jim zabi čali,
da ne marajo pohojene trave!
Kmalu so spoznali kup novih i zrazov. Seznanili so se s c ik li.
Cikel dobimo, če vzamemo oglišča mnogokotn ika za to čke, stran!
ce mnogokotnika pa za povezave grafa . če izh ajam o iz m- kot n i ka,
dobimo Cm' cikel n a m t o č k a h. če ciklu odstranimo povezavo,
dobimo graf, ki mu rečejo p o t . Iz Cm dobimo t ako Pm , pot n a m
to č k a h . C i k e l Cm ima m točk in m povezav, pot Pm pa ima m točk
230
CIKLI r. o o
C, C. Cs
POTI O !p,
p,
51 i ka 5: e ik 1i i n pot i
51 ika 6: Pr imer drevesa na 18 točkah . Narisa l i smo ga na dva n ač in a.
2 3
7 8
4 5 6
13
16
17
i n m- 1 povezav . Cm in Pm sta povezana grafa . Pot Pm je le pos~
ben primer drevesa. Dr evo na m točkah je vs a k povezan graf z m
točkami i n m- 1 povezavami . Drevo ima zan imi ve lastnos ti :
- če mu odvza me mo kateroko li povezavo , dobimo gra f, ki ni
pove za n
- dr evo ne vs ebuj e noben ega c ik la
- če dreves u dod amo š e kakšno pove za vo, dobimo gra f , ki vs ~
bu j e c ikel.
23 1
če si drevesa narišemo, opazimo, da spomlnJaJo na prava dreve-
sa, od tod tudi "čudno" ime, ki ga nosijo (Slika 6).
Kr ožk a r j i so zdaj dokončno razumel i, kaj pravzaprav i ščejo. Na
izbr an i h ose m to č k mor aj o nape ti drevo, tak o da bo cena , t o j e
vsota dol žin vseh sedmih povez av, najman j ša . Mentor je v ne ki
knjigi na še l t a pr obl em z imenom: .pr ob l em naj c e nejše g a drev es a.
Zraven je bi la t udi sp lošna rešitev tega problema, ki jo j e l~
ta 1957 na š el R. Prim in se po njem imenuje Primov postopek
( a l g or i t em) za kon s t r ukc ijo najcen ej še ga dreve s a. Pr i mov pos t Q
pe k gradi naj cenej še drevo po kora kih. Z a čne s poljubno t očko,
potem pa v sak i č doda to čko in povezavo, dok ler ne povež e vseh
točk med seboj.
PRIMOV POSTOPE K: Na z a čet k u imamo n t o čk v ra vnini. Nobe n pa r
toč k ni med seb oj povez an. Na konc u dobimo naj cen ej še d r ev o .
l . korak: Izberi pol jubno to č ko. Imenuj jo p ov ezani de l. Pr eo-
sta le točke imenuj nepovezani de l .
2 . kor a k: Dokler je nepove zan i del neprazen, ponavlja j:
2. 1: V povezanem delu izberi toč ko x , v ne poveza nem
delu pa toč k o y ta ko, da bo razdalja med njima
najmanj ša.
2 . 2 : Pove ži x in y s povezavo in prenesi y iz ne po
vezan eg a dela v povezani del .
U č e n c i s o te meljito premislili delov an je tega postop ka in so
se l ot i l i dela. Natančno so izmerili r a zda l j e med posameznimi
točkami. Izmerjene razda lje so vnesl i vrazprede lni co:
H I SV TO S SK CV Š
H 7,62 3 , 16 4, 47 6 ,4 0 8 , 60 9, 85 12, 81
I 7,62 8 , 00 3 , 16 3,61 2 , 00 6,71 5, 83
sv 3,16 8 , 00 5,10 5,3 9 8, 25 7, 81 12,08
TO 4 ,4 7 3 , 16 5 ,10 3 , 00 4, 24 7, OO 8 , 49
S 6 , 40 3,16 5 ,3 9 3 , 00 3 , 00 4 , 00 6 ,71
SK 8 , 60 2, OO 8 ,25 4, 24 3 , 00 5,0 0 4,24
CV 9, 85 6,71 7, 81 7, OO 4,00 5,00 6,0 8
Š 12 , 81 5, 83 12 ,0 8 8 , 49 6, 71 4, 24 6,08
232
Za zač etno t o č k o (glej 1. kor a k Primove ga postop ka!) so si i z-
br a l i šo lo (Š) . V povezanem delu je sedaj sa mo šola . Iz zad nje
vrstic e razpr edelnice s e lepo v id i , da j e SK najbliž je Š , zato
so dod a li poveza vo med šolo i n sk upi no klop i . V novem poveza -
ne m de lu s ta sedaj šo la in sku pi na klop i (2. korak posto pka ) .
Naj bl i žje šo li a l i sk up i ni klo pi je ig ri š č e ... Celot ni potek
post opka pr ikaz uj e nasled nj a r azp re de ln ica :
Zapored na Povezani de l Nepoveza n i de l Toč k a Točk a Razdal j a
štev i lka x y
1. Š SK,I,S, GV, TO,H, SV Š - K 4,24
2. Š,SK I ,S, GV, TO, H, SV SK - I 2,00
3. Š,SK, I S , GV, TO, H, SV SK - S 3,00
4. Š, SK, I , S, GV,TO, H,SV S - TO 3,00
5. Š, SK, I , S , TO, GV, H, SV S - GV 4,00
6. Š,SK,I,S, TO,GV H,SV TO - H 4,47
7. Š, SK, I , S, TO,GV,H SV H - SV 3, 16
Š, SK,I, S , TO, GV, H, SV
cv
SI i ka 7 : Dokon čni na črt šo lskega d vori šča . Skupna do l žina stez ic je 23 .8 7 .
To j e naj bolj ša re ši t ev.
233
Vsot a dol žin vseh s t e z i c v drev esu je:
4,24 + 2,00 + 3,00 + 3,00 + 4,00 + 4,47 + 3 , 16 = 23, 87 enot .
To je ce na naj cenejšega dr eve sa. Učenci so se prepr iča l i , da
bi dobili isto drevo , če bi zače li s kak šno drugo točko, le PQ
vezave bi vstop ale van j v drugačn em vr s tnem redu .
Kr ožk a r j i so napravil i do kon čni n ačrt ( s li ka 7). St ev il ke pr i
povezavah povedo, po ka kš ne m vr s tnem redu so se odločali zanje.
Mlad i matema tiki s o bi li z r e š i t vi j o zadovolj ni , saj so oprav i
l i koristno de lo : seb i in sošo lcem so prihrani li napor, šoli
pa denar . Tu je na še zgodbe konec . Ni pa š e konec uporabe Pri-
movega postopka.
Oglejmo si sorod en problem. Na sliki 8 je naris ano ces t no omre
žje, ki povezuje kr a j e A, B, C, D, E, F in G.
Tel efons ko pod j et j e se je nam e nil o povezat i me s t a v te lefonsko
omrežje. Zaradi la žjega vzd ržev anj a so se odločili , da bodo te
Sl ika 8 : Cestno omrežje. Stevilke ob ces t ah pomen ijo razdalje.
234
lefons ki kabl i pote kal i ob obsto ječ ih cestah . Spet je treba P9
is kati najcenejše omrežj e, spet je tu problem najcenej šega dr~
vesa . Naloga je l e malo drugačna od prve. Zdaj mo ramo namreč
poiskati najcenejše drevo na že o b sto je čem vrednostnem gra fu .
V drevo smemo vključiti l e obstoje če pove zave. Tako npr. ne
s mem o na pe l j at i kab la ne posred no od mesta A do mes ta G. Pr i mo v
pos t ope k pa deluje pravi l no t udi v t em pr i meru . Sli ka 9 nam ka
že najcenejše dre vo . Telefon s ko podjetje bo pot rebov alo 165 km
kab la.
Primov postope k nam v povezanem gra f u v vsakem primer u p oišče
najcenejše drevo . če ima več povezav v gra fu isto ceno (vred -
nost), se lah ko zgod i, da obst aj a več na j cenejših dreves . Po-
stope k nam v tem primeru izbere eno od njih .
V resnici je pr va nalo ga l e poseben primer dru ge . če imamo nam
r e č n točk v ra vnin i in poljub ni dv e med njimi povežemo z da-
lji co, dob i mo polni g r a f Kn na n točkah. Poveza ve (s kupaj j ih
je n (n - 1) / 2 ) nosijo vrednosti , ki s o v tem primeru kar do lži
......... ....... --------
I
I
I
/
/
/
/
/
./
./
SI i ka 9: Načrt za nape ljavo telefonskih kab lov. Skupna do lžina kabl a je
165 km.
235
A A A
B
Slika 10: Pri mov pos topek najde v g ra fu ( 1) na jceneJ se drevo (2) do lžine
2a, medtem ko je mogoče dodat i točko S v središču t r ikotnika
ABe i n dob iti cenej še , Ste i ne rjevo drevo z do lž ino 1,73a (3).
ne dalj ic . V dru gi nalogi imamo opr avka s splošnim grafom, v
katerem vr ed nost i povezav niso nuj no dolžine da lj ic .
če paz lj ivo pre ber ete začetek tega pri s pevka, bo s t e opazili ,
da smo re kl i, da v omrež ju stezi c na šo lskem d vor i šču ne žel i -
mo nepotre bnih k ri ži šč . S t em s mo k r i ž išča omej i l i na že ob -
sto ječe to čk e. Brez t eg a pogoja dobi mo namreč drug o nal ogo , n ~
l ogo o Steine r je vem dre ves u . Raz l i ko med obema nalogama s i bo-
mo og led a l i na pose bnem pr imer u . Za točke vzemimo o g l išča e na -
kost raničnega t ri kotni ka z dol ži no s t ran ice a . S Prim ov im po -
stop kom dob imo e nega od treh min imalnih d r ev e s z dol ž i no Za .
če pa d opus tim o dodatne t o č ke , dobimo 19hko cene jše , Ste i ner j~
vo dr ev o s ce no (d olži no) l3a = 1 , 73 a (g le j sl iko 10) .
Za konec povejmo l e tole ža lostno dej stv o. Dos l e j matematikom
š e ni uspe lo najt i u č in k ov i t e g a post op ka za is kan j e Ste i ne rje-
ve ga dr eve s a v s ploš nem pr i me r u . Vs e ka r je do s lej znaneg a o
tem prob lemu , daje celo s lut i ti, da uč in k ovitega pos t opka za
ta prob lem s plo h ni !
Tom a ž Pisans ki
Z36
...................