Ziel des Spiels ist es, den Graphen "gültig" zu färben, wobei so wenige Farben wie möglich verwendet werden sollen.
Damit ein Graph gültig gefärbt ist sind folgende Regeln zu beachten:
- Alle Knoten müssen mit einer der verfügbaren Farben gefärbt werden.
- Benachbarte Knoten (d.h. solche, die mittels einer Kante verbunden sind) müssen verschiedene Farben haben!
Die folgenden Bilder zeigen zwei Färbungen eines Graphen; die linke Färbung ist ungültig weil
beispielsweise die roten Knoten miteinander verbunden sind. Die rechte Färbung ist hingegen gültig.
Die aktuelle Farbe wird mit dem Symbol brush
markiert und kann mittels Klick auf eine andere Farbe gewechselt werden.
Knoten können nach dem Färben auch umgefärbt werden.
Das Spiel gilt dann als gewonnen, wenn der Graph mit der kleinstmöglichen Anzahl
von Farben gültig gefärbt wurde!
Fachliche Verantwortung: Benjamin Hackl, Angelika Wiegele
Technische Umsetzung: Benjamin Hackl, Johannes Gigacher, Lisa Knoblinger, Maximilian Molnar, Mattea Pötzi, Anita Schwaiger.
Feedback, Fragen oder Anmerkungen zu dieser Illustration von einfachen Graphfärbungsproblemen des
Instituts für Mathematik können gerne an benjamin.hackl@aau.at
gerichtet werden. Wir freuen uns darüber!