Page 4 - Grafentheorie HS 3 Graafkleuringen

HS 3 Graafkleuringen

3.1.3 Historiek van het vierkleurenprobleem

Eén van de problemen waarmee cartografen te maken hebben is het kleuren van landkaarten.
In 1852 stelde de plantkundige en wiskundige Francis Guthrie zich de vraag of elke landkaart kan
ingekleurd worden met ten hoogste vier kleuren en wel zodanig dat landen die aan elkaar grenzen
verschillende kleuren krijgen. Omdat Francis zijn universitaire studies al had beëindigd stuurde hij een
brief met deze vraag naar zijn broer Frederick, die toen wiskundecursussen volgde bij de bekende
wiskundige August De Morgan. Omdat ook hij dit probleem niet kon oplossen legde hij dit probleem
voor aan Sir William Hamilton.
In 1878 presenteerde een andere wiskundige Arthur Cayley het vraagstuk aan een London
Mathematical Society.

Francis Guthrie Arthur Cayley

In 1879 werd een artikel gepubliceerd waarin een Londense advocaat Arthur Kempe een bewijs gaf voor
het vermoeden dat 4 kleuren volstonden. Er bleek in dit bewijs echter een fout te zitten. Gedurende
zowat 100 jaar hebben vele wiskundigen een poging gedaan om te bewijzen dat het inkleuren van
landkaarten met ten hoogste vier kleuren altijd mogelijk is. Soms werd pas jaren later ontdekt dat er een
fout zat in het bewijs.
In 1976 bewezen de wiskundigen Kenneth Appel en
Wolfgang Haken met behulp van uitgebreide
computerberekeningen de vierkleurenstelling: voor een
willekeurige landkaart is het mogelijk om de landen met
ten hoogste vier kleuren zodanig in te kleuren dat geen
twee aangrenzende landen dezelfde kleur hebben.
We noemen twee landen aangrenzend als ze een grens
delen; landen die slechts in een punt aan elkaar liggen
t
(zoals twee overliggende stukken van een gesneden taart) e
zijn dus niet aangrenzend. Met een land bedoelen we n
.
bovendien een samenhangend deel van de kaart. o
l
Het bewijs van de vierkleurenstelling is het eerste bewijs e
h
van een “grote” stelling die met behulp van een computer
t
bewezen is. a
m
Afbeeldingen wikipedia.nl .
w

w
w

© 2021 Ivan De Winne ivan@mathelo.net 3