Glossari

Seleccioneu una de les paraules clau de l’esquerra ...

Gràfics i xarxesPintar Mapa

Temps de lectura: ~15 min
Aquesta pàgina ha estat traduïda automàticament i pot contenir errors. Poseu-vos en contacte si voleu ajudar-nos a revisar les traduccions.

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

0 colours used

South America

0 colours used

Germany

0 colours used

England

0 colours used

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 i els països que connectat per una vora:

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 Francis Guthrie va haver de pintar un mapa de comtats d'Anglaterra. Va observar que quatre colors semblaven suficients per a qualsevol mapa que intentava, però no va ser capaç de trobar una prova que funcionés per a tots els mapes. Aquest va resultar ser un problema extremadament difícil, i es va fer conegut com el teorema de quatre colors .

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 Wolfgang Haken i Kenneth Appel van utilitzar un ordinador per solucionar-lo finalment. Van reduir infinitament molts mapes possibles a casos especials de 1936, els quals van ser verificats per un ordinador amb més de 1000 hores en total.

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.