Firfarveproblemet

Fra Wikipedia, den frie encyklopædi

Firfarveproblemet er fra 1852, hvor en englænder ved navn Francis Guthrie opdagede at man øjensynlig kunne nøjes med 4 farver når man skulle farvelægge landkort således at to tilstødende områder ikke får samme farve.

Francis Guthrie var fascineret af problemstillingen, og fortalte om det til sin yngre broder Frederick, der læste på University College i London. Francis’ bror bragte problemet videre til hans professor August de Morgan, som igen bragte det videre til den irske matematiker og fysiker William Rowan Hamilton. Problemet cirkulerede nu rundt blandt matematikere i hele Europa, men dette var et hård nød at knække ingen kunne løse det. Men i 1879 publicerede den engelske matematiker Alfred Bray Kempe en artikel, hvori han hævdede at have fundet en løsning. Dette vakte anerkendelse han blev slået til ridder og medlem af Royal Society.

Men i 1890 skrev Percy John Heawood, at der var en fejl i Alfred Bray Kempes bevis. Percy kunne vise at der højest skulle bruges 4 eller 5 farver og ikke flere.
Efter en længere tilstand i bevisførelsen begyndte der at komme gennembrud i 1922, Philip Franklin kom med et bevis på at kort med 25 områder altid kan dækkes med 4 farver. I 1926 kom Reynold med et lignende bevis for 27 områder, og i 1940 udvidede Winn det til 35 områder, i 1970 kom Ore og Stemple op på 39 områder.

I 1970 begynder to matematiker ved University of Illinois, Wolgang Haken og Kenneth Appel at arbejde med problemet. De fandt frem til at alle kort kunne konstrueres ud fra et endeligt antal grundtyper af kort, der var 1482 typer af kort hvorfra alle kort kunne tegnes. Nu var det bare at gå alle disse grundtyper igennem for firfarveproblemet. Men dette var et uoverkommeligt arbejde for selv de bedste matematiker-teams. Selv for computere ville det være en meget stor opgave, det ville tage 100 år at gennemgå alle muligheder. Haken og Appel begyndte at tænke andre strategier og genveje, således at problemet eventuelt kunne løses via computer. Det lykkedes og i juni 1976 blev problemet løst med 1200 timers computerarbejde – det første matematiske bevis udført via computer.