i
i
“348-Bezek-Batagelj” — 2010/5/18 — 11:18 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 6 (1978/1979)
Številka 1
Strani 24–31
Danijel Bezek, priredba Vladimir Batagelj:
NEKAJ O GRAFIH IN NJIHOVI UPORABI
Ključne besede: matematika, kombinatorika, teorija grafov, Eulerjevi
grafi, naloge.
Elektronska verzija: http://www.presek.si/6/348-Bezek-Batagelj.pdf
c© 1978 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 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.
MATEMATIKA101 _
NEKAJ OGRAF IHINNJ IHOVI UPORABI
V ugan kar s kih k o t ičk i h č as o p i so v i n re vij najdemo ne kat ere ti -
p i čne vr s te na lo g in pr oblem ov . V te m se st av ku si bomo og l eda -
li dokaj pogo s t tip t ak i h nalog i n pokaza li, kako j i h r e šujemo
z gr a fi , ki j i h obr avn ava po sebna veja matema ti ke - teo ri ja
gra fo v .
Z ačetk i t e orije grafov sega jo v 18 . s t ol e tje . St aro me sto
Ko ni gs berg ( z na no tu di po tem , da t am po čiv a j o pos mrt ni osta n-
ki ve l ikeg a fi l ozofa Kant a) j e kr a s i l o sed em mos t ov, ki s o po-
vezo va l i bregove reke Prege l z o toč kom sred i nj e ( Sl . 1 ) .
Sl.1 Sl .2
Me šča ne Kon igsbe rg a je l ep č as vznemi rja lo nasl e dn j e v pr a š an j e :
Al i se j e m og o č e sp re ho dit i p reko mo st ov ta ko , da g reš čez v s a-
kega sa mo e nkra t ? Posku s i!
Za prob lem je zvedel tudi največji matema ti k ti s tega ča s a -
Le o nhar d Eu l e n ( 1707 - 1783 ) . Prob l em s i je poe nos tavi l t a ko ,
da je br egove i n oto ček oz n a č i l s kr ože i i n j ih pove za l s č r ta -
24
Kon igsbe rg - danes Ka l in ing rad
Le onh a x-d s a t.e » je bil r oj e n 15 . ap ril a 1707 v Baz l u v š vi c i .
Bi l je u č en e c in pr i jate lj Ber nou l li j ev . Veli k de l svojega ž i ~
ljenj a (1727 - 1741, 1766 -17 83) je prež i ve l v Ru s i j i na Pet ro-
g ra j s ki ( da ne s Len ingrad ) ak ademi j i , ki jo je takrat ustanov i -
la ca r i ca Ka t a r i na 1 . Tam je tud i umrl 18. septembra 1783 .
Obdobje 17 41- 17 66 pa j e na povab ilo Fr i ed ri ch a I I pre bi l na
ber l ins ki akade mij i znanost i. Eul er j e e den n ajv e č jih mat emati
kov vse h časo v . Pose ge l je na vsa področja mat em atik e in j o o-
bogat i l s pom em bnimi s pozn a nji. št ejemo ga med oč et e vari acij-
sk ega raču na, teo r ije d if erencia l nih e n ačb, t eorije š tev i l in
t opol ogi j e. Pri dokazo va nj u je zače l d a ja ti pr edn ost a l ge bri
pred geometr ijo . Ukvarja l se je tu di s fi z i ko , mehaniko, ba l i -
s t iko in astronomijo. Let a 1735 j e za rad i preveč vn etega opa zQ
vanj a Sonca pri sesta vljanju s istema za do ločanje časa os lep el
na desno oko. Popo lnoma s lep je post al l et a 17 66 , kar pa ni
bi st ve no vpl iv al o na nj eg ovo u s tvarj aln ost. Imel j e i z r ed en
spom i n . č loveštv u je za pus t il nek aj knj ig, več ko t 800 č la nk o v
( neka te r i s o prece j dolgi ) in kup ne objavljenih del. Uv ed el je
oz nake e za os novo nara vnih l ogaritm ov , i za kvadtatni kor en
i z min us ena i n f ( ) za f unkc i je.
25
mi, ki p r e d s ta v l ja j o mostov e (S l . 2 ). Taki s he mi p r a v i mo graf .
še nekaj g r af ov j e p ri ka z ani h n a s l i ka h ( S l . 3) i n ( S l . 5 ) .
Ka ko r v id imo , j e g ra f s es ta v ljen iz množi c e krožce v a l i točk
grafa, k i . s o med seboj par oma povez ani z množi c o črt a l i pov e -
za v . Name sto bes ed t oč ka (g ra fa) in pov e zav a pogosto u pcr a b l j a
mo tud i bese d i v o z e l in v e j a . Točki, k i j u povez ava veže , ime -
nu j e mo kraji šči pov e z a ve. Da ima pove za va p kra j išč i u in v ,
bo mo zap i s a 1 i p (u ; v ) .
w
b
z
S1.3
Prim e r: Graf na s l i ki 3 j e d ol o č en z množi c o točk T = { x , y ,
z , w } in množi c o po vezav P = {a (x ;x ) , b (x ;y ) , c (y ;z ) , d ( z ;w ) ,
e (w ;y ) , f ( w ;y ) } . Najb rž je med pove za va mi priteg n ila vašo po -
z o r nos t p ovez a va a (x ;x ) , k i i ma za o be k r a j i š č i i sto t o č k o x .
Takim po v ez avam pravimo zan k e.
š tev i lo pov ez av , ki i maj o z a kraj iš če t o č k o t , i menuj e mo k rat -
nost to čk e t in jo označ imo k ( t ) . Zanke u pošte vam o p r i do loča ­
n ju kra t nost i dv a krat. Ta ke velja za g r af na s l iki 3 :
k (x ) = k (w ) = 3 k (y ) 4 in k (z ) 2
Postavimo se v neko t o č k o g r af a . S te m, da se po pove z av i, k i
im a t o č k o, v kate r i s e t r enutno nah a jamo , za k r a j i š č e , pomak-
nem o v d rug o kr a ji š č e , lahko "p otu jem o" po gr afu od t o čke d o
t o č k e . Za po redj e po ve za v , k i j ih pri t e m prehod imo, i menu j emo
pot po gra f u.
Za gra f na sl i ki 3 st a z ap ore d ji povezav :
P 1 = a , b , c , d , e , e , f
26
P2 = c
poti; zaporedj e
P3 = b , a , e
pa ni (zakaj?).
Vsaka pot ima svoj zače t e k in svoj k o n e c . Pot P1 ima začetek
v točki x in konec v točki y , kar zapišemo P 1 (x, y) . Za začetek
poti P 2 pa lahko izberemo katerokoli od krajišč povezave c . Za
to, da bo pot po grafu natančno določena, moramo v splošnem
poleg zaporedja prehoje nih pove zav podati še njen začetek .
če obs t a j a pot i z točke u (začete k ) v t oč ko v (konec), pravimo,
da je toč ka v doseg~ji va iz toč ke u . Kadar so vse toč ke grafa
med sebo j dosegljive , bomo rekl i, da je graf pov ezan .
Graf na sliki 3 je pove zan; če pa "zbri šemo" povezavo b , dob i -
mo nepovezan graf, saj točka x ni več dosegljiva iz drugi h
toč k grafa.
Seda j vemo o grafih že toliko , da lahko sledimo rešitvi naloge
o koni gs ber šk i h mostovih, ki jo posplošimo na grafe takole:
Ali ob s t a j a po danem grafu pot, ki vsebuje vsako povezavo na -
ta nko en kr a t ?
Ta ki poti pravimo Eu ~erjeva pot . Reši tev zastavljene naloge
daje naslednji izrek :
V grafu obstaja Eulerjeva pot natanko takrat, ko je povezan
in ima največ dve točki lihe kratnosti .
č e obstajata dve l i hi točki (vedno obstaja sodo število li-
hih točk) , je ena za čete k , druga pa konec Eulerjeve poti .
č e pa so vse toč ke sode , je Eulerjeva pot s klenjena ali
cike~ - nj en z ačet e k in kone c sov pa data; za začetek pot i la
hko iz bere mo poljubno to č ko .
Uteme ljimo najp rej trditev : č e v danem grafu obstaja Eu lerjev a
pot, potem s ta v grafu največ dve lihi točki . Mislimo si, da
je graf narisan s kredo. Vzemimo v roke gobo in s ledi mo Eu l e r-
jevi poti po grafu. Prehojeno pot za seboj briš imo . Ko pre ho-
27
d imo celo tno pot, bodo vse povezav e gra fa zb r isane - vse točke
bcd o imel e kr a t nos t O, to re j bodo s ode . Oč it n o pr i vsak em
pre hodu skoz i točko zb r išemo dv e pove z av i - tisto, po ka ter i
smo v točko pr išl i, in tisto, po kateri smo točko zapustili .
Potemtakem pr i prehodu skoz i njo osta ne so da točka so da, 1iha
pa l ih a. Le na začetku i n koncu pot i l ah ko spremen imo parnost
točke, kaj t i l e v te h dveh pr imer i h zbr i še mo v d an i t o č k i eno
samo pov ez av o . Ker morajo bit i na koncu v se točke sode, i mamo
zato l a hko spočet~a kvečjemu dve lih i točk i.
Naj sedaj graf z ado š ~ a pugojem i zr e ka . Kako do bimo Eul e r j ev o
pot? č e v grafu obsta j a ta lihi to čki , z ačnemo ve ni i zmed nji-
ju i n potu jemo po gra f u . Ker l a hko v vs a ki s od i točk i po t na-
daljujemo, se bomo prej a li s lej us tav ili v drug i li hi točki.
V še ne prehojenem del u grafa so sedaj v s e t o č k e sod e . To v e -
l j a tu di v pri meru, ko že spoč etka ni v gra fu noben e lih e t o č­
ke . V obeh primerih izberemo pol j u bno točko, ki je kraji š č e še
ne pr e hoj en e povez ave in začnemo po t ovan je . Ker so vse t očke
sode , bomo pot ovan j e konča l i v začet n i točk i - dob ljena pot
j e c ike l . To pona v ljamo , do kl er ne po kri j emo s c ik l i ves graf.
Zara d i pove za nos t i gr af a l ahko c ik l e ( i n pot ) zd ru žim o v e n
sa m c ik e l ( pot). Osn ovn a zami sel zdr uževanja j e prik az an a na
s lik i 4:
2 . cikel
-ZDRUŽIMO
Sl.4
S podo bni m r a zmi šl j anj em j e Eule r na r edil konec brez gl av emu
i s ka nj u . Svoja dogn anja j e obj avil v r azpr avi : Solutio proble-
mati s ad geometriam , s i t us pert ine nt is , Comme nta ri i Acad emia e
28
\
Petropo lit an ae VII I , 17 36 ( 174 1) , p . 12 8 -140 . Na l og a o kl.i nigs -
be rških mostovih ni rešl jiva, saj i ma pri rejen i graf š ti r i l i -
he točke .
Tovr stn e nal oge s reča mo v uga nk arsk i h ko t ič k i h pogosto pod na-
s lovo m " na r iši z e no pote zo " . Ta ke na loge nam ne bodo več de-
l ale t ežav . Ka j pa , če s ta v g r a f u v e č kot dve lih i točk i ? V
na jmanj koliko pot ezah l ah ko nari š em o tak graf ? Odgo vo r d aj e
iz r e k :
Povezan i gra f z 2m lih imi t o č kami l ah ko pokr ij e mo ( = vsaka
povezava vstopa v ne ko pot ) z m l o č e n i m i (= vs a ka pove zava
vstopa v največ eno po t ) potm i.
Seda j nam ne bo v e č t e ž ko r eši t i nasledn jih ne ka j nalog :
Na lo ge :
1. Nar iš i graf, do ločen z množico točk T = {x, y , z, u,v } i n mno-
ž i co pove zav p = {a {z ; y) , b { y ; v ) , c { v ;z ) , d {u ; z) , e {u ;v ) ,
f {u ; y ) , g {v ; v )}.
2 . Nariš i povezan graf na petih točkah , ki imajo vs e kr a t -
nost 2 .
3. Kr a t nos t i peti h to č k so zap or ed oma 1 , 2 , 3 , 4 i n 5. Na r i š i
gr af!
4 . V vs a kem grafu je s odo mn ogo l i hi h točk . Do kaži !
5. Vsa keg a i zmed gr a f ov na slik i 5 nari š i s C1m ma nj potezam i
( pot e za = neprekinjena črta), pr i čemer nar i š e š vsa ko črto
l e enkrat :
S1.5a St.5b St .5e Sl .5d
29
Med nalogami je tudi P1em1jev a uganka ( Sl. 5b) . Anekdoto o
nje j s i l ah ko po i šč et e v en em od pr et ekl ih le tnikov Prese ka
6 . Prav il ni n- kot n i k z vse mi d i agon alam i j e pravz ap rav gr af
nad n toč k ami ( o g l išč i). č e je ri liho š t ev il o , ga lah ko po
Eulerjevem izreku- narišemo v eni potezi . To zna tudi prog-
ram, ki je "nari sal" pri mer tega mnogo kotni ka za n = 31
(Gl ej s l iko na naslovni st ra ni) . Pos kusi sam na r isati v eni po-
tezi pr av i l ni sedem kotni k z vs emi diagonalami!
REŠ !TV E
3 . Tak graf ne obstaja, ker
je število lihih točk v
graf u vedno sodo '( g l e j na-
logo 4).
l. Kak o narišemo graf ? Naj-
prej narišemo za vsako toč ­
ko po en kr ogec in ga ozna-
č i mo z nje no ozna ko . Na t o
točke povežemo s povezava-
mi i n graf je narisan. V
našem primeru dobimo
Seveda je sli ka grafa od -
visna od z a č e t n e raz pore -
ditve točk. Posebnost na-
šega grafa je to č ka x , ki
ni krajišče nobene poveza-
ve.
2 .
o
x
a
z
li
3 0
4 . Vs a ka povezava ima dve kra -
jišči . Torej je število
vseh k r a j i š č povezav sodo.
število vseh k r a j i š č pa
dobimo tudi, če seštejemo
kr a t nos ti v s e h t oč k . Ker
je vsota soda, mora bi ti
tudi število l i hi h č lenov
v te j vsoti sodo .