i
i
“5-2-Repovs-naslov” — 2009/3/27 — 11:43 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 5 (1977/1978)
Številka 2
Strani 73–76
Dušan Repovš:
PROBLEM O BARVANJU KART
Ključne besede: matematika, teorija grafov, barvanje grafov.
Elektronska verzija: http://www.presek.si/5/5-2-Repovs.pdf
c© 1977 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.
PROBLEM OBARVANJU KART*
Pri zemljepisu ste gotovo opazili , da so posamezne države na
zemljevidih razli čno obarva ne, da jih laže raz ločimo. Ali s t e
že kda j pomislili, koli ko ba rv potrebujemo na j man j za ta kšno
razmejevanje drž avnih ozemelj? Pa sami pobarvajte zemljevid Ev-
r op e s 4 r a z l i č n i m i barvam i ! Pa z i t e , dr žavi, ki me jita , morata
biti ra z L i čno obarvani!
sI. ,
Razmi šljanje, ki smo ga ubral i, je pred več kot sto l eti pri -
vedlo do slovitega probLema štirih bar v [1] , ki je bil r eš en še -
le l ani - z raču nalnik om. Tej t e ž ki nal ogi da mo ta kole obli ko :
Doka ži , da Lahko s samo štirimi razLičnimi barvami pobarvamo po -
Lj ub e n zemLjevid , če mora t a biti dve sosednji dr žavi pobarvani z
razLi čnima b ar vama .
* Pr i s pevek je ilustriral Božo Kos
73
S1.2
sLa
74
Problem sodi v posebno matewatično ve jo - teorijo grafov, s
katero se ukvarjajo tudi na ši matematiki, v s ve t u pa p r edn j a č i
ma džarska matematična šola.
Pr oblem štirih barv smo pokazali le za ilustraci jo znatno laž-
je na loge , ki jo kanimo ugnati v tem prispevku [2]:
V r avnini načrtajmo n premic . Dokaži . da ~a h ko območja, na
katera de~e premice ravnino , obarvamo ž e z dvema barvam a ta k o,
da s o s e dn.j i: območji ne bosta iste bar ve . ( Območji, ki mej ita sa-
mo V t očki , nimat a sku pne me j e in sta p o temtakem ~ahko i s te bar-
ve ) .
Naj pr e j vid imo, da dve s tr a ni - dva de l ara vnin e, ki j u r a z-
mejuje prem ica, more mo vedno obarvati le z dvema bar vama v s kl a -
du s pogoji na loge .
Pokažimo tole :če ~ahko ob -
močja ravnine , ki jih ustvar -
ja n premic , pobarvamo z dve -
ma bar~ ama p o po go jih na~oge ,
~ahko tudi območja, ki jih
napravi n+l premic , pobarva-
mo z dvema barvama po zahte -
v a h na l oq e , Odtod po pravi lu
matemati čne indukc ije sledi,
da je trditev na še na l oge
pr ev i l na . Imej mo n+l premic v
ravnini : P l ' " , Pn+l ' Odstra-
nimo eno , npr. Pn + l ' Ostalih
n premic de li ravnino na ob- 81.4
močja, ki j ih po predpostav ki
l ahko pobarvamo z dve ma bar-
vama po zahtevah naloge .
N a č r t a j m o premico Pn + l in na enem izmed njenih br egov s preme-
nimo vse bar ve. Na drugem br egu ne spreminjamo ničesar .
če i ma t a dve območji ravnine za me jo katero i zmed pr emi c P "
•. . , Pn ' sta l e razli čno obarv ani . To je ve ljalo že prej, zdaj
pa smo zamenjal i hkrati obe bar v i, tako da sta ostal i ba rvi isti
ali pa sta 5e obe hkrati zamenjali . če pa območji mejita na pre -
mic i Pn+l' bosta različno obar vani, saj smo za to spr emenili bar-
ve sa mo na enem bregu prem i ce Pn + l ' Tako dobl jeno obarvan je pov-
sem us t r eza zaht evam na loge in dokaz je k o n č a n .
75