Gràfics i xarxesPintar Mapa
Ja hem utilitzat la teoria de gràfics amb determinats mapes. A mesura que ens reduïm, les carreteres i ponts individuals desapareixen i, en canvi, veiem el traç de països sencers.
Quan es colora un mapa o qualsevol altre dibuix format per regions diferents, els països adjacents no poden tenir el mateix color. També potser voldríem utilitzar el mínim color possible.
Alguns “mapes” simples, com un tauler d’escacs, només necessiten dos colors (blanc i negre), però els mapes més complexos necessiten més.
Al pintar el mapa dels estats dels Estats Units, òbviament són suficients 50 colors, però són necessaris molt menys. Proveu de pintar els mapes a continuació amb el mínim color possible:
United States
South America
Germany
England
Tots aquests mapes poden ser acolorits només amb quatre colors diferents, però no és difícil imaginar que altres mapes molt complicats poden necessitar molts més colors. De fet, alguns mapes necessiten almenys quatre colors, sempre que contenen quatre països tots connectats entre si.
Com abans, podem convertir un mapa amb països i fronteres en un gràfic pla: cada país es converteix
Ara volem acolorir els vèrtexs d’un gràfic i dos vèrtexs han de tenir un color diferent si estan connectats per una vora.
El 1852, l'estudiant de botànica
Durant els següents 100 anys, molts matemàtics van publicar “proves” al teorema de quatre colors, només per trobar errors després. Algunes d’aquestes proves no vàlides eren tan convincents que van trigar més de deu anys a descobrir errors.
Durant molt de temps, els matemàtics no van poder demostrar que són suficients quatre colors o bé trobar un mapa que necessités més de quatre colors.
Es van progressar poc en el problema dels quatre colors fins al 1976, quan
El teorema de quatre colors és el primer teorema matemàtic conegut que es va provar mitjançant un ordinador, cosa que des de llavors s’ha convertit en molt més comuna i menys controvertida. Els ordinadors més ràpids i un algorisme més eficient significa que avui podeu demostrar el teorema de quatre colors en un ordinador portàtil en poques hores.
Postmark for the Department of Mathematics at the University of
Illinois Urbana-Champaign, where Haken and Appel worked.
El teorema de quatre colors només funciona per mapes en un pla pla o una esfera, i on tots els països consisteixen en una sola àrea.
Tanmateix, els matemàtics també han mirat mapes d’ imperis , on els països poden constar de múltiples components desconnectats i mapes en planetes de forma diferent, com ara un toro (forma de donut). En aquests casos, és possible que necessiteu més de quatre colors, i les proves es fan encara més difícils.
This map on a torus requires seven colours.
English
عربى
Azərbaycan
Català
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng Việt