Java-Applet zum Färbungsproblem

Applet zur Ampelschaltung

1. Klicken Sie auf den Button 'Graph' und es öffnet sich ein Fenster mit dem zur Kreuzung passenden Graphen. Er besitzt entsprechend der Ampelnummerierung die Knoten 1 bis 11. Würde eine gleichzeitige Grünstellung zweier Ampeln auf der Kreuzung zu einem Konflikt, d.h. einer Behinderung führen, sind die zugehörigen Knoten durch eine Kante miteinander verbunden.
2. Färben Sie nun den Graphen durch Ziehen (linke Maustaste festhalten) eines farbigen Punktes von links auf den gewünschten Knoten; dieser erhält die bewegte Farbe. Eine Färbung ist unzulässig, wenn Knoten derselben Farbe durch eine Kante miteinander verbunden sind.
3. Schließen Sie nun das Fenster 'Graph', und Sie entdecken eine Leiste der im Graphen verwendeten Farben. Jede Farbe entspricht einer Grünphase, d.h. der gleichzeitigen Grünstellung der zugehörigen Ampeln. Klicken Sie auf eine Farbe, und verfolgen Sie das Geschehen auf der Kreuzung.
4. Klicken Sie auf 'Automatic', werden alle Farben einmal durchlaufen.
5. 'Reset' stellt den Ausgangszustand wieder her; kein Knoten ist gefärbt.
6. An der großen Ampel links oben erkennen Sie die Güte Ihrer Lösung. ROT bedeutet, Ihre Färbung ist unzulässig. GELB besagt, dass noch eine Verbesserung, d.h. eine Reduktion der verwendeten Farben möglich ist. GRÜN gibt an, dass eine Färbung mit minimaler Anzahl Farben gefunden wurde.
7. Es ist jederzeit möglich, eine Änderung der Einfärbung im Graphen vorzunehmen.