SEGRE
teoria dels grafs

teoria dels grafs

detail.info.publicated

Creat:

Actualitzat:

Si vostè té canalla en algun moment li haurà tocat pintar el mapa de les comarques catalanes. Quants colors diferents necessita per pintar-lo? Amb un no en tindrà prou, ni amb dos tampoc. I amb tres colors? Per exemple si pintem el Pla d’Urgell de verd, la Noguera i les Garrigues les podem pintar de groc i el Segrià i l’Urgell de blau, amb tres colors en tindríem prou. I el Pla de l’Estany? Si el pintem de groc, la Garrotxa i el Gironès les hem de pintar de colors diferents perquè limiten totes entre elles, per tant ja necessitem tres colors. I quan pintem l’Alt Empordà necessitarem un altre color perquè té frontera amb les tres comarques anteriors. Necessitem quatre colors. Però en tindríem prou amb quatre colors per a pintar qualsevol mapa per recargolat que sigui? Això es preguntà fa 150 anys Francis Guthrie pintant un mapa dels comtats d’Anglaterra. Mogut per la curiositat ho comentà al seu germà, el físic Frederick Guthrie qui ho traslladà al seu profe de matemàtiques, Augustus de Morgan. Aquest no mostrà gaire interès i s’encarregà de difondre-ho a Hamilton, un altre matemàtic, i al filòsof William Whewell. El problema dels colors creuà l’Atlàntic i Charles Sanders Peirce digué que tenia una demostració... però no l’arribà a escriure.

Un altre il·lustre de les matemàtiques, Arthur Cailey, l’any 1878 el presenta a la London Mathematical Society. El problema queda obert amb l’enunciat “tot mapa pla pot pintar-se amb, com a màxim, quatre colors amb la condició que regions amb frontera comuna tinguin colors diferents”. L’any 1879 Arthur Kempe va publicar una demostració... semblava que el problema estava resolt... però l’any 1890 Percy Heawood hi trobà una errada. El problema es començà a fer molt famós i cap matemàtic aconseguia donar-ne una demostració vàlida. Fins i tot l’arquebisbe de Canterbury Frederick Temple amb il·luminació divina gosà publicar una demostració que també resultà errònia, i Lewis Carroll l’usava per plantejar enigmes matemàtics.

Al segle XX es comença a pensar en els ordinadors per trobar aquesta demostració. El matemàtic alemany Heinrich Heesch fou el pioner fent servir la programació en Algol 60. Finalment, l’any 1976 Kenneth Appel i Wolfgang Haken van anunciar oficialment que “amb 4 colors n’hi ha prou”. La demostració es feu en un ordinador IBM 360 i ocupà 1.200 hores de processament de dades (50 dies!).

tracking