Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Beispiele zur Färbung

Leider zeigt Ihr Brouwser keine Java Applets an.
Versuchen Sie doch diese Graphen mit 4 oder weniger Farben zu färben. Der Computer weigert sich, unzulässig zu färben). Graph A entsteht aus dem Vorlesungsbeispiel: Die Ecken sind die Vorlesungen, und solche Vorlesungsecken sind benachbart, wenn es gemeinsame Studenten gibt. Graph B enthält (sogar mehrere) vollständige Teilgraphen mit 3 Ecken, weshalb wir sicher 3 Farben brauchen. Kommen wir hier auch mit 3 Farben aus? Graph C enthält keinen vollständigen Teilgraphen mit 3 Ecken. Wieviel Farben brauchen wir hier?
Erich Prisner
erstellt im Juni 2000.