i
i
“1367-Klavzar-Stopnje” — 2010/7/27 — 14:06 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 26 (1998/1999)
Številka 2
Strani 72–78
Sandi Klavžar:
STOPNJE TOČK GRAFOV V NALOGAH, (za ko-
nec gremo tudi v Portorož)
Ključne besede: matematika, teorija grafov, grafi, povezave, stopnje
točke.
Elektronska verzija: http://www.presek.si/26/1367-Klavzar.pdf
c© 1998 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.
Matematika I
STOPNJE TOČK GRAFOV V NALOGAH
(za konec gremo tudi v Portorož)
V Preseku in tudi dr ugj e pogosto naletimo na naloge, ki jih lahko pr eve-
demo v jezik teorij e grafov. Take naloge so poseb ej pogost e na medna-
rodnih matematičnih tekmovanjih mest , ki jih spremlja t udi Presek. Pri
nalogah tega t ipa nam grafi pom agaj o na dva načina. Najprej z njimi
nalogo prevedemo v matematični jezik , nato pa z nekaj znanja o grafih in
kakšno dobro idejo poskušamo problem tudi rešiti .
Ko sem pr egledoval naloge te vrste, sem ugotovil, da jih lahko raz-
delimo v dve skupini: v skupino nalog o stopnjah točk grafov in skupino
pr eost alih nalog, ki jih t udi lahko rešujemo s pomočjo grafov. Vsaj polo-
vica nalog obravnava stopnje točk in take naloge si bomo ogledali tokrat.
Na tem mestu vabim br alca , da pogleda na konec članka (naloga 7) ,
kjer se odpravimo na portoroško plažo. Če lahko reši zastavljeni pro-
blem , zasluži vse čestitke . V vsakem primeru naj se pot em vrne naz aj in
pr egleda, kako rešuj emo podobne naloge. Če bo tudi potem portoroški
problem ostal pr etrd oreh, pa naj bralec pogleda v prihodnjo šte vilko
Preseka , kjer bomo objavili rešitev.
Nekaj besed o grafih
O gra fih Presek kar pogosto piše, na primer pr ed kratkim, ko je bilo go-
vora o varn ih pot eh in kratkih poteh . TUdi v P resekovi knji žnici najdemo
pr ijetno br anj e o grafih za začetnike (Bajc, Pisan ski : Najnujnejše o gra-
tih ). Nobene škode pa ne bo, če t udi t u pojasnimo osnovne pojme teorij e
grafov.
Graf G sestavljata množica točk, ki jo označimo z V(G) , in množica
povezav, ki jo označimo z E(G). Pri tem je mn ožica E(G) sestavljena iz
(neurejenih) parov točk. Točki iz iste povezave imenujemo sosedi. Zelo
pogost o si pomagamo s sliko grafa, ki jo dobimo takole: Za vsako točko
gra fa narišemo krožec, med dvem a točkama pa potegnemo črto (pove-
zavo), če ti dve točki nastopata kot par v množici E (G ). Na primer, če je
mn ožica točk grafa G enaka
{1,2,3, 4 ,5, 6, 7,8, 9}
in je mn ožica povezav
{{1 ,2},{1,8} ,{1 ,9},{2,3} ,{2,7},{3,4} ,
{3,6} ,{4,5},{4,9} ,{5,6} ,{6,7} ,{7, 8}} ,
graf G lahko nari šemo, kot je prikazano na sliki 1.
I Mat ematika
9
1 C5-- -o-- --o- -oo4
8 7 G 5
Slika 1. Graf G.
Osnovni poj em o grafu, ki ga še potrebujemo, je število povezav, ki
izhaj ajo iz dane točke. Temu številu rečemo stopnja točke. Na grafu
G s slike 1 so točke 5, 8 in 9 stopnje 2, medtem ko so ostale točke sto-
pnj e 3. Dovoljene so t udi točke stopnje 0, torej take, ki nimajo nob enega
sose da. Stopnjo točke u bomo označili z d(u) . Dogovorimo se t udi, da
naj IE (G)I označuj e število vseh povezav grafa G . (V gornjem primeru
imamo IE(G)I = 12.)
Tale uvodni del zaklj učimo z naslednjo ugotovitvijo, ki se imenuj e
osnovna lema teorije grafov. Za poljubni graf G z množico točk V (G) =
= {1, 2, . . . , n} velja:
d(1) + d(2) + ...+ d(n) = 2 · IE (G)I. (1)
Osnovna lem a teorije grafov torej trdi, da je vsota stope nj točk grafa enaka
dvak ratniku šte vila povezav. Res je tako, saj ko seštejemo stopnje vseh
točk , vsako povezavo upoštevamo ravno dvakrat . (P reizkus i to sam na
gornjem primeru.) Kljub temu, da je osnovna lema teorije grafov dokaj
prep rosta, je izjemno uporabn a. To bom o delno spoznali v nadaljevanju
te ga članka .
Naloge s stopnjami točk
Naloga 1. (Izbirno tekmovanje za 1. letnik, 1991) V skupini ljudi je
vsak poznalliho šte vilo ljudi iz t e skupine . Dokaži, da je v skupini sodo
ljudi .
To je tipična naloga , ki jo s pomoejo osnovne leme teor ije grafov
uženemo v trenutku. Vsaki osebi priredi mo točko grafa , povezave pa naj
predst avljaj o poznanstva. P redpost avka naloge pravi , da je stopnja vsake
točke liho št evilo. Če bi bilo v skupini liho ljudi , potem bi na levi st rani
strani enakosti (1) dobili liho število (vso ta lihega števila lihih števil je
liho šte vilo) . Ker imamo na desni strani enakosti (1) sodo število, to ni
možno, zato mor a biti v skup ini sodo št evilo ljudi.
Matema tika I
Naloga 2. (Izbirno te kmovanje za 1. letnik, 1979) V dru žbi šest ih
fant ov so tudi deklet a . Dve deklet i po znata vsaka po štiri fante, tri
vsaka po t ri fante, ostale pa vsaka po dva fan t a . Noben fant ne pozn a
več kot štiri deklet a . Koliko največ je lahko deklet v družbi ?
Shematično smo nalogo prikazali na sliki 2, kjer smo z fI , [ z , .. . , 16
označi l i šest fantov .
fI h iJ 14 15 16
/1\\ /1\\ /1\\ /1\\ /1\\ /1\\
VI VI W W W V \ / . . . \ /O O
Slika 2. Šes t fantov in dek leta .
Največj e število deklet bom o imeli v primeru, ko vsak fant po zna po
št ir i deklet a , ta primer smo tudi prikazali na sliki. P ovezav, ki izhaj ajo iz
fantov, je v t em primeru 6 ·4 = 24. Seveda mora biti tud i šte vilo povezav ,
ki izhaj aj o iz dek let , enako 24. Pet deklet s štirim i oz. tremi znanci nam
da skupaj 17 povezav. P reostane nam še 7 povezav za dekleta z dvema
znance ma, torej imamo prostora še za t r i deklet a . V družbi je to rej največ
8 deklet .
Naloga 3. V cirkušk i predst avi nas top ajo štirje pari klovnov, dva
rdeča, dva modra , dva zelena in dva rumena . Med predst avo se na
veselje gledalcev zaletavajo med seboj, pri tem pazijo le, da se ne zale-
tijo v klovna enake bar ve. Nekega dne je prvi rdeči klovn po predst avi
vprašal vseh preost alih sedem klovnov, v koliko dru gih klovnov so se za-
leteli med predst avo. Dobil je same različne odgovore. V koliko klovnov
se je med predstavo za lete l drugi rdeči klovn ?
Na prvi pogled je videti, kot da nalogi manjkaj o podat ki. Vendar
temu ni tako. Sestavimo graf G takole: Njegove točke naj predstavljajo
klovn e, graf ima torej 8 točk . Dve točki povežimo s povezavo , če sta se
ust rezna klovn a med predst avo zalet ela . Zanima nas to rej stopnja točke,
ki ustreza drugemu rdečemu klovnu .
Stopnja točke v grafu G je največ 6, saj imamo 8 točk , klovn pa ni
sam sebi sosednj i in t udi klovnu ist e barve ne . Zato so odgovor i, ki jih je
dobil prv i rdeči klovn , enaki 0, 1, 2, 3, 4, 5 in 6. Označimo ustrezne točke
v G kar z 0, 1, 2, 3, 4, 5 in 6, prvega rdečega klovn a pa z r (glej sliko 3) .
I Matematika
7'
o
o
o
--o 1
::>o 2
Slika 3 . Stopnje klovn ov.
P oglejmo klovna st opnje 6. Ta je sosednji vsem klovnom, razen is-
tobarvnemu. Ta mora biti seveda stopnje O, sa:j imajo vsi drugi klovn i
vsaj enega soseda . Recim o, da klovna 6 in Otvorit a modri par. Poglejmo
sedaj klovna, ki je odg ovori l s 5. Ta klovn ni sosednji Oniti 1 (saj je njemu
sosednji 6). To pomeni, da klovna 5 in 1 t vorita par , recimo zelenega. Z
enakim pr emi slekom bo sedaj vsak sa m ugotovi l, da klovn a 4 in 2 tvorit a
rumeni par. To pa že pomeni, da je klovn 3 drugi rdeči klovn, torej se je
za let el s tremi drugimi klovni .
Naloga 4 . (14. mednarodno tekmovanje mest - pomladanski krog ,
prva skupina, 1992/ 93) V Petrovem razredu je po leg njega še 25 dija-
kov . Peter je opazil, da ima vsak izmed teh 25 dijakov različno šte vilo
pri jateljev. Koliko pr ijateljev ima Peter v tem razredu ? Po daj vse
možne odgovore.
Ta naloga pr ecej spominja na prej šnjo, klovnovsko , zato bomo rešitev
le skicirali, bralec pa naj doda manjkajoče podrobnosti.
Ker ima ustrezni graf 26 točk , je največja možna stopnja 25. Ločimo
dva primera. V pr vem primeru pr edpostavim o, da ima vsak vsaj eneg a
prijatelja , torej da ni točke stopnj e O. Tor ej , 25 dijakov ima stopnje od 1
do 25. Sedaj kot v nalogi s klovni pridem o do zaključka, da ima Peter 13
prij at eljev.
V drugem primeru pr edpostavimo , da imamo točko stopnje O. To
pom eni , da ima pr eostalih 24 dijakov stopnjo največ 24, za to so njihove
sto pnje od 1 do 24. Kot pri klovnih zopet sklepamo , da ima Pet er v te m
primeru 12 prijateljev.
Mat ematika I
Naloga 5. (18. mednarodno tekmovanje mest - jesenski kro g, prva
<, skupina, 1996/97)
a) Ali obstaj a taka družba 10 deklet in 9 fantov, da so šte vila fantov , s
katerimi se posamezna dek leta poznaj o, med seboj različna, števila
deklet , s kat erimi se posamezni fantj e poznajo, pa so med seb oj
enaka?
b) Ali obstaj a družba 11 deklet in 10 fantov z zgornjo last nostjo?
Rešitev t e naloge najdemo v prvi št evilki lanskega P reseka. Tu le
dodajmo, da (negativni) odgovor na vpraša nje b) takoj dobimo z osnovno
lemo teorije grafov, ustrezni graf za (pozit ivni) od govor na vprašanje a)
pa je prikazan na sliki 4.
Slika 4. Rešitev naloge 5.
Zadnj a naloga, ki jo bomo rešili , je zaht evnej ša in primerna za dij ake
v zaklj učnih razredih srednje šole. Kdor ne sodi v to skupino, naj nalogo
kar preskoči in se lot i portoroških plaž.
Naloga 6. (16. mednarodno tekmovanj e mes t - pomlad anski krog,
druga skupina, 1994/95) Dokaži, da sta v skupini 50 ljudi vedno dva,
ki imata sodo število (lahko tudi O) skupnih znancev iz skupine.
Kot smo že navajeni , bo do točke grafa za to nalogo pr edst avljale ljudi
in povezave poznan stva.
Najprej opazimo, da ni kaj dokazovati, če obstaj ata dve točki, ki
nimata skupnega soseda (saj imata O skupnih sosedov). P redpost avimo
torej , da ni dveh takih točk. Zato si gra f lahko pr edstavljamo takole: Vze-
mimo neko poljubno točko , recimo u . Nato en nivo nad njo nari šimo vse
njene sosede, še en nivo više pa vse sosede sosedov, ki j ih še nismo narisali
I Matematika
(glej sliko 5) . Prvi nivo smo označili z N I in drugega z N 2 . Povezave
našega grafa torej pot ekajo med u in N I, med NI in N 2 t er znot raj NI in
znot raj N 2 .
Slika 5. G raf po znanst ev po nivoj ih .
Na sliki 5 se pojavijo vse točke našega grafa . Če bi namreč obst ajal
še en višji nivo, potem točka u ne bi imela skupnega soseda s točkami
t retjega nivoja , vend ar smo to možnost izključili .
Naj bo v poljubna točka iz N I , to rej poljubna soseda točke u . Če
ima v znot raj N I sodo sosedov , je problem rešen , sa j imata te daj u in v
sodo število skupnih sosedov . Zato predpost avimo, da ima v liho sosedov
v N I. Ker je bila v poljubna točka iz N I, ima to rej vsaka točka iz N I liho
sosedov v N I . Sedaj uporabimo osnovno lemo teorij e grafov, iz katere
sledi, da je v NI sodo število točk. Z drugimi besedami, st opnja točke u
je soda .
Spomnimo se, da je bila u poljubna točka našega grafa, torej smo
ugotovili , da so vse točke grafa sode stopnje .
Vzemimo sedaj poljubno točko w iz N 2 . Če ima w sodo sosedov v
N I , smo opravili, saj imata tedaj u in w sodo skupnih sosedov . Zato
predpost avimo, da ima ima w liho sosedov v N I . Ker je v N I sod o število
točk, ki imajo sod o mnogo sosedov v N 2 , ugotovimo, da mora biti v N 2
sodo št evilo točk. Torej imamo sod o točk v NI , sod o točk v N 2 in še
točko u , skupaj to rej liho število točk. To seveda ni možno, saj ima graf
po predpostavki 50 točk. Tako smo prišli v protislovje, ki nam pove, da
smo morali v enem prejšnjih korakov izpeljave imeti situacijo z dvema
točkama s sodim številom skupnih sosedov.
Pozorni bralec je verje tno opazil, da nalo ge nismo rešili le za 50 ljudi,
ampak za poljubno skupino sodo mn ogo ljudi.
Tako. Spoznali smo nekaj tipičnih nalo g, ki jih lahko rešimo s po-
močjo gra fov in stopnjami točk . Za konec pa še obljubljena portoroška
naloga.
78 Muternotika - Novice I 
Nalcga 7, Kot; gotova W e ,  j6 portim&ka pl&a sredi poletja zf:b 
aasedeaa. Vwhabr t o h ,  da h a t e ,  kjerkoli Se ste na njej, na razdalji 
do 10 m 9e h u g e  obiskodce. P o w ,  da Mko v takem vmZu vedno 
najdemo d w  wbi, ki imata enako Btevilo obiskwaIceu plee,  
ljenih do 10 m od njiju. AIi trditev velja tudi, Ee 10 m zamenj 
1W