P R E S E K
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652 Letnik 25 (1997/1998) Številka 6 Strani 348-350
Marija Vencelj:
MALA ŠOLA TOPOLOGIJE - 6. del
Ključne besede: matematika, topologija, teorija grafov, barvanje parcel, zemljevidi, problem štirih barv.
Elektronska verzija: http://www.presek.si/25/1354-Vencelj.pdf
© 1998 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
Barvanje parcel
Prerisite naslednje risbe in jih pobarvajte. Pri tem naj bo posamezna parcela pobarvana z eno samo barvo, dve sosednji parceli, to je parceli, ki ju loči skupni lok, pa vedno z različnima barvama. Ne pozabite na zunanjost risbe! Parceli, ki imata skupno kakšno izhodišče, ne pa tudi loka, nista sosednji in ju torej lahko pobarvamo z isto barvo.
(a)	(b)	(c)	(d)	(e>
1.	Pri delu poskusite uporabiti čim manj barv. Koliko barv ste potrebovali za posamezni primer? Kdo je risbo (d) pobarva! z najmanj barvarni? In kdo risbo (e)?
2.	Sami narišite risbo, za barvanje katere potrebujemo:
(a)	samo dve barvi,
(b)	vsaj tri barve,
(c)	vsaj Štiri barve.
3.	Ali znate narisati risbo, za barvanje katere potrebujemo vsaj pet barv?
4.	Narišite risbo z osmimi parcelami, ki jo lahko pobarvamo samo s tremi barvami.
5.	Narišite več krožnic s polmeri okrog 5 cm. V prvo vrišite eno tetivo, v drugo dve. v tretjo tri tetive, itd. Tetive izbirajte tako, da boste vsakokrat dobili znotraj krožnice čim večje število parcel.
(a)
Koliko parcel je na posameznem koraku? Koliko najmanj barv potrebujete za vsako barvanje (samo notranjosti krožnice)? Kaj opazite?
Kratka zgodovina problema štirih barv
Leta 1852 je mladi angleški matematik Francis Guthrie ob barvanju zemljevida angleških grofij prišel na misel, da se morda da vsak zemljevid, narisan na ravnini, pobarvati samo s štirimi barvami. Pri tem je zahteval, podobno kot v zgornjih nalogah mi. da sta dve sosednji državi pobarvani z različnima barvama.
Da obstajajo zemljevidi, za katere potrebujemo štiri barve, ste lahko sami ugotovili, če ste rešili nalogo 2(c). To je vedel že Guthrie. Za dokaz, da štiri barve res vedno zadoščajo, pa je bilo potrebnih nadaljnjih 124 let.
Oglejmo si najpomembnejše delne uspehe. Najprej je Guthriejevemu sodobniku, velikemu angleškemu matematiku de Morganu uspelo dokazati, da na nobeni risbi ne more biti pet parcel v položaju, v katerem bi vsaka mejila s preostalimi štirimi. Nato je leta 1879 odvetnik Alfred Bray Kempe objavil 'dokaz' izreka štirih barv, v katerem je po enajstih letih matematik Pearcy John Heawood našel napako. Na osnovi Kempejeve ideje je Heawood dokazal, da za barvanje zemljevidov zadošča pet barv. Ni pa um uspelo dokazati pravilnosti domneve štirih barv, čeprav se je z njo ukvarjal še polnih 60 let.
Več kot osem nadaljnih desetletij je veliko matematikov, pa tudi ljubiteljev, raziskovalo problem štirih barv. V ta namen so razvili številne matematične metode, ki so obogatile tudi druga področja matematike. Sčasoma je postalo jasno, da je število primerov, ki bi jih bilo potrebno proučiti, izredno veliko. Prvi, ki je pomislil, da bi se dalo problema lot iti z uporabo računalnika, je bil nemški matematik Heinrich Heesch. Njegovo delovanje v tej smeri je omogočilo, da sta leta 1976 ameriška matematika Kenneth Appel in Wolfgang Hakeu računalniško dokazala, da je domneva štirih barv pravilna. Kot zanimivost povejmo še, da sta svoj program, ki se je 'učil' tudi sam. pognala v začetku leta 1976 in po šestih mesecih, junija istega leta, pričakala odgovor.
Kaj pa zunanjost?
Zlahka uvidimo, da je za izrek štirih barv vseeno, ali barvamo samo notranjost risbe ali tudi njeno zunanjost. Za zunanjost res ne potrebujemo dodatne barve: Notranjost, risbe obdamo z enostavno sklenjeno krivuljo, ki vsa poteka po zunanjosti risbe. Tako dobimo zaključeno območje, ki ima eno parcelo več kot prvotna risba, ki pa ga po našem izreku lahko pravilno pobarvamo s štirimi barvami. Nato samo še razširimo barvo dodane parcele na vso zunanjost risbe.
Igra barvanja
Po tem, kar smo izvedeli o barvanju s štirimi barvami, je gotovo zanimiva naslednja igra za dva igralca:
Prvi igralec nariše parcelo, Drugi igralec parcelo pobarva in doda novo parcelo. Nato prvi igralec pobarva drugo parcelo in spet doda novo, itd, Pri tem morata paziti, da nobeni sosednji parceli nista enako pobarvani. Igra je končana, ko je eden od igralcev prisiljen uporabiti peto barvo. Ta igralec igro tudi izgubi,
Marija Vencelj