JavaScript-Applikation zum »Färbungsproblem«

Was tun?

1. Die Teilnehmerinnen und Teilnehmer eines Workshops haben angegeben, welche Vorträge (1 bis 9) sie in jedem Fall besuchen möchten. Diese Präferenzen sind in der nachfolgenden Tabelle zusammengestellt.
   Die Vorauswahl kann von Ihnen durch Anklicken verändert werden. Die Kanten im nebenstehenden Graphen wird damit gelöscht und durch Anklicken des Buttons »Build Graph« neu generiert.
   Mit »Clear Table« werden alle Positionen in der Tabelle wie auch die Kanten gelöscht.
   »Reset« lädt das ursprünglich vorgegebene Szenario.
2. Das Zeitraster sieht vor, dass ab 9:00 Uhr Vorträge stets zur vollen Stunde eingeplant werden. Für den Fall, dass alle Vorträge nacheinander gehalten werden, wäre der Workshop ohne Berücksichtigung einer Mittagspause also erst um 18:00 Uhr beendet.
   Die möglichen Anfangszeiten werden durch verschiedene »Farben« identifiziert. Das Anklicken einer Farbe, Gedrückthalten der linken Maustaste und Ziehen dieser Farbe in einen der Knoten 1 bis 9 färbt den betreffenden Knoten entsprechend ein.
3. Für eine gegebene Zuordnung kann dann jeweils festgestellt werden, ob Restriktionen, die durch die Kanten visualisiert sind, verletzt werden. Tragen zwei mit einer Kante inzidente Knoten dieselbe Farbe, wird die entsprechende Kante rot.
4. Ist der Graph zulässig eingefärbt, wird mit »Schedule« der zugehörige Zeitplan erzeugt, in den die Vorträge gemäß der gewählten Farben den Anfangszeiten und Räumen zugeordnet sind.
5. Mit Erzeugen des Zeitplans wird gleichzeitig durch Bestimmung der größten Clique eine untere Schranke für die chromatische Zahl ermittelt und unter den Schaltflächen angezeigt.