Izrek štirih barv
Izrèk štírih bárv izjavlja, da se lahko vsako ravnino razdeljeno na področja, kot je na primer politični zemljevid držav, grofij, ali karkoli že, pobarva 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 je treba 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 se zapiše z besedami iz tistega časa: »dober matematični dokaz je kakor pesem - to pa je telefonski imenik!«
Zgodovina izreka uredi
Domnevo, ki predstavlja problem barvanja, je prvi predlagal 23. oktobra 1852 mladi južnoafriški matematik Francis Guthrie.[1]:103[2]:18[3] Pri barvanju angleških grofij je zapazil, da so za to potrebne le štiri barve. Guthriejev brat Frederick je bil študent Augustusa De Morgana na Univerzitetnem kolidžu v Londonu (UCL). Francis je poizvedoval o problemu pri bratu, ta pa ga je podal De Morganu. Guthrie je leta 1850 diplomiral na UCL, kasneje pa je poučeval matematiko na Južnoafriški univerzi v Kaapstadtu.
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.[3]
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.
Sklici uredi
- ↑ MacKenzie (2004), str. 103.
- ↑ Wilson (2000), str. 18.
- ↑ 3,0 3,1 Cayley (1879).
Viri uredi
- Cayley, Arthur (1879), »On the colourings of maps«, Proceedings of the Royal Geographical Society, Blackwell, 1 (4): 259–261, doi:10.2307/1799998, JSTOR 1799998
- MacKenzie, Donald A. (2004), Mechanizing Proof: Computing, Risk, and Trust, MIT Press, ISBN 0-262-13393-8
- Wilson, Robin James (2002), Four Colors Suffice, London: Penguin Books, str. 18, ISBN 0-691-11533-8
