Färbungen von Graphen: Registerzuteilung, Stundenpläne, Sudoku und das Borsuk-Ulam-Theorem.
In Teil 12 hatte ich kurz erwähnt, daß sich das Borsuk-Ulam-Theorem auf Graphenfärbungsprobleme und damit auf Fragen der Registerzuteilung anwenden läßt. (Bei der Registerzuteilung geht es darum, umfangreiche Daten möglichst effektiv auf mehrere Speicherzellen eines Prozessors zu verteilen. Genaueres hier.)
Zunächst: ein Graph besteht aus Ecken und Kanten. Unter einer Färbung versteht man eine Färbung der Ecken, so daß für jede Kante die beiden Ecken unterschiedliche Farben haben. Zum Beispiel zeigt das Bild einen Graphen mit 6 Ecken, 7 Kanten und eine Färbung mit 4 Farben. (Es gibt auch eine Färbung mit nur 2 Farben. Wie?)
Ein anderes einfaches Beispiel ist folgende Färbung eines Graphen mit 3 Farben, die sich offensichtlich nicht weiter verbessern läßt.
Die praktische Bedeutung von Graphfärbungsproblemen kommt daher, daß sich Register-Zuweisungs-Probleme in Prozessoren, oder Bandbreiten-Zuweisung-Probleme, als Graphenfärbungsprobleme formulieren lassen.
Das hinter diesen Anwendungen stehende Prinzip kann man an folgendem Alltags-Beispiel (Quelle: Wikipedia) veranschaulichen.
Das Aufstellen eines Stundenplans läßt sich als Graphfärbungsproblem formulieren: Die Knoten des Graphen sind dabei die zu plazierenden Veranstaltungen, und eine Kante wird zwischen zwei Veranstaltungen eingefügt, die nicht gleichzeitig stattfinden können (in der Schule wären das z.B. Stunden, die von demselben Lehrer unterrichtet werden sowie Stunden in derselben Klasse). Die möglichen Farben entsprechen den zuteilbaren Zeitfenstern. Man sucht natürlich nach einer Färbung mit möglichst wenigen Farben.
Ein ähnliches Beispiel wäre die Vergabe von Radiofrequenzen an verschiedene Funktürme, deren Signale sich teilweise überlagern. (Benachbarte Funktürme dürfen nicht identische Frequenzen nutzen, weil der Empfang sonst gegenseitig gestört wird.)
Und auf analoge Weise kann man auch das Problem der Register-Zuteilung in Prozessoren als Graphfärbungsproblem auffassen.
Auch wenn man das nicht wirklich als Anwendung bezeichnen kann, ist auch Sudoku ein spezielles Graphfärbungsproblem: man nehme einen Graph mit 81 Ecken, die den Feldern des Sudoku entsprechen. Wenn zwei Felder nach den Sudoku-Regeln nicht dieselbe Ziffer bekommen dürfen (d.h. in derselben Reihe, derselben Spalte oder demselben 3×3-Block), verbinde man sie durch eine Kante. Eine Lösung des Sudoku ist dann dasselbe wie eine Färbung dieses Graphen mit 9 Farben (die den Zahlen 1 bis 9 entsprechen): die Bedingung, daß benachbarte Ecken unterschiedliche Farben bekommen, entspricht ja gerade den Sudoku-Regeln.
Man kann also versuchen, die bekannten Graphfärbungsalgorithmen auf das Sudoku-Problem anzuwenden. (Das zusätzliche Problem beim Sudoku ist natürlich, daß für einige der Ecken die Farben bereits vorgegeben sind.) Über die mathematischen Schwierigkeiten, die mit diesem Zugang verbunden sind, berichtete letztes Jahr ein Artikel auf Spiegel Online.
Graphfärbungen und Algorithmen dafür sind natürlich ein eigenes Teilgebiet der Mathematik, über daß man eine ganze Serie schreiben könnte. Ich will hier nur über die Anwendung des Borsuk-Ulam-Theorems (Teil 12) auf Färbungsprobleme für eine sehr spezielle Klasse von Graphen schreiben.
Es geht um sogenannte Knesergraphen. Diese hängen von zwei Parametern n,k ab, werden mit KGn,k bezeichnet, und sind wie folgt definiert: Die Ecken entsprechen den k-elementigen Teilmengen von {1,2,…,n}. Zwei Ecken sind durch eine Kante verbunden, wenn die entsprechenden Teilmengen kein gemeinsames Element haben.
Zum Beispiel ist KGn,1 einfach ein Graph mit n Ecken, die alle durch Kanten verbunden sind. KG3,2 besteht aus drei isolierten Ecken, KG4,2 aus drei Paaren von Ecken mit je einer Kante. KG5,2 ist der unten abgebildete Petersengraph.
Es ist leicht, eine Färbung von KGn,k mit n-2k+2 Farben zu finden. Martin Kneser hatte 1955 vermutet, daß es keine besseren Färbungen gibt. Bewiesen wurde dies 1978 von Laszlo Lovasz unter Benutzung des Borsuk-Ulam-Theorems. (Wie das Borsuk-Ulam-Theorem dort ins Spiel kommt, kann man in einem Überblicksartikel von de Longueville oder natürlich in der dort zitierten Originalliteratur nachlesen.)
Wer selbst mit Graphfärbungen experimentieren will, kann das Programm CoLoRaTiOn von Jim Andrews und Michael Fellows verwenden.
Teil 1, Teil 2, Teil 3, Teil 4, Teil 5, Teil 6, Teil 7 , Teil 8, Teil 9 , Teil 10 ,Teil 11, Teil 12, Teil 13
Bild 1 ist von Joseph Culberson, die anderen aus Wikimedia.
Letzte Kommentare