|
durch
eine Kante verbunden sind, heißen benachbart. Das Graphfärbungsproblem
besteht nun darin, die Knoten des Graphen mit möglichst wenig Farben so zu
färben, dass benachbarte Knoten stets verschieden gefärbt sind. Eine solche
Färbung eines Graphen wird meist durch eine Abbildung f : V  C dargestellt,
wobei C eine beliebige Menge von Farben ist. Die minimale Anzahl von Farben,
die benötigt wird, um einen gegebenen Graphen G zu färben, heißt auch die
chromatische Zahl von G, bezeichnet als  (G). Als Beispiel betrachte man Abb. 2:
Der dort dargestellte Graph lässt sich mit drei Farben färben (wir haben die
„Farben“ hier einfach durchnumeriert). Es ist auch leicht einzusehen, dass diese
Färbung optimal ist, da wir bereits drei Farben brauchen, um jedes der beiden
„Dreiecke“ im Graphen zu färben. Die chromatische Zahl dieses Graphen ist also 3.
Kommen wir nun auf das Anwendungsbeispiel der Kanalzuweisung zurück. In diesem Fall repräsentieren die Knoten die Sender, und die Kanten die Kopplungsbeziehungen zwischen den Sendern; sind zwei Knoten also durch eine Kante verbunden, so müssen die entsprechenden Sender verschiedene Kanäle erhalten. Der entstehende Graph wird auch als der Kopplungsgraph bezeichnet. Das Kanalzuweisungsproblem besteht also darin, den Kopplungsgraphen mit möglichst wenig Kanälen zu färben, und die chromatische Zahl des Kopplungsgraphen gibt die für ein interferenzfreies Netz benötigte Kanalzahl an. Die dargestellte graphentheoretische Modellierung des Kanalzuweisungsproblems, die auf die Arbeiten von W.K. Hale zurückgeht [Hale 1980] und beim SWR verfeinert wurde [Quellmalz 1993] bietet gegenüber anderen gebräuchlichen Verfahren, die mit regulären Netzstrukturen (z. B. Rautengittern) operieren, zwei entscheidende Vorteile. Zum einen sind die Ergebnisse und Verfahren der Theorie der Graphenfärbung direkt anwendbar. Zum anderen können mit Graphen im Prinzip beliebige |
