DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000
Beispiele zur Färbung
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.