i i “537-Pisanski-naslov” — 2009/6/10 — 9:14 — page 1 — #1 i i i i i i List za mlade matematike, fizike, astronome in računalnikarje ISSN 0351-6652 Letnik 9 (1981/1982) Številka 2 Strani 68–70 Tomaž Pisanski: PROBLEM ŠTIRIH BARV Ključne besede: matematika. Elektronska verzija: http://www.presek.si/9/537-Pisanski.pdf c© 1981 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. PROBLEH STIRIH MRV Zanimivo j e , da v matematikf obs ta ja mnogo problemav, k i ae j i h da enostavno z a a t a v i t i , r e f f t l pa f i h j e s i l a te2ko. Eden t a k i h de t u d i probtam I $ $ r t h bum. Denlmo, da moramo pobarvat l po l juben rem l jev fd . Drfave barvamo z r a r l t t n l m i barvami tako, da s t a sosedn j i d rZav i (drZavS, k i tmata skupno mejo) vedno r a z l i t n i h barv (drugate na zeml jevidu ne b i vede l i , k j e pofeka meja med nj ima), Dos le j se j e za vee s tvarne In u m i f l j e n e zeml jev lde pokazalo, da j e dovoSj i m e t i na razpolago l t i r i barve. Eeprav se s tem problamom re dolgo Easa u k v e r j a j o matematiki. J l m j e 3 e l e pred k r a t k i m uspelo dokazat f . da Je vsak zeml j e v t d mogote p r a v f l n ~ pobarvat f s J t i r i m i barva- mi. Hetematika Appal i n Haken, k f s t a l e t a 1976 r e P f l a problem Z t i r i h barv, s t a p r i r e l e v a n j u uporabl j s l a ra tuna ln i k , kar j e za re fevan je Eisto matemat i tn fh grobtemov p r e c e j nanavadno. Primer na s l i k i 1 pokafe, da potrebujemo za nekatere zeml jev Ide vsa j f t f r i barve ( t r f barve so t o r e j premalo). S l f k a 1 Vsaka od štirih držav na sliki meji na vsako drugo, zato moramo vsako pobarvati s svojo barvo. Prvi do kument v zvezi s problemom štirih barv je pismo znanega an gleškega ma t ema t i ka in log ika DeMorgana z dne 23. oktobra 1852 pr ijatelju, slavnemu matematiku Hamiltonu. V njem piše, da mu je njegov u čenec Frederick Guthrie zastavil problem štirih barv in da ga s am ni znal r eš i t i . Freder ickov stare jši br a t Francis je namre č opazil, da se s štirimi barvami da na zemljevidu Ang- lij e ločiti vse grof ije. Kasnej e so se s problemom š t i r i h barv ukva r j a l i mnogi matemat i ki pa tudi mnogi amaterji. Kempe je na primer l e t a 1880 objavil "re ši t ev " problema štirih barv. šele leta 1980 je angle ški matematik Heawood našel luknjo v Kempeje- vem do kazu . Hkr ati je Heawood do kazal, da se vsa k zemljevid da pobarvat i z največ petimi barvami. Tudi pisca tega prispevka je pred ne kaj leti zbudil prijatelj-matematik in mu ob štirih zju- t raj poved al, da je problem k o n č n o rešil. Po enournem zasliše- va nj u pa je sa m na šel "1uknj o" v svojem "do ka zu" . Pr oblem štirih barv za matematiko ne bi bil tako pomemben, če ne bi matemati ki ob pos kusih r e š eva nj a tega problema odkrili mno ge ze lo pomembne matem atične me t ode . Ves čas, ko smo govo ri- li o zemljevidih smo misl i li na zemljevide, ki jih rešujemo v ravnini ali na zemlji, torej na površini kro gle . Problem pa l ah- ko prene semo tu di na druge plos kve . V bo d očnosti bodo morda ob- s t aj ali ume t ni planetoid i v obli ki svitka (torusa). Sl ika 2 69 Denimo, da je t a k p l a n e t o i d ob702en s posebnimi ploSCami. ra ka- tere moraao l e od d s l e t v j d e t i , kje se s t t k a j o . P l o S t e (d rZave) moramo t o r e j b a r v a t i z r a z l I tnf m i barvami tako , da p o k r 4 j e j o t a r u s t n da s t a dve s o s e d n j i vedna p o b a r v a n l z r a z t t E n i m a Bar - vama. To j e t o r e j problem b a r v a n j a r e f i t f e v j d o v ns svttku. C a p - r a v f a t a problem na v i d e x d o s t f b o l j zamotan ad problem8 & t t - r 2 h barv, ga j e r e 3 f 1 re v p r e j l n j e m s t o l e t j u Heawoad. Dokazal j e , da se da v r a k zemtJevid ria t o r v s u p o b a r v a t l s sadmCmt bar- yam(. N a l e l pa f e t u d i t a k r e m l j e v i d za k a t e r e g a sedem barv r e s pot rebujemo. Eeprav Js po s r o j i n a r a v i prob lem k r v a n j a t o p o l o - f k t , sodl danes b o l j v t e o r f j o g rs fov . . Vsak i d ~ t a v i p r i r e d i m o t o t k o ( g l s v n o mesto) . tako dobimo t o l i k c toEk, k o l i k ~ r d r f a v fmamo na z e m l j e v f d u . Po due t o t k t poveteRo s E r t o , t e s t a g l a v - n I mestl s o s e d n j f h drgav. S t r u k t u r o , k t j c s e s t a v l j a j o t o t k e i n povezava, Tnenujemo v rnatemat ik f g r a f . Problem b a r v a n j a zeml j e - v i d a l a h k o sadaf prevedemo u prob lem b t r v a n j r t o t k g r d f a . Toeke g r a f a [ g l a v n a mesta dr fav) barvamd tako, da s t % s c s e d n j t t o E k i ( t o r e j t o f k l , k i j u ve2e povezava) pobarvan i t s a z l i t n f m a bar- vama. VeE o tam morda k d a j drugiEE