Diese Abbildung könnte aus einem Ausmalbuch für Kinder entnommen sein. Das kleine
Seeungeheuer darauf staunt, dass es bei uns heut eine Rolle spielen wird. Aber
diese Abbildung hat doch nichts mit Graphen zu tun - oder?
Unsere Aufgabe: Das Bild soll so ausgemalt werden, dass zwei angrenzende Flächen
stets unterschiedliche Farben erhalten. Dabei wollen wir - im Gegensatz zur
"Färbewut" mancher Kinder - möglichst wenige Farben verwenden.
Betrachten wir also das Bild im Lichte der Graphentheorie: Die Linien sind Kanten
(1, 2,
3... ) ihre Kreuzungspunkte Knoten
(A, B,
C ...). Von jedem Knoten geht eine gerade Anzahl
von Kanten aus. Zum Beispiel gehen vom Knoten A,
die Kanten 1, 2,
13 und 6 aus.
So ist es bei all diesen Knoten, von ihnen gehen jeweils immer vier Kanten aus.
Einige Kanten sind sogar unbeschränkt (sie treffen keinen Knoten), aber auch deren
Anzahl ist gerade. Zum Beispiel sind die Kanten 14
und 15 unbeschränkt, außerdem sind es zwei
Kanten, also ist die Anzahl gerade.
Wir können also stets zwei Kanten miteinander verbinden.
Wenn ihr wissen wollt, was man mit diesem Graphen noch so alles anstellen kann,
dann geht einfach zur Knobelaufgabe 5 .
Na los traut euch!
Die zänkischen Nachbarn