Teilprojekt II.1.2: Färbungsalgorithmen in der Sendefrequenzplanung

Teilprojekt II.1.2: Färbungsalgorithmen in der Sendefrequenzplanung

Projektkoordination: Dr. Frank Wankmüller (Stellvertretender Vorsitzender des IAK Musikinformatik; Abteilung Musikinformatik, FB 16)

Projektleitung: Univ.-Prof. Dr. Clemens Lautemann (Institut für Informatik, FB 17), Dr. Frank Wankmüller (Abteilung Musikinformatik, FB 16)

Projektmitarbeiter: Dr. Albert Gräf, Martin Stumpf, Gerhard Weißenfels (Abteilung Musikinformatik, FB 16)

Förderung: Ministerium für Wirtschaft, Verkehr, Landwirtschaft und Weinbau Rheinland-Pfalz

Inhalt

• Der Interdisziplinäre Arbeitskreis Musik- und Kunstinformatik
• Beteiligte Institutionen
• Projektleitung
• Projektmitarbeiter
• Die Problemstellung
• Der Lösungsansatz
• Ergebnisse
• Ausblick
• Literatur

Detailinformationen

• NP-Vollständigkeit
• Das Graphfärbungsproblem
• Verallgemeinerte Graphfärbungsprobleme

Am Interdisziplinären Arbeitskreis "Musik- und Kunstinformatik" nehmen Wissenschaftler aus den Bereichen Musik, Musikwissenschaft, Informatik, Mathematik, Bildende Kunst, Nachrichtentechnik, Physik, Biologie, Psychologie und andere teil, die sich mit fächerübergreifenden Vorhaben in Forschung und Lehre befassen.

Aufgaben des Arbeitskreises sind:

1. Vorbereitung und Förderung von interdisziplinären Forschungsvorhaben
2. Durchführung und Förderung von interdisziplinären Lehrveranstaltungen
3. Förderung der Zusammenarbeit von Universität, Wirtschaft und anderen Institutionen

Vorsitzender: Univ.-Prof. Dr. Christoph-Hellmut Mahling (FB 16, Musikwissenschaftliches Institut)

Stellvertretender Vorsitzender: Dr. Frank Wankmüller (FB 16, Abteilung Musikinformatik)

Abteilung Musikinformatik

Die Abteilung Musikinformatik widmet sich seit 1991 der Durchführung umfangreicher Drittmittelprojekte in den Bereichen der Musik- und Kunstinformatik und der Medientechnik. Dazu zählen insbesondere die vom Ministerium für Wirtschaft und Verkehr Rheinland-Pfalz geförderten Projekte "Rechnergestützter Arbeitsplatz für Musiker (COMES)", die hier dargestellten FMS-Projekte "Datenreduzierte digitale Speicherung von Musik und Sprache für Archive in Forschung und Rundfunk" und "Färbungsalgorithmen in der Sendefrequenzplanung", sowie das von der Stiftung Rheinland-Pfalz für Innovation geförderte Projekt "Entwicklung eines Konzepts verteilter objektorientierter Bilddatenbanken im technischen und künstlerischen Einsatzfeld am Beispiel eines Informationssystems zum Werk Pablo Picassos". Die Forschungsvorhaben wurden auf verschiedenen Ausstellungen (Hannover-Messe, CeBit, PC-Tage an der Johannes Gutenberg-Universität, Rheinland-Pfalz-Tag in Ludwigshafen, Ausstellung im Landtag anläßlich der Präsentation der Universität) dargestellt. Desweiteren wurde über alle Musikinformatik-Projekte mehrfach und ausführlich in Fernsehen, Hörfunk und Presse berichtet.

Im musikwissenschaftlichen Bereich bildet das Thema "Würfelmusik" einen weiteren kleinen Forschungsschwerpunkt. Zum einen kann "Würfelmusik" als Vorläufer der Algorithmischen Komposition angesehen werden, zum anderen geben z.B. die Arbeiten von Kirnberger einen wichtigen Einblick in die Werkstatt eines Komponisten der damaligen Zeit. Besonders gelungene Beispiele sind "Der allezeit fertige Polonoisen- und Menuettencomponist" und "Methode Sonaten aus 'm Ermel zu schüddeln". (Zum Abspielen einer Würfelsonate bitte auf die Abbildung klicken.)

Institut für Informatik

Das Institut für Informatik wurde 1990 gegründet. Durch drei Professoren, einen Hochschuldozenten, zwei wissenschaftliche Assistenten sowie derzeit sechs wissenschaftliche Mitarbeiter sind hier etliche Teilgebiete der Angewandten, Praktischen und Theoretischen Informatik vertreten. Es gibt an der Johannes Gutenberg-Universität keinen Informatik-Diplomstudiengang, wir führen Nebenfach-Ausbildung in Informatik für eine Vielzahl von Studiengängen durch; auch eine Promotion in Informatik ist am Institut möglich. (Nähere Informationen zum Studium: Dr. H.J. Schröder, Tel.: 39-3605)

Entsprechend dieser Rolle in der Lehre ist auch die Forschung am Institut stark interdisziplinär geprägt.

In einer Reihe von Projekten arbeiten wir mit unterschiedlichen Anwendungsbereichen zusammen.

Am FMS beteiligte Professoren mit Forschungsgebieten und Forschungsprojekten

• Prof. Dr. Herbert GÖTTLER
• Programmiersprachen (insbesondere visuelle)
• Compilerbau
• Graphgrammatiken
• Projekte
• Entwicklung von graphenbasierten Werkzeugen für die semantische Modellierung objektorientierter Datenbanken im Multimediabereich sowie visuelle Recherchesprachen
• Prof. Dr. Clemens LAUTEMANN
• Effiziente Algorithmen
• Komplexitätstheorie
• endliche Modelltheorie
• Projekte
• Graphalgorithmen zur Optimierung von Sendernetzen
• Logische Unterteilung von Komplexitätsklassen
• Gewinnstrategien in Logik-Spielen

Clemens Lautemann, Studium der Mathematik in Marburg, Bielefeld und Berlin, Diplom 1979 an der FU Berlin. Danach wissenschaftlicher Mitarbeiter am FB Informatik der TU Berlin, dort 1983 Promotion zum Dr. rer. nat. 84-89 Lehr- und Forschungstätigkeiten in Edinburgh, Bremen und Oldenburg, seit 1989 Professor für Informatik an der Johannes Gutenberg-Universität Mainz.
Arbeitsgebiete: Komplexitätstheorie, effiziente Algorithmen für kombinatorische Probleme.

Frank Wankmüller studierte von 1971 bis 1976 Informatik an der Universität Dortmund und war anschließend bis 1983 wissenschaftlicher Mitarbeiter. 1982 promovierte er mit einer Arbeit zum Thema "Charakterisierung von Graphklassen durch verbotene Strukturen und Reduktionen”. Besondere Beachtung fand der wissenschaftliche Wettbewerb "Busy Beaver”, den er im Rahmen der 6. Fachtagung "Theoretische Informatik” der Gesellschaft für Informatik veranstaltete. Ziel war es, möglichst einfache Programme zur Berechnung möglichst komplizierter Funktionen zu finden.
Nach kurzer Zeit als Hochschulassistent an der Universität Osnabrück und nach Vertretung einer Professur an der Universität Dortmund wechselte er zum WS 1984/85 an die Johannes Gutenberg-Universität, wo er seit 1991 den neu eingerichteten Bereich "Musikinformatik” am Musikwissenschaftlichen Institut leitet.
Bereits 1981 begannen die Arbeiten an dem Projekt "Rechnergestützter Arbeitsplatz für Musiker COMES”. Dieses Vorhaben wurde von 1989 bis 1992 im Rahmen des Programms "Wirtschaftsnahe Forschung” vom Ministerium für Wirtschaft, Verkehr, Landwirtschaft und Weinbau gefördert. Dieses Projekt war der Ausgangspunkt für die Arbeiten der Mainzer Universität im FMS.
Zur Zeit ist Dr. Wankmüller stellvertretender Vorsitzender des Interdisziplinären Arbeitskreises "Musik- und Kunstinformatik" an der Johannes Gutenberg-Universität, Mitglied in der Projektgruppe 14 "Informatik im nichttechnischen Bereich" des Technologiebeirates des Landes Rheinland-Pfalz und Mitglied im Arbeitskreis III "Mehrwertedienste" des DAB-Pilotversuches Baden-Württemberg.

Albert Gräf hat Mathematik mit Schwerpunkt Informatik an der Johannes Gutenberg-Universität Mainz studiert, wo er 1995 auch mit einer Dissertation zum Thema "Erkennung und Färbung spezieller Graphklassen” promovierte. Seine Hauptinteressensgebiete liegen in den Bereichen Compilerbau, funktionale Programmiersprachen, algorithmische Graphentheorie und kombinatorische Optimierung. Sein besonderes Interesse gilt der Analyse und Lösung komplexer Optimierungsprobleme aus der Praxis. Von 1991 bis 1995 war er in der Abteilung Musikinformatik als Mitarbeiter im Projekt "Färbungsalgorithmen in der Sendefrequenzplanung” tätig und ist dort seit 1996 wieder als wissenschaftlicher Mitarbeiter mit der Vorbereitung fortführender Drittmittelprojekte im Bereich der Lösung von Planungsproblemen in der Informations- und Telekommunikationstechnik beschäftigt.

Martin Stumpf, Jahrgang 1966, Studium der Mathematik und Betriebswirtschaftslehre an der Johannes Gutenberg-Universität Mainz. Diplomarbeit 1991 über "Endliche Markov-Ketten und ihre Anwendung auf Optimierungsprobleme”. 1992 bis 1995 wissenschaftlicher Mitarbeiter im Projekt "Färbungsalgorithmen in der Sendefrequenzplanung”. Interessen: probabilistische Optimierungsstrategien, Fehlerabschätzung bei Heuristiken.

Gerhard Weißenfels studierte Mathematik mit Schwerpunkt Informatik an den Universitäten Bonn und Mainz. Er schloß 1994 sein Studium in Mainz ab, wo er zur Zeit wissenschaftlicher Mitarbeiter am Institut für Informatik ist. Seine Hauptinteressengebiete liegen in den Bereichen Komplexitätstheorie, algorithmische Graphentheorie und kombinatorische Optimierung. 1995 war er als wissenschaftlicher Mitarbeiter im Projekt "Färbungsalgorithmen in der Sendefrequenzplanung” tätig.

Die Problemstellung

Ausgehend von dem vom Südwestfunk erstellten Sendernetzmodell widmet sich die Arbeitsgruppe "Sendefrequenzen” der Abteilung Musikinformatik der Lösung der kombinatorischen Optimierungsprobleme, die sich bei der Sendefrequenzplanung ergeben. Es handelt sich dabei um bekanntermaßen schwierige, nämlich sogenannte "NP-schwierige” Probleme, zu deren Lösung neueste Ansätze und Verfahren der algorithmischen Graphentheorie benötigt werden. Diese Probleme können daher nur durch eine intensive interdisziplinäre Zusammenarbeit zwischen Nachrichtentechnikern und Informatikern gelöst werden.

Ausgangspunkt der Problemformulierung ist das vom Südwestfunk entwickelte graphentheoretische Modell. In diesem Modell wird jeder Sender durch einen Knoten repräsentiert, wobei sich gegenseitig störende Sender durch eine Kante verbunden werden (siehe Abbildung). Im einfachsten Fall müssen sich störende Sender durch Wahl verschiedener Kanäle entkoppelt werden. Daraus ergibt sich das sogenannte Graphfärbungsproblem: die Knoten eines gegebenen Graphen sollen mit möglichst wenig verschiedenen Farben so eingefärbt werden, daß je zwei durch eine Kante verbundene Knoten stets verschieden gefärbt sind. (Drücken Sie bitte auf Färben, um den Graphen in der Abbildung korrekt einzufärben.)

Bereits für relative kleine Knotenzahlen wird das Färben eines Graphen mit kleinstmöglicher Farbenzahl ein manuell nicht mehr zu bewältigendes Problem, da zu viele verschiedene Lösungsmöglichkeiten zu beachten sind. Tatsächlich handelt es sich bei der Graphfärbung um ein sogenanntes NP-schwieriges Problem. Alle derzeit bekannten Verfahren zur optimalen Lösung solcher Probleme beruhen darauf, daß man im Prinzip alle denkbaren Lösungsalternativen, d.h. sämtliche möglichen Färbungen, "durchprobiert”. Bereits für relativ kleine Graphen ergibt sich so jedoch schon eine astronomische Anzahl von Lösungsmöglichkeiten. Nehmen wir der Einfachheit halber an, daß unser Färbungsalgorithmus sämtliche Zerlegungen einer n-elementigen Menge in disjunkte Teilmengen als Lösungkandidaten berücksichtigt, so ergibt sich als Anzahl der potentiellen Lösungen:

Dabei bezeichnet

Diese Größenordnungen sind bei der Größe realistischer Sendernetze selbst für modernste Supercomputer nicht mehr zu bewältigen. Ein einfaches Zahlenbeispiel: Wenn wir pro Sekunde eine Million Lösungskandidaten überprüfen können, so benötigen wir zur Berechnung der optimalen Färbung eines 10-knotigen Graphen ca. eine Zehntelsekunde, für 15 Knoten etwa 23 Minuten, aber für 20 Knoten bereits gut anderthalb Jahre. Während der Berechnung für einen Graphen mit 25 Knoten würde unsere hypothetische Maschine wahrscheinlich zu Staub zerfallen, dauert diese Berechnung doch knapp 150.000 Jahre! Auch wenn wir gewillt sind, gut anderthalb Jahre auf das Ergebnis der Berechnung zu warten, so versetzten uns selbst tausendfach schnellere Rechnern nur in die Lage, das Problem statt für 20 nun auch für bis zu 23 Knoten lösen zu können.

Damit ist klar, daß das Graphfärbungsproblem (und daher auch die Sendernetzplanung) mit schierer Rechenleistung allein nicht zu lösen ist. Man ist stattdessen darauf angewiesen, mit vernünftigem Rechenaufwand Lösungen zu berechnen, die der optimalen Lösung (der Lösung mit minimaler Farbenzahl) möglichst nahekommen. Dies ist umso wichtiger angesichts der Tatsache, daß es sich bei der allgemeinen Form des Frequenzplanungsproblems tatsächlich um eine verallgemeinerte Form des hier skizzierten Graphfärbungsproblems handelt.

• stochastische Methoden (z.B. Simulated Annealing, Tabu Search, genetische Algorithmen)
• problemspezifische Heuristiken (z.B. sequentielle Graphfärbungsalgorithmen)
• geometrische Verfahren (z.B. Branch and Cut)

Für das vorliegende Problem der Frequenzplanung sind jedoch alle diese Verfahren nur bedingt tauglich, da sie einesteils für die betrachteten Problemgrößen zu ineffizient sind (z.B. Simulated Annealing) und anderenteils keine A-Priori-Aussagen über die Qualität der gefundenen Lösung gestatten (z.B. sequentielle Färbungsalgorithmen). Tatsächlich läßt sich für das Graphfärbungsproblem nachweisen, daß die "hinreichend gute” Approximation einer optimalen Lösung des Graphfärbungsproblems schon NP-schwierig ist. Hierbei ist "hinreichend gute Approximation” in dem Sinne zu verstehen, daß, für eine beliebige gegebene Konstante c, die gefundene Lösung stets höchstens c-mal schlechter ist als die optimale Lösung mit kleinstmöglicher Farbenzahl.

Die Arbeitsgruppe "Sendefrequenzen” verfolgt daher den Ansatz, die betrachtete Klasse von Graphen einzuschränken. Motivation für diesen Ansatz war die Beobachtung, daß die sich aus der Sendernetzmodellierung ergebenden Graphen keineswegs beliebig sind, sondern eine bestimmte, an der geometrischen Konfiguration des Sendernetzes orientierte, Struktur zeigen. Nun ist bekannt, daß das Graphfärbungsproblem für bestimmte eingeschränkte Klassen von Graphen durchaus approximiert werden kann, bzw. sogar in vernünftiger Rechenzeit lösbar ist. Unsere Hoffnung war daher, innerhalb der Sendernetz-Graphen solche Strukturen finden zu können, um daraus Lösungsverfahren für das Frequenzplanungsproblem abzuleiten. Hierzu waren wir auf eine intensive Zusammenarbeit mit den Nachrichtentechnikern des Südwestfunks angewiesen, um die in Frage kommenden Struktureigenschaften der Netzwerk-Graphen identifizieren zu können. Neben den eigentlichen Graphfärbungsalgorithmen mußten dann Verfahren entwickelt werden, um die vom Südwestfunk berechneten Sendernetz-Graphen im Hinblick auf die ermittelten Struktureigenschaften zu analysieren und entsprechende Graph-Modelle zu berechnen.

Ergebnisse

Im Rahmen des Projekts wurde das Frequenzplanungsproblem insbesondere im Hinblick auf die darin enthaltenen verallgemeinerten Graphfärbungsprobleme und die beteiligten Graphklassen analysiert und daraus Ansätze zur Lösung des Problems entwickelt. Derzeit werden die gefundenen Lösungsansätze in eine Softwarebibliothek umgesetzt, die auch über eine Schnittstelle zum Sendernetzplanungssystem SNP des Südwestfunks verfügen wird.

Die wichtigsten Projektergebnisse im einzelnen:

Derzeit wird eine C++-Software-Bibliothek "CAPtool” entwickelt, die sämtliche im Projekt entwickelten Verfahren auf der Grundlage einer einheitlichen Basisdatenstruktur zusammenfassen soll. Dazu wurde ein objektorientiertes Konzept entwickelt, das die Implementierung der verschiedenen Varianten von Frequenzplanungsalgorithmen erleichtern und eine spätere Erweiterung der Bibliothek um neue Netzmodelle und Verfahren ermöglichen soll. Von Interesse ist dabei vor allem die Anpassung der im Projekt entwickelten Verfahren auf digitale Gleichwellennetze (z.B. DAB, vergleiche Ausblick).

---

Ausblick

Für die kommende zweite Phase des Forschungsverbundes Medientechnik Südwest sollen die im Projekt entwickelten Modelle und Verfahren nun an die Verhältnisse in digitalen Gleichwellennetzen (DAB= Digital Audio Broadcasting, DTVB = Digital Television Broadcasting) angepaßt werden. Hier wird derzeit in Zusammenarbeit mit unseren Projektpartnern beim Südwestfunk untersucht, welche Planungsprobleme dabei von besonderem Interesse sind. Als ein wichtiges Problem wurde dabei bereits die Versorgungsplanung identifiziert. Durch die geforderte Regionalisierung der digitalen Netze und die Einbeziehung von Mehrwertediensten ergeben sich in diesem Zusammenhang über die Kanalzuweisung hinaus neue Randbedingungen für die Planung. Insbesondere müssen sogenannte "Packungsprobleme” gelöst werden, die im allgemeinen Fall NP-vollständig sind.

---

Literatur

A. Gräf, C. Lautemann, F. Wankmüller (Hrsg.). Färbung von Graphen. Musikinformatik und Medientechnik 1/91, Johannes Gutenberg-Universität Mainz, 1991.

Martin Stumpf. Endliche Markov-Ketten und ihre Anwendung auf Optimierungsprobleme. Musikinformatik und Medientechnik 3/92, Johannes Gutenberg-Universität Mainz, 1992.

A. Gräf. Permutative Graph Colorings. Musikinformatik und Medientechnik 5/92, Johannes Gutenberg-Universität Mainz, 1992.

G. Weißenfels. Das Färbbarkeitsproblem für spezielle Graphklassen. Diplomarbeit, Johannes Gutenberg-Universität Mainz, 1993.

A. Gräf. Complete Difference Sets and T-Colorings of Complete Graphs. Musikinformatik und Medientechnik 7/93, Johannes Gutenberg-Universität Mainz, 1993. Kurzversion in Proceedings 3rd Twente Workshop on Graphs and Combinatorial Optimization, S. 55-60, 1993.

M. Stumpf. An exact algorithm for the minimum span T-coloring problem on complete graphs. Musikinformatik und Medientechnik 16/94, Johannes Gutenberg-Universität Mainz, 1994.

A. Gräf, M. Stumpf, G. Weißenfels. On Coloring Unit Disk Graphs. Musikinformatik und Medientechnik 17/94, Johannes Gutenberg-Universität Mainz, 1994. Kurzversion in Proceedings 3rd Twente Workshop on Graphs and Combinatorial Optimization, S. 206-208, 1993.

A. Gräf. Coloring and Recognizing Special Graph Classes. Dissertation, Musikinformatik und Medientechnik 20/95, Johannes Gutenberg-Universität Mainz, 1995.

M. Stumpf. A Note on Coloring 2-Nested Unit Disk Graphs. Musikinformatik und Medientechnik 22/95, Johannes Gutenberg-Universität Mainz, 1995.

Ewa Malesinska, Steffen Piskorz, Gerhard Weißenfels. On the Approximability of Coloring Problems for Disk Graphs. Musikinformatik und Medientechnik 26/96, Johannes Gutenberg-Universität Mainz, 1996.

---

NP-Vollständigkeit

Unter der Bezeichnung "NP-vollständige Probleme” wird in der Informatik eine große Anzahl verschiedener Optimierungsprobleme zusammengefaßt, für die es nach gegenwärtigem Kenntnisstand keine effizienten Lösungsverfahren gibt. Ein NP-vollständiges Problem P ist dabei durch zwei Eigenschaften charakterisiert:

• P gehört zur Klasse der nichtdeterministisch polynomiell lösbaren (NP-) Probleme, d.h. zu jedem solchen Problem gibt es ein Verfahren, das die Zulässigkeit einer gegebenen Lösung des Problems in polynomieller Rechenzeit entscheiden kann. Dabei bedeutet polynomielle Rechenzeit, daß das Verfahren für eine Eingabe der Größe n (z.B.: einen Graphen mit n Knoten) höchstens n^k elementare Rechenschritte benötigt, wobei k eine von P abhängige Konstante ist.

• P ist außerdem NP-schwierig, d.h. zu jedem anderen NP-Problem P' gibt es ein Verfahren, das es gestattet, Problem P' in polynomieller Rechenzeit auf Problem P zurückzuführen.

Die NP-vollständigen Probleme sind also diejenigen Probleme, deren Lösungen "effizient” (in polynomieller Rechenzeit) überprüfbar sind, und die "mindestens genauso schwierig” (bis auf polynomielle Rechenzeit) wie jedes NP-Problem sind. Insbesondere sind alle NP-vollständigen Probleme bis auf polynomielle Rechenzeit gleich schwierig.

Zur Klasse der NP-vollständigen Probleme gehören eine große Anzahl von bekanntermaßen schwierigen Optimierungsproblemen aus der Praxis. Alle bekannten Verfahren zur optimalen Lösung solcher Probleme beruhen im Prinzip darauf, alle möglichen Lösungsalternativen "durchzuprobieren” und benötigen damit exponentielle Rechenzeit, sind also zur Lösung größerer Problemstellungen aus der Praxis ungeeignet. Man ist daher häufig darauf angewiesen, NP-vollständige Planungsprobleme mittels Heuristiken zu lösen, die zwar nicht die Optimalität der gefundenen Lösung garantieren können, dafür aber mit polynomieller Rechenzeit auskommen.

---

Das Graphfärbungsproblem

Das Graphfärbungsproblem ist eines der bekanntesten und am besten untersuchten Probleme der Graphentheorie. In der Gestalt der sogenannten Vierfarben-Vermutung ("jede Landkarte läßt sich mit vier Farben so färben, daß keine zwei aneinandergrenzende Länder die gleiche Farbe haben”, bzw., in der Sprache der Graphentheoretiker ausgedrückt, "jeder planare Graph ist 4-färbbar”) begegnet es uns bereits in einer Mitteilung von Guthrie an de Morgan um 1850, und möglicherweise war Möbius bereits 1840 mit diesem Problem vertraut. Ist auch die Vierfarben-Vermutung in den 70er Jahren dieses Jahrhunderts durch massiven Rechnereinsatz bewiesen worden, so ist doch im allgemeinen Fall bislang kein effizientes Verfahren zur optimalen Färbung beliebiger Graphen bekannt. Tatsächlich gehört dieses Problem zur Klasse der sogenannten NP-vollständigen Probleme.

Mathematisch wird das Graphfärbungsproblem wie folgt formuliert. Gegeben ist ein Graph G , bestehend aus einer Menge V von Knoten und einer Menge E von Kanten zwischen diesen Knoten. Dabei ist jede Kante durch ein entsprechendes ungeordnetes Paar vw von verschiedenen Knoten v und w des Graphen gegeben.

Eine Färbung von G ist eine Funktion f , die jedem Knoten v von G eine entsprechende "Farbe” f(v) zuordnet, so daß für jede Kante vw von G die Bedingung

gilt. Als chromatische Zahl von G bezeichnen wir die kleinste Farbenzahl in einer Färbung von G , d.h.

wobei das Minimum über alle Färbungen f von G gebildet wird. Eine Färbung f von G wird als optimal bezeichnet, wenn

Die Aufgabenstellung beim Graphfärbungsproblem ist es nun, zu einem gegebenen Graphen G eine optimale Färbung zu bestimmen.

Das Graphfärbungsproblem ist eines der klassischen NP-vollständigen Probleme. Es tritt in vielen Anwendungsproblemen auf, in denen die "Unverträglichkeit” bestimmter Problemelemente (z.B. die Gleichzeitigkeit zweier Kurse oder die gegenseitige Störung zweier UKW-Sender) modelliert werden muß. Für das Frequenzplanungsproblem sind außerdem verschiedene allgemeinere Varianten des Graphfärbungsproblems von Bedeutung.

---

Verallgemeinerte Graphfärbungsprobleme

Bei der Frequenzplanung treten neben dem klassischen Graphfärbungsproblem auch verschiedene verallgemeinerte Versionen dieses Problems auf. Die wichtigsten dieser Probleme sollen im folgenden kurz erläutert werden.

Listenfärbungsproblem: Beim Listenfärbungsproblem ist für jeden Knoten v eine Menge S(v) der zur Verfügung stehenden Farben vorgegeben. Als zusätzliche Bedingung an die Zulässigkeit einer Färbung hat man:

für alle Knoten v des Graphen. Das Listenfärbungsproblem tritt bei der Frequenzplanung in Erscheinung, wenn die Menge der zur Verfügung stehenden Frequenzen z.B. durch politische Vorgaben oder technische Voraussetzungen eingeschränkt ist.

Mengenfärbungsproblem: Hier ist jedem Knoten v des Graphen nicht nur eine einzige Farbe f(v) , sondern eine ganze Menge von Farben F(v) zuzuordnen. Die Größe der einzelnen Farbenmengen ist dabei ein Parameter der Problemstellung. Die Verträglichkeitsbedingung für zwei durch eine Kante vw verbundene Knoten lautet:

Das Mengenfärbungsproblem spielt vor allem bei der Planung von mobilen Netzen eine große Rolle.

T-Färbungsproblem: Beim T-Färbungsproblem ist zusätzlich zum Graphen eine Menge T verbotener Abstände gegeben. Die Bedingung für die Verträglichkeit der durch Zahlen angegebenen Farben zweier durch eine Kante vw verbundener Knoten lautet dann:

Im Frequenzplanungsproblem tritt dieser Fall auf, wenn zur Entkopplung zweier Sender bestimmte Kanalabstände vermieden werden müssen. Dabei ist die zu minimierende Größe nicht die Anzahl der Farben, sondern der sogenannte Span (Spannweite) der Färbung,

d.h. die Breite des verwendeten Frequenzbandes.

Mindestabstandsfärbungsproblem: Hier ist zu jeder Kante vw des Graphen ein Mindestabstand m_vw gegeben. Die zugehörige Bedingung lautet:

für alle Kanten des Graphen. Auch hier ist diejenige Färbung optimal, die minimalen Span hat.

---