Kenneth Appel

Transcription

En teoría de grafos, un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano, sin que ninguna arista se cruce. Una coloración apropiada de un grafo plano, es el resultado de colorear los vértices, de modo que dos vértices unidos por una misma arista, no pueden tener el mismo color. Igual que coloreamos vértices, podemos colorear las regiones del plano separadas por las aristas. Este es el caso de los mapas. Todos hemos visto un mapa geopolítico con los estados coloreados, donde dos estados fronterizos tienen colores distintos. Determinar el menor número necesario de colores para colorear este tipo de mapas, ha sido un problema que ha interesado durante un siglo. Alrededor de 1850, Francis Guthrie, trataba de colorear una carta de los condados de Inglaterra, de manera que se viesen rápidamente los condados colindantes y sus fronteras. Para su propósito, coloreaba con colores distintos los condados fronterizos. Tras varios intentos, observó que con cuatro colores tenía suficiente para colorear todo la carta, sin que coincidieran en el mismo color dos condados colindantes. ¿Era ese el mínimo número de colores necesario para todos los posibles mapas? Francis mostró el problema a su hermano Frederick, quien a su vez se lo enseñó a su profesor del College Augustus De Morgan. De Morgan no supo darle una respuesta, y dos años después se lo plantearía a uno de los más eminentes matemáticos de las Islas: William Hamilton, sí el mismo de los cuaterniones. Pero a Hamilton no le interesó el problema. Sí medró en otro de los matemáticos, que junto a Hamilton estaban cimentando la escuela británica moderna de matemáticas puras: Arthur Cayley. En 1878, durante una reunión de la Sociedad Matemática de Londres, Arthur Cayley lo presenta formalmente, para que la comunidad matemática intente resolverlo. El problema lo enuncia así: Todo mapa plano puede colorearse con, como máximo, cuatro colores, con la condición de que regiones con frontera común tengan colores distintos. Todos los retos son buenos, y cuando estos implican derrotar a eminencias que no lo han conseguido, aumenta el interés de los poco conocidos. Al año siguiente Alfred Kempe, alumno de Cayley, presenta una demostración de la conjetura; pero en 1890 Percy Heawood encontró un fallo insalvable en la demostración. Heawood no fue completamente destructivo con Kempe, probó que adaptando la prueba de Kempe, podía probarse que con cinco colores bastaba para colorear cualquier grafo plano. Así que la conjetura permaneció sin resolverse hasta 1976, cuando Kenneth Appel y Wolfgang Haken resolvieron la conjetura de los cuatro colores, para ello utilizaron un ordenador, donde ejecutaron un algoritmo que permitía reducir cualquier mapa a una de las 1482 configuraciones inevitables con una coloración máxima de cuatro colores. El proceso necesitó de 1200 horas (50 días) de computación en un IBM 360. Para atestiguar la demostración se requirió de una publicación de 140 páginas. Posteriormente, otras pruebas reafirmaron que el planteamiento de Appel y Haken era correcto. La demostración por ordenador del teorema de los cuatro colores no solo fue un reto, además abrió el camino de una nueva forma de demostración matemática. En 1998 Thomas Hales anunció que había demostrado la conjetura de Kepler sobre el empaquetamiento de esferas. La comprobación de Hales es una demostración por casos en la que se prueban agrupamientos mediante complejos cálculos de ordenador. A finales del siglo pasado las máquinas dejaron de hacer solo cálculos, y demostraron teoremas. Pero esa, es otra historia.