Teorema dels quatre colors

Quants colors creieu que fan falta per tal d’acolorir un mapa sense que dues regions limítrofes (que estan l’una al costat de l’altre) tinguin el mateix color sense considerar les que es tallen en un sol punt? Dos? Vuit? Cinc?

El teorema dels quatre colors diu que qualsevol mapa dibuixat sobre un pla o sobre una esfera es pot acolorir amb quatre colors distints de manera que dues regions adjacents no siguin del mateix color, com per exemple en aquest mapa

Francis Guthrie

El teorema va ser plantejat per primer cop l’any 1852 per Francis Guthrie a la seva germana després d’acolorir un mapa de Gran Bretanya. El problema es va plantejar de la següent manera: “Són suficients quatre colors per acolorir qualsevol mapa imaginable de manera que cap país amb límits comuns tingui el mateix color?”. I així una simple pregunta per divertir a una germana, es va convertí en un problema matemàtic que va estar obert més de 100 anys.

 

El teorema va ser demostrat l’any 1976 per Kenneth Appel i Wolfgang Hanken. Va ser una demostració que va crear una gran polèmica degut a que va ser assistida per un ordinador i per tant era impossible de comprovar a mà per un humà. Aquesta demostració es basava en demostrar que hi ha un conjunt particular de 1.936 mapes, cadascun dels quals no pot formar part d’un contraexemple de mida més petita pel teorema dels quatre colors i aquests mapes van ser comprovats per un ordinador. Anys més tard, el 1997, va ser demostrat d’una manera més senzilla per Neil Robertson, Daniel P. Sanders, Paul Seymour i Robin Thomas. El 2005, Benjamin Werner i Georges Gonthier van formalitzar una demostració del teorema dins de l’assistent de proves Coq. La resolució d’aquest teorema està molt lligada amb la Teoria de Grafs, ja que va definir termes i conceptes fonamentals per a l’estudi dels grafs (els grafs són col·leccions d’objectes, anomenats vèrtex connectats per línies anomenades arestes.

Kenneth Appel (sentat) i Wolfgang Hanken (dret)

Martin Gadner deia haver trobat un contra-exemple de la teoria dels quatre colors, però era fals. Aquí us deixem el mapa que va fer perquè el pugueu veure i provar de resoldre’l només usant quatre colors: http://www.xtec.cat/~jjareno/problemes/geometrics/4_colors_e.htm

Però… com podem estar segurs de que estem acolorint un mapa amb el mínim de colors necessaris? Doncs utilitzant l’algoritme d’acolorit.

Primer hem de saber que tot mapa, en el pla o en l’esfera pot ser representat mitjançant graf i si cap aresta es talla amb una altra el graf s’anomena planar. Així doncs, començarem l’algoritme fent el graf planar corresponent al mapa que volem acolorir. Cada regió serà un vèrtex i posarem una aresta entre els vèrtexs que representin regions contigües.

Tot seguit, ordenarem els vèrtexs en ordre decreixent segons el grau (nombre d’arestes que té un vèrtex).

Assignarem colors a cada vèrtex de la següent manera:

1. Assignarem el primer color al primer vèrtex.
2. Al segon vèrtex li assignarem el primer color si no és adjacent i si ho és li assignarem el segon color.
3. Si el tercer vèrtex és adjacent a tots dos anteriors li assignarem el tercer color, si no és adjacent al primer vèrtex li assignarem el primer color i si és adjacent al primer, però no al segon vèrtex li assignarem el segon color.
4. Seguirem amb aquest procés fins que haguem assignat un color a tots els vèrtex.

Finalment acolorirem el graf i tot seguit el mapa.

En aquest enllaç podreu veure aquest procés d’acolorit, pas a pas, per al mapa de les Comunitats Autònomes d’Espanya, i veureu que és suficient pintar-lo amb només 3 colors.

Els grafs planars van ser ideats per Euler, un famós matemàtic molt important. A continuació us deixem un vídeo sobre la vida d’aquest home.

A la següent entrada, uns companys nostres us explicaran com saber si un graf es pot recòrrer d’una sola passada!

Advertisement