OR-Labor

Das Färbungsproblem in der Betriebswirtschaftslehre

Problemformulierung

Gegeben sei ein ungerichteter Graph G=(V,E) mit Knotenmenge V und Kantenmenge E. Die Knoten von G heißen zulässig gefärbt, wenn jedem Knoten eine Farbe so zugeordnet ist, dass die Knoten, die durch eine Kante verbunden sind, nicht dieselbe Farbe tragen. Man spricht auch vereinfachend von der Färbung des Graphen. Eine triviale Färbung erhält man, wenn jedem Knoten eine andere Farbe zugewiesen wird; bei n Knoten benötigt man genau n Farben. Interessant sind nun genau die zulässigen Färbungen, bei denen möglichst wenig Farben verwendet werden. Das Minimum der für eine zulässige Färbung von G erforderlichen Farben heißt die chromatische Zahl .

Anwendungen

Ampelschaltung
Die Ampeln stellen die Knoten im Graphen dar. Zwei Ampeln, die nicht gleichzeitig GRÜN zeigen dürfen, sind durch Kanten im Graphen verbunden. Eine Phase ist durch eine bestimmte Ampelschaltung charakterisiert. Eine solche Schaltung heißt dann zulässig, wenn die freigegebenen Wege nicht zu Verkehrskonflikten auf der Kreuzung führen. Versuchen Sie nun mit dem von uns programmierten Applet einmal selbst, eine möglichst gute Färbung eines Graphen zu finden.

Frequenzblockzuweisung im Bereich der Telekommunikation
Die Deutsche Telekom hat ein Softwarepaket zur Verteilung von Sendefrequenzen entwickelt, bei dem auch Tabu Search implementiert ist. Beim digitalen terrestrischen Hörrundfunk werden sechs Stereoprogramme zu einem Programmblock zusammengefasst und in einem Frequenzblock abgestrahlt. Für jedes Verbreitungsgebiet, in der Bundesrepublik können das mehrere Hundert sein, ist ein Frequenzblock erforderlich.
Herr Hackelbörger, Mitarbeiter im Technologiezentrum der Telekom in Darmstadt, gab interessante Erläuterungen (6MB), von denen Sie einen Ausschnitt hier sehen können. Das vollständige Interview finden Sie auf unserer CD Intelligente Strategien in Theorie und Praxis.

Konfliktfreie Lagerung von Sonderabfällen
Der sachgerechten Lagerung von Chemikalien wird bei Sicherheitsbetrachtungen oft wenig Bedeutung beigemessen, doch Unfälle wie der spektakuläre Lagerbrand bei der Firma Sandoz in Basel 1986 zeigen, dass auch mit der Lagerung schwer kalkulierbare Gefahren verbunden sein können. Kernpunkt der Abbildung des Lagerproblems auf das Graphenfärbungsproblem ist die Unterscheidung von unterschiedlichen Gefahrenklassen, die im Chemikaliengesetz unter Berücksichtigung des individuellen Gefahrengrades festgelegt ist. Ordnet man jeder Klasse einen Knoten im Graphen zu und drückt das Verbot der gemeinsamen Lagerung von Stoffen unterschiedlicher Klassen durch eine entsprechende Kante aus, so ergibt sich - wie Untersuchungen gezeigt haben - für das beschriebene allgemein formulierte Problem ein Graph mit 26 Knoten und 254 Kanten. Mit der vorgenommenen Transformation des Problems sind auch entsprechende Algorithmen anwendbar, die insbesondere für die Konzeption von Lagern und die damit verbundenen Entscheidungen von großer Bedeutung sind.

Applet-Seite

Zum Ampelproblem wurde von uns ein Applet programmiert, mit dem Sie einmal selbst die Einfärbung eines Graphen vornehmen können, um eine Ampelschaltung mit konfliktfreien Grünphasen zu generieren.
Die Lösung des Färbungsproblems mittels neuerer Verfahren wie Simulated Annealing und Tabu Search wird im multimedialen Lehrprogramm »Intelligente Strategien in Theorie und Praxis« behandelt.