Izrek štirih barv

Iz Wikipedije, proste enciklopedije

Izrèk štírih bárv izjavlja, da lahko vsako ravnino razdeljeno na področja, kot je na primer politični zemljevid držav, grofij, ali karkoli že, pobarvamo z največ štirimi barvami tako da nobeno izmed sosednjih področij ni pobarvano z isto barvo. Dve področji sta sosednji, če njuna meja ni le točka. Vsako področje se mora stikati z drugim, kar pomeni, da nima eksklav kot jih imata npr. Michigan in Azerbajdžan.

Očitno je, da tri barve niso dovolj. Tudi ni težko pokazati, da je pri barvanju dovolj pet barv.

Izrek štirih barvah je bil prvi veliki izrek, ki so ga (leta 1976) dokazali s pomočjo računalnika. Njegovega dokaza vsi matematiki ne sprejemajo, saj ga človek ne more preveriti na roko. Navsezadnje moramo verjeti v pravilnost prevajalnika in strojne opreme, ki sta izvršila program za dokaz.

Dokazu so očitali tudi da ni ličen, ali če zapišemo z besedami iz tistega časa: »dober matematični dokaz je kakor pesem - to pa je telefonski imenik!«

[uredi] Zgodovina izreka

Domnevo, ki predstavlja problem barvanja, je verjetno prvi predlagal leta 1852 mladi angleški matematik Francis Guthrie. Pri barvanju angleških grofij je zapazil, da so za to potrebne le štiri barve. Guthrie je leta 1850 diplomiral na Univerzitetnem kolidžu v Londonu (UCL), kasneje pa je poučeval matematiko na Južnoafriški univerzi v Capetownu.

Problem se je prvič pojavil v delu Arthurja Cayleyja O barvanju zemljevidov (On the colourings of maps), ki ga je izdala Kraljeva geografska družba leta 1879.

Pred končnim dokazom se je pojavilo več neuspešnih poskusov. Enega od dokazov je podal leta 1879 Alfred Bray Kempe. Njegov dokaz so sprejeli. Drug dokaz je podal leta 1890 škotski fizik in matematik Peter Guthrie Tait. Leta 1890 je Percy John Heawood dokazal problem barvanja zemljevidov za pet barv in pokazal, da je Kempeov dokaz nepravilen. Leto kasneje 1891 je Julius Petersen pokazal še na nepravilnost Taitovega dokaza.