Netzstrukturen dargestellt werden, so dass die realitätsnahe Modellierung irregulärer Netze unter Berücksichtigung von morphographischen und topographischen Gegebenheiten kein Problem darstellt.

Das Graphfärbungsproblem ist eines der klassischen mathematischen Optimierungsprobleme. In Gestalt der sogenannten „Vierfarben-Vermutung“ (darunter versteht man die erst in den 70er Jahren des 20. Jahrhunderts unter massivem Computer-Einsatz positiv beantwortete Frage, ob sich jede Landkarte mit vier Farben so färben lässt, dass zwei benachbarte Länder stets verschieden gefärbt sind) begegnet es uns bereits in einer Mitteilung von Guthrie an de Morgan um 1850, und möglicherweise war der durch sein Band berühmt gewordene Mathematiker Möbius bereits 1840 mit diesem Problem vertraut. Außerdem ist das Graphfärbungsproblem eines jener grundlegenden Probleme, die man auch dem mathematischen Laien in zehn Minuten erläutern kann, das aber nichtsdestotrotz extrem schwierig zu lösen ist. Es handelt sich dabei um eines jener berüchtigten „NP-vollständigen“ Probleme, die sich allem Anschein nach nur durch systematische Aufzählung sämtlicher Lösungsalternativen optimal lösen lassen. Da eine solche Vorgehensweise aber exponentiellen Rechenaufwand erfordert, muss man sich zur Lösung konkreter Anwendungsprobleme i.a. mit heuristischen Näherungsverfahren behelfen, die in vernünftiger Zeit ein „hinreichend gutes“ (allerdings nicht notwendigerweise optimales) Ergebnis liefern. Für das Graphfärbungsproblem gibt es eine ganze Reihe solcher heuristischer Lösungsverfahren, z. B. den sogenannten „sequentiellen“ Färbungsalgorithmus. Allerdings können auch diese Verfahren keine gleichbleibende Lösungsgüte garantieren, was u. a. damit zusammenhängt, dass selbst das Problem, eine näherungsweise optimale Graphfärbung zu finden, zu den NP-vollständigen Problemen gehört. (Leider können wir im Rahmen dieses Beitrags nicht auf die mathematischen Details der NP-Vollständigkeit und der Graphfärbungsverfahren eingehen. Der interessierte Leser sei dazu auf [Garey/Johnson 1979] und [Jensen/Toft 1995] verwiesen.)

Im Zusammenhang mit Graphfärbungsheuristiken sind auch untere Schranken für die chromatische Zahl eines Graphen interessant. Diese können nämlich dazu verwendet werden, die Qualität einer mit einer Heuristik gefundenen Lösung abzuschätzen. Eine solche untere Schranke liefert die Clique-Zahl eines Graphen, die auch mit (G) bezeichnet wird. Es handelt sich dabei um die maximale Anzahl von Knoten, die innerhalb des Graphen paarweise benachbart sind. Da alle Knoten einer solchen Clique paarweise verschieden gefärbt werden müssen, ist stets (G) < (G). Z. B. ist 3 die Clique-Zahl des Graphen in Abb. 2 (der Graph hat zwei Cliquen der Größe 3, nämlich die beiden „Dreiecke“), daher ist die angegebene Färbung mit drei Farben optimal. Allgemein gilt: Finden wir für einen beliebigen Graphen G eine Färbung mit k Farben, so beträgt die Abweichung dieser Lösung vom Optimum höchstens (k - (G))/(G) × 100%.

Leider ist auch die Berechnung der Clique-Zahl ein NP-vollständiges Problem. Für eine ganze Reihe von eingeschränkten Klassen von Graphen (z. B. für die sogenannten „Einheitskreisscheiben-Graphen“, die bei der Modellierung einfacher Sendernetze auftreten, s. [Clark/Colbourn/Johnson 1990]) gibt es jedoch effiziente Lösungsverfahren. Für den allgemeinen Fall gibt es immerhin ein Enumerationsverfahren, den Algorithmus von Carraghan und Pardalos [1990], das oft für kleinere,