lunes, 5 de enero de 2015

TEOREMA DELS QUATRE COLORS

Recentment a classe de matèria optativa, hem treballat el teorema dels quatre colors. Nosaltres l'hem trobat molt interessant. Consisteix en el següent: qualsevol mapa (del tipus que sigui) es pot pintar amb un màxim de quatre colors diferents sense que els colors de les regions limítrofes coincideixin. A primera vista sembla impossible. Malgrat això, és demostrable.

L'any 1852 Francis Guthrier va plantejar la conjectura que més endavant va esdevenir el teorema dels quatre colors. Al cap d'un temps, l'any 1976, Kenneth Apple i Wolfgang Haken, mitjançant un ordinador, van convertir la conjectura en teorema, perquè la van comprovar
, utilitzant la teoria dels grafs. Qualsevol mapa es pot representar a través d'un graf. Seguint aquesta idea, assignarem un vèrtex per cada "comarca" i una aresta entre dos vèrtexs, si les comarques són limítrofes.

Algoritme d'acolorit

L'algoritme d'acolorit ens permet demostrar el teorema dels quatre colors:

  • Ordenem els vèrtexs en ordre decreixent segons el nombre d'arestes (grau). 
  • Assignem els colors a cada vèrtex seguint el següent procés:
                   - Assignem el color 1 al primer vèrtex.
                   - Assignem el color 1, si no és adjacent amb el primer, al segon vèrtex.
                   - En cas contrari, assignem el color 2. I així successivament.


  • Per acabar, acolorim el graf i tot seguit el mapa inicial.
Si seguiu aquest procés, veurem que el teorema funciona. Us animen a que intenteu pintar aquests mapes mitjançant l'algoritme d'acolorit!!





















Mapa senzill de les comunitats autònomes d'Espanya

























Mapa més complicat (Us veieu capaços?)




Martí Oró i Arnau Velàzquez











No hay comentarios:

Publicar un comentario