De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

Graaf met chromatisch getal 5

Ik kan eigenlijk kort zijn. Ik denk dat ik het vierkleurenprobleem begrepen heb maar concludeer hieruit dat het chromatisch getal van een graaf nooit groter kan zijn dan 4. Klopt dit? Indien ik mij vergis, kan u mij dan een graaf tekenen met chromatisch getal groter dan 4?

martie
3de graad ASO - woensdag 15 februari 2006

Antwoord

Dag Martien,

Je hebt bijna gelijk: het chromatisch getal van een PLANAIRE graaf is altijd maximum 4. Een planaire graaf is een graaf die je op een blad papier kan tekenen zonder dat verschillende bogen elkaar snijden. Als je vertrekt van een wereldkaart (het oorspronkelijke vierkleurenprobleem), en je stelt elk land als top voor, en je verbindt twee toppen als de landen aan elkaar grenzen, dan krijg je zo een planaire graaf.

Maar er zijn dus ook andere (niet-planaire) grafen, en die kunnen wel een hoger chromatisch getal hebben. Het verzinnen van voorbeelden is niet zo moeilijk: denk bijvoorbeeld aan de complete graaf met vijf toppen (dus vijf toppen en alle mogelijke bogen), om die te kleuren heb je vijf kleuren nodig, dus het chromatisch getal is vijf.

Groeten,
Christophe.

Christophe
Vragen naar aanleiding van dit antwoord? Klik rechts..!
donderdag 16 februari 2006



home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2024 WisFaq - versie 3