Direkt zum Inhalt | Direkt zur Navigation

Benutzerspezifische Werkzeuge

Sektionen

Graphentheoriebasierte Verfahren

next up previous contents
Next: Lineare Programmierung / Ganzzahlige Up: Lösungsansätze Previous: Wissensbasierte Verfahren / Expertensysteme

Graphentheoriebasierte Verfahren

Wie auch die Heuristiken bewahren diese Verfahren die Invariante, daß kein Objekt zur selben Zeit an zwei verschiedenen Orten sein kann und versuchen, die Zahl der gesetzten Stunden zu erhöhen.  

Modellierungsansätze

Aus der Theorie der tex2html_wrap_inline5146 -Vollständigkeit ergibt sich, daß jedes tex2html_wrap_inline5146 -schwere Problem dazu verwendet werden kann, das Timetablingzu modellieren. Daher werden im folgenden ausschließlich Beispiele angegeben, die in tatsächlichen Lösungsversuchen angewandt wurden bzw. bei denen die Modellierung besonders einfach ist.

Knotenfärbungen:
Jeder Termin, der angesetzt wurde, wird als Knoten eines Graphen repräsentiert. Zwei Knoten werden genau dann durch eine (ungerichtete) Kante verbunden, wenn die beiden zugehörigen Termine kollidieren. Offenbar sind dann die Mengen von Terminen, die gleichzeitig stattfinden können, genau die unabhängigen Knotenmengen. Eine Knotenfärbung dieses Graphen ergibt somit eine gültige Lösung, wenn man jeder Farbklasse einem Zeitpunkt zuordnet.

Kantenfärbungen:
Hier werden die einzelnen Ressourcen als Knoten und die Termine als (Hyper-)Kanten modelliert. Zwei Termine kollidieren genau dann, wenn sie einen gemeinsamen Knoten haben. Eine Färbung der Kanten induziert somit wieder einen gültigen Stundenplan. Diese Darstellung und die des Knotenfärbens sind durch Cliquen bzw. Linegraphbildung ineinander überführbar.

Netzwerkflüsse:
Das Problem, einen Fluß in einem Netzwerkgif zu finden, liegt, wenn keine weiteren Anforderungen gestellt werden, in tex2html_wrap_inline5238 . Daher läßt es sich nur für Spezialfälle wie den folgenden anwenden: CHAHAL und DEWERRA [CdW89] beschreiben ein Timetabling-Problem, bei dem es egal ist, welcher konkrete Lehrer in einer Klasse ein Fach gibt, solange nur die Belastungszahlen von Klassen und Lehrern relativ zu den jeweiligen Fächern eingehalten wird. Hier kann die Bestimmung eines maximalen Matchings, wie sie in Satz 4.3.3 verwendet wird, als Flußproblem interpretiert und mit einer weiteren Menge von Knoten versehen werden, so daß der Graph dann tripartit wird:

tex2html_wrap5612

Hierbei repräsentiert die innere Knotenreihe die Fächer und jeder Fluß kann als eine Menge von parallel zu haltenden Stunden interpretiert werden. Die Möglichkeit einer guten Lösung - ohne zusätzliche Bedingungen - ergibt sich aus Kapitel 4.3.3. Zusatzbedingungen - wie z.B. Raumzahlen - lassen sich einbinden, indem man die Fachknoten aufspaltet und zwischen den beiden Duplikaten eine mit der Raumzahl kapazitätsbeschränkte Kante einfügt; hierbei geht die Garantie der Existenz einer Lösung natürlich verloren.

Die ersten beiden Ansätze haben den Nachteil, daß sie keine Modellierung dynamischer Ressourcen erlauben. Eine Konstruktion für einen Spezialfall im Bereich der Knotenfärbung ergibt sich z.B. [JT95] folgend: Will man bei einer k- Färbung erreichen, daß aus einer gegebenen Menge M von weniger als k Knoten ein Knoten eine andere Farbe erhält als alle anderen, kann man einen tex2html_wrap_inline5568 hinzufügen und jeden Knoten aus M mit mindestens einem Knoten davon verbinden, so daß jeder Knoten des tex2html_wrap_inline5568 davon überdeckt wird. Offenbar ist eine monochromatische Färbung von M somit nicht mehr möglich.
Es bleibt aber zu zeigen, daß stets eine Färbung gefunden werden kann. Hierzu seien (nach geeigneter Umnumerierung) tex2html_wrap_inline5576 , die Farben von M. tex2html_wrap_inline5580 bezeichne ihre Vielfachheit. Ist k=l, so genügt es , eine beliebige fixpunktfreie Permutation der Farben für die Knoten aus tex2html_wrap_inline5568 zu wählen. Ansonsten seien die Knoten des tex2html_wrap_inline5586 der Farbgröße der zugehörigen Knoten aus M nach sortiert als tex2html_wrap_inline5590 Nun gibt man tex2html_wrap_inline5592 für i<k jeweils die Farbe i+1. Da tex2html_wrap_inline5598 ist, ergibt sich somit leicht per Induktion, daß die Knoten 1 bis k-1 korrekt gefärbt werden. Da es nach Voraussetzung mehr als eine Farbe gibt, kann der zu Knoten tex2html_wrap_inline5604 adjazente Knoten aus M nicht die Farbe 1 haben, so daß tex2html_wrap_inline5604 diese erhalten kann.

Integer Multicommodity Flüsse

Zur Bearbeitung des Gesamtproblems fehlt in klassischen Netzwerkflüssen eine Art Schalter, da der benötigte Schaltfluß stets auch die dem zu steuernden Fluß zugedachten Kanten verwenden kann. Die gewünschte Erweiterung des Flußmodells stellen die sogenannten Integer Multicommodity-Flüsse   dar. Zugrunde liegt hier die Vorstellung von mehreren - in diesem Fall zwei - Flüssen, die sich dieselben Netzwerkkapazitäten teilen.gif Die folgenden zwei Abbildungen beschreiben eine einfache Reduktionsmöglichkeit.

tex2html_wrap5622

Die Ovale repräsentieren Gruppen von Ressourcenanforderungen, die je eine Unterrichtseinheit bilden: Z.B. Lehrer A + Klasse C + 1 Biologieraum. Die Knoten auf der rechten Seite repräsentieren die verfügbaren Objekte und eine Kante verbindet eine Anforderung mit allen Objekten, die diese erfüllen können. Durch die Anforderungen laufen quer die Kanten eines zweiten Flusses. Der zweite Fluß kann diese Kanten nicht verlassen, da er sonst seine Senke nicht erreichen kann.

Die dargestellten Platten werden wie folgt zusammengesetzt:

tex2html_wrap5624

Für jede Zeitstunde wird eine solche Platte eingefügt. Die Kanten des zweiten Flusses werden gruppenweise verbunden und der Zufluß zu jeder Gruppe erhält als Kapazität die Zahl der Zeitstunden, die diese Gruppe nicht benötigt. Die Summe dieser Werte über alle Gruppen wird in der Senke angefordert. Die Verteilerknoten des anderen Flusses werden jeweils mit Quelle und Senke verbunden, wobei an dieser Senke die Gesamtzahl aller je benötigten Objekte angefordert wird.
Wenn es einen gültigen Stundenplan gibt, gibt es offensichtlich einen Multi-Commodity-Fluß, der das gegebene Netzwerk befriedigt. Ist umgekehrt ein Fluß gegeben, so müssen alle nicht vom zweiten Fluß blockierten Anforderungen erfüllt werden. Dies ist aber nur möglich, wenn die entsprechende Anzahl von Stunden der jeweiligen Gruppen mit Ressourcen versehen werden kann. gif

Hierbei bezeichne T die Zahl der Timeslices und tex2html_wrap_inline5618 die Zahl der Stunden, die Gruppe i (Lehrer, Klassen, Räume, s. Kapitel 5.3.1) benötigt.

Der Algorithmus nach König

Dieser und der nächste Abschnitt beschreiben auf Kantenfärbungen beruhende Ansätze zur Lösung von Spezialfällen des STP.   Der älteste und wohl bekannteste Algorithmus beruht auf der Tatsache, daß für bipartite Graphen Maximalgrad ( tex2html_wrap_inline5626 ) und Kantenfärbbarkeitszahl ( tex2html_wrap_inline5628 ) übereinstimmen. Diese bereits 1916 von K¨ONIG durch Ergänzung zu einem regulären Graphen bewiesene Tatsache soll hier nochmals auf anderem Wege hergeleitet werden:

Einige Grundlagen aus der Matchingtheorie

  Als Matching in einem Graphen bezeichnet man eine unabhängige Kantenmenge, d.h. eine Menge von Kanten, die keinen Knoten gemeinsam haben.
Wesentliches Element bei der Erzeugung von Matchings sind alternierende Pfade, d.h. Pfade in Graphen, bei denen abwechselnd zum Matching gehörige und nicht zum Matching gehörige Kanten auftreten. Solange ein alternierender Pfad existiert, der mit je einem nicht vom Matching überdeckten Knoten beginnt und endet, kann das Matching weiter vergrößert werden, indem man auf diesem Pfad jeweils Matchingkanten durch Nicht-Matchingkanten ersetzt und umgekehrt. Daß dieses Verfahren hinreichend ist, um maximale Matchings zu erstellen, ist Aussage des Satzes von BERGE.

Satz1029

Beweis:
Betrachtet man die symmetrische Differenz zwischen dem gegebenen und einem maximalen Matching, so hat jeder Knoten einen Grad kleiner-gleich zwei. Damit besteht der Differenzgraph aus alternierenden Wegen und Kreisen. Da in jedem Kreis genausoviele Kanten des gegebenen, wie des maximalen Matchings auftreten, muß eine überzählige Kante des maximalen Matchings in einem Weg auftreten, der somit ein augmentierender sein muß.

Dieser Satz besagt insbesondere, daß man mit einem beliebigen Matching beginnen und dieses dann durch Finden alternierender Pfade zu einem maximalen Matching vergrößern kann. Dies liefert das sehr nützliche

  Kor1038

Beweis:
Man konstruiere ein maximales Matching M' aus M durch beständiges Alternieren über augmentierende Pfade. Bei jeder Augmentierung bleiben alle vom ursprünglichen Matching übberdeckten Knoten überdeckt, da an jedem Knoten auch stets eine Nicht-Matching-Kante innerhalb des Pfades anliegt.

Zum Abschluß dieses Kapitels sei noch einer der wichtigsten Sätze über bipartite Graphen, d.h. Graphen, die sich in zwei innerhalb nicht verbundene Komponenten zerlegen lassen, erwähnt. Im Bereich der automatische Stundenplanerstellung und somit auch im Rest dieser Arbeit werden fast ausschließlich Graphen dieses Typs verwendet.

  Satz1045

Der Beweis findet sich in nahezu jedem Buch über Graphentheorie und wird daher und auch wegen seines Umfangs und der Größe des benötigten Begriffsapparates hier nicht wiedergegeben.

Anwendung im Timetabling

Zunächst sollen hier einige unmittelbare Korollare aus Satz 4.2 gezogen werden. Das folgende, eigentlich allgemeinere Ergebnis fällt zumeist als Nebenprodukt des Beweises des Satzes von Hall ab, kann aber auch aus diesem recht einfach bewiesen werden.

Kor1052

Beweis:
Die Notwendigkeit ist wie im Satz von HALL trivial. Man verbinde nun alle Knoten in tex2html_wrap_inline5660 mit allen Knoten aus B. Der so entstandene Graph G' erfüllt die Voraussetzungen des Satzes von Hall: Enthält eine Teilmenge einen Knoten aus tex2html_wrap_inline5660 so gilt die Behauptung trivial, ansonsten folgt sie aus der Voraussetzung dieses Korollars. G' besitzt somit ein Matching, das V(G') und somit auch A' überdeckt. Betrachtet man nun die Kanten, die in A' enden, so bilden sie offenbar auch in G ein Matching.

Mit Hilfe des Schubfachprinzips erhält man:

   Kor1057

Mit Hilfe dieser Aussage kommt man schließlich zum folgenden Korollar:

Kor1062

Beweis [Huc]:
  Offenbar gibt es mit Korollar 4.3 auch ein Matching, daß alle Knoten maximalen Grades in B überdeckt ( tex2html_wrap_inline5686 ). Die Frage ist ausgehend von tex2html_wrap_inline5688 , ob es eines gibt, daß die verbleibenden Knoten (eventuell ehemals) maximalen Grades in B überdeckt. Hierzu sei zunächst die Menge der Knoten maximalen Grades in A mit A' bezeichnet (analog B'). Es seien aus tex2html_wrap_inline5688 diejenigen Kanten tex2html_wrap_inline5700 gewählt, die von A' nach B' führen. Diese bilden offenbar ein Matching in dem von tex2html_wrap_inline5706 induzierten Teilgraphen. Gemäß Korollar 4.1 und dem obigen Korollar kann man dieses zu einem Matching tex2html_wrap_inline5708 erweitern, daß ganz B' und tex2html_wrap_inline5712 überdeckt. Damit ist tex2html_wrap_inline5714 . Für jeden Knoten tex2html_wrap_inline5716 gibt es aber aus tex2html_wrap_inline5688 eine Kante nach tex2html_wrap_inline5720 . Nimmt man diese dann zu tex2html_wrap_inline5708 hinzu, wenn a nicht bereits von tex2html_wrap_inline5708 überdeckt wurde, erhält man ein Matching der gewünschten Art.

Somit erhält man unmittelbar den

  Satz1072

Beweis:
Man wähle als Farbklasse stets die Kanten eines Matchings das alle Knoten maximalen Grades überdeckt. Offenbar sinkt jedesmal der Maximalgrad im Graphen der noch nicht gefärbten Kanten um 1. Damit sind nach tex2html_wrap_inline5626 Schritten alle Kanten gefärbt. Als maximales Ergebnis dieses Sachverhalts für einen Algorithmus zur automatischen Stundenplanerstellung erhält man somit das folgende Lemma:

Lem1076

Die zu diesen Lehrern bzw. Klassen assoziierten Knoten werden im folgenden als kritisch bezeichnet. Dieser Satz ermöglicht es, den Algorithmus von König als Teilroutine anderer Verfahren zu verwenden. Siehe hierzu Kapitel 6.

Der Satz von Galvin

  Lange Zeit gab es gegenüber den Verfahren von K¨ONIG keinerlei Verbesserungen [dW85]. Mit dem Beweis der Vizingschen Listenfärbungsvermutung für bipartite Graphen durch Galvin ergibt sich für allgemeine Vorgaben- und Unverfügbarkeitszahlen ein wohl für das School-Timetabling\ endgültiges Ergebnis, sofern man keine spezifischen Forderungen an die Unverfügbarkeiten stellt.gif

Satz1084

Beweis:
[Die96] Der Beweis verläuft in zwei Schritten. Zunächst wird gezeigt, daß jeder gerichtete Graph, dessen sämtliche induzierten Teilgraphen einen sog. Kern haben, und der für alle tex2html_wrap_inline5740 tex2html_wrap_inline5742 erfüllt, mit den tex2html_wrap_inline5744 listenfärbbar ist. Dann wird bewiesen, daß jeder Linegraph eines bipartiten Graphen so orientiert werden kann, daß diese Bedingungen für Listen der Größe tex2html_wrap_inline5280 gelten. Da in bipartiten Graphen tex2html_wrap_inline5438 gilt, folgt somit die tex2html_wrap_inline5626 -Kanten-Listenfärbbarkeit bipartiter Graphen und daraus wegen tex2html_wrap_inline5752 die Aussage des Satzes.

Def1094

Das Wesen der Methode besteht nun darin, die Bedingung tex2html_wrap_inline5742 zu erhalten, indem man jedesmal, wenn tex2html_wrap_inline5766 verkleinert wird, sicherstellt, daß auch tex2html_wrap_inline5768 reduziert wird.

Lem1097

Beweis:
Der Beweis erfolgt durch Induktion. Der leere Graph kann offenbar mit 0 Farben gefärbt werden. Sei nun H=(V,E) mit obigen Eigenschaften gegeben. Sei eine Farbe tex2html_wrap_inline5780 beliebig gewählt und sei D derjenige Teilgraph von H, der von den Knoten v mit tex2html_wrap_inline5788 erzeugt wird. Dann besitzt D nach Voraussetzung einen Kern U. Man färbe nun alle Knoten in U mit tex2html_wrap_inline5780 und entferne tex2html_wrap_inline5780 aus allen Listen in tex2html_wrap_inline5800 . Da alle Knoten, deren Liste verkleinert wird, mit U verbunden waren, sinkt deren Ausgangsgrad ebenfalls um eins und tex2html_wrap_inline5804 erfüllt die oben gestellten Bedingungen. Nach Induktion ist tex2html_wrap_inline5804 mit den Farbmengen tex2html_wrap_inline5808 färbbar, und somit gilt die Behauptung.

  Lem1101

Beweis:

Im folgenden wird weiterhin vom Graphen G die Rede sein. Da das eigentliche Objekt der Betrachtungen der zugehörige Linegraph ist, werden nun Kanten zwischen Kanten auftreten.

Es sei eine beliebige (herkömmliche) Färbung von G mit den Farben tex2html_wrap_inline5820 gegeben. Treffen sich zwei Kanten in X, so sei die Kante zwischen ihnen von der mit der größeren Farbe zu der mit der kleineren Farbe gerichtet. Treffen sie sich in Y, sei die Orientierung umgekehrt.

Zunächst ist zu zeigen, daß tex2html_wrap_inline5826 . Sei dazu tex2html_wrap_inline5828 fest gewählt. Alle Nachbarn von tex2html_wrap_inline5828 , die Nachfolger von tex2html_wrap_inline5828 bezüglich der Kanten des Linegraphen sind, treffen tex2html_wrap_inline5828 in einem Punkt in X bzw. in einem Punkt von Y. Die Kanten in X haben alle kleinere und paarweise verschiedene Farben als tex2html_wrap_inline5828 ; die Kanten in Y haben größere und paarweise verschiedene Werte. Damit kann es maximal tex2html_wrap_inline5846 dieser Kanten geben. Zu tex2html_wrap_inline5828 parallele Kanten sind entweder in X oder in Y Nachfolger von tex2html_wrap_inline5828 . Damit gefährdet ihre Existenz die Gültigkeit der Aussage nicht.

Als zweites ist zu zeigen, daß jeder Teilgraph einen Kern besitzt. Die Aussage gilt offenbar für leere Teilgraphen. Somit kann die Aussage wie folgt durch Induktion bewiesen werden: Es sei gezeigt, daß die Aussage für Graphen mit n Kanten gelte. Sei nun ein beliebiger Teilgraph D mit n+1 Kanten gewählt. Für tex2html_wrap_inline5862 sei tex2html_wrap_inline5864 die Menge der mit x inzidenten Kanten und tex2html_wrap_inline5868 diejenige Kante aus tex2html_wrap_inline5864 mit minimaler Farbe. Sei tex2html_wrap_inline5872 . Offenbar hat jede Kante in D einen Nachfolger in U, da jede Kante einen Knoten aus X trifft. Dies gilt ebenfalls für parallele Kanten. Insbesondere wird von zwei parallelen Kanten immer nur eine in U sein. Ist U also unabhängig, so ist U ein Kern. Es sei also angenommen, daß U nicht unabhängig ist, sich also zwei Kanten e,e' mit o.B.d.A. c(e')>c(e) in Y treffen. Man entfernt nun e und erhält einen Teilgraph D' mit n Kanten, der nach Voraussetzung einen Kern U' besitzt. Ist e' in U', so ist wegen der Existenz der Kante (e,e') U' auch ein Kern von D.

Ansonsten gibt es eine Kante tex2html_wrap_inline5912 , die von e' aus erreicht wird. Träfen sich e'' und e' in X, so wäre c(e'')<c(e'), was der ursprünglichen Wahl von e' widerspricht. Somit treffen sie sich in Y, was c(e'')>c(e') impliziert, woraus wegen c(e')>c(e) c(e'')>c(e) folgt, was wiederum die Existenz der Kante (e,e'') erzwingt. Somit ist U' ein Kern von D.

Wiederum ergibt sich kein Konflikt bei mehrfachen Kanten.

Kor1116

Dies ergibt sich unmittelbar aus den Anmerkungen.

Kor1118

Dies folgt aus dem vorigen Korollar und Satz 4.3.3.

Lem1122

Beweis:

Jeder Kante e sei tex2html_wrap_inline5954 als Farbliste zugewiesen. Diese Liste ist n.V. größer als tex2html_wrap_inline5286 . Somit existiert nach obigem Korollar eine gültige Listenfärbung.

Damit kann also im klassischen STP jeder Kante eine Menge von verbotenen Timeslots zugeordnet werden, die der Größe nach durch die Differenz der Zahl der möglichen Stunden und der maximalen Stundenzahl einer Klasse (bzw.eines Lehrers) beschränkt ist. Bei normalerweise 39 verfügbaren Schulstunden und 33 Klassen-Wochenstunden entspräche dies also 6 Stunden. [Tuz97] erwähnt, daß sich dieses Ergebnis noch soweit verschärfen läßt, daß jede Liste nur soviele Farben enthalten muß, wie der größere Maximalgrad der inzidenten Knoten. Dies bringt im Timetablingaber keinen Vorteil, da nahezu alle Klassen stets zu fast allen Zeitstunden Unterricht haben, der obige Wert sich also nie sonderlich vom Maximalgrad des Graphen unterscheidet.

Der Beweis des Satzes von Galvin ist so konstruktiv, daß sich ein Algorithmus unmittelbar ableiten läßt (vgl. [Sli96]):

Alg1137

  1. Färbe den Graphen mit tex2html_wrap_inline5286 Farben z.B. mit dem Algorithmus aus Abschnitt 4.3.3.
  2. Richte die Kanten des Linegraphen wie im Beweis beschrieben.
  3. Für jede Farbe tex2html_wrap_inline5966 :
    1. Sei D der von den Kanten e mit tex2html_wrap_inline5972 erzeugte Teilgraph des Linegraphen.
    2. Setze D'=D.
    3. Wähle U aus D' wie oben beschrieben.
    4. Solange U nicht unabhängig ist,
      • wähle zwei adjazente Kanten in U und entferne aus D' diejenige mit der kleineren Farbe,
      • bestimme U erneut aus D'.
    5. Färbe die Kanten aus U mit tex2html_wrap_inline5780 , entferne sie aus D und entferne tex2html_wrap_inline5780 aus allen Farblisten.
Die Korrektheit des Algorithmus ergibt sich unmittelbar aus den vorangehenden Sätzen und Korollaren.

Lem1146

Beweis:

Sei o.B.d.A |X|=|Y|=n und m die Zahl der Kanten. Die Listen seien durch eine Farben-Kanten Matrix repräsentiert. Der Algorithmus nach K¨ONIG bestimmt k ungewichtete Matchings in jeweils bipartiten Graphen, was in tex2html_wrap_inline6006 [Blu98]gif zu bewerkstelligen ist. Nach jeder Bestimmung eines Matchings können alle Kanten im Linegraphen, die Kanten des letzten Matchings (die die bisher größte Farbe erhalten) mit Kanten kleinerer Farbe verbinden (und umgekehrt), sofort erzeugt werden. Da jede Kante maximal mit tex2html_wrap_inline6010 Kanten verbunden ist, läßt sich der Aufwand dafür mit diesem Wert abschätzen. Da für das jeweils nächste Matching die jeweils nächstgrößte Farbe gewählt wird, können die zu einem Knoten gehörigen Kanten und die Farben-Kanten-Matrix gleichzeitig der Farbgröße nach sortiert werden. Somit erhält man für die Schritte 1 und 2, die hier gleichzeitig behandelt werden, eine Laufzeit von tex2html_wrap_inline6012 , wobei tex2html_wrap_inline6014 gilt.

Die nun folgende Schleife wird k mal ausgeführt. Der Teilgraph kann über die Matrix in tex2html_wrap_inline6018 bestimmt werden und aufgrund der Sortierung kann gleichzeitig U daraus erzeugt werden, indem bei jedem vorangegangenen Entfernen nicht zum Teilgraphen gehörender Knoten aus Y ein Zeiger, der stets auf die Kante mit minimaler Farbe zeigt, auf das nächstgrößere, nicht gelöschte gesetzt wird. Dies setzt voraus, daß die Kanten-Farben-Matrix entsprechend ihrer Sortierung abgearbeitet wird. Das abschließende Auslesen von U geht in tex2html_wrap_inline6026 .

Der Test auf Unabhängigkeit benötigt tex2html_wrap_inline6026 Schritte, da sich die entsprechenden Kanten nur in Y schneiden können und es somit ausreicht, die bereits überdeckten Knoten in Y zu markieren und ein nicht unabhängiges Paar daran zu erkennen, daß einer nochmals markiert werden soll. Das Entfernen einer Kante und das Neuberechnen von U sind wiederum aufgrund der Sortierung in tex2html_wrap_inline6036 möglich, da beim Entfernen einer Kante nur jeweils die Kante mit der nächstgrößeren Farbe am selben Knoten aus X diese ersetzt. Es müssen höchstens m Kanten entfernt werden, um Unabhängigkeit zu erzielen. Damit ergibt sich eine Gesamtlaufzeit von

displaymath6042

Im Timetabling-Kontext ist zumeist tex2html_wrap_inline6044 , da Lehrer und Klassen eine beschränkte Stundenzahl haben, und der Algorithmus hätte hier somit eine Laufzeit von tex2html_wrap_inline6046 , was der des Algorithmus nach K¨ONIG für diese Fälle entspricht.

Der Algorithmus läßt drei Freiheitsgrade für weitere Verbesserungen. Zum einen könnte überprüft werden, ob es möglich ist, jeweils andere Kerne zu wählen oder die Reihenfolge der Farbwahl zu variieren, zum anderen ist es möglich, die Ausgangsfärbung analog zu Abschnitt 6.6 zu modifizieren. Hier tritt allerdings das Problem auf, daß obiger Algorithmus bereits gültige Ausgangsfärbungen nicht erhält, wie das folgende Beispiel zeigt. Dabei seien für alle Punkte beide Farben zulässig; die dicken Kanten tragen Farbe 2:

tex2html_wrap6184

Die oben dargestellte Färbung ist offensichtlich gültig. Der Algorithmus würde nun zunächst alle Kanten in U aufnehmen, dann aber die obere Kante aus U entfernen, da sie die kleinere Farbe an y hat. Damit würden zwei Kanten, die in der gültigen Ausgangsfärbung verschiedene Farben hatten, nun die gleiche Farbe erhalten. Dies ist auch nicht weiter verwunderlich, da die Werte der Ausgangsfärbung durch eine andere Wahl der Reihenfolge im zweiten Schritt des Algorithmus teilweise außer Kraft gesetzt werden können.

Dennoch läßt sich durch Modifikation dieser Färbung etwas erreichen: Im Bereich der automatische Stundenplanerstellung ist es häufig so, daß nur einige Objekte von Bedingungen betroffen sind. Daher ergibt sich in geringfügiger Abweichung von der Bestimmung der Listenfärbbarkeitszahl die Frage, wie klein man irgendeine bestimmte Liste wählen kann. Hier nutzt der Satz von GALVIN die Kraft seiner beiden Lemmata nicht voll aus, da tex2html_wrap_inline6056 unmittelbar klar ist, und sich die Frage nach unterschiedlich großen Listen beim reinen Beweis der Viezingschen Vermutung nicht stellte. Durch striktere Interpretation kommt man somit zu dem:

Satz1174

Die Frage ist also, unter welchen Umständen man gezielt den Ausgangsgrad eines Knotens des Linegraphen H reduzieren kann. Dies ist offensichtlich nicht möglich, wenn beide Knoten, zu denen die entsprechende Kante inzident ist, den Grad tex2html_wrap_inline5286 aufweisen. Nimmt man aber an, daß einer (o.B.d.A der in Y) geringeren Grad hat, so kann man durch geeignete Wahl der Farbe dieser Kante e in F erreichen, daß der Grad in H entsprechend sinkt, z.B. indem man e in F die kleinstmögliche Farbe gibt. Damit hat e um eins geringeren Ausgangsgrad in H, als der zugehörige Knoten in Y Nachbarn, da alle in X e treffenden Kanten somit Vorgänger von e in H sind. Gibt man dann der nächsten Kante die zweitkleinste Farbe, so ist in X ein Nachfolger möglich, die Zahl derer in Y reduziert sich aber um 1. Insgesamt erhält man

  Lem1180

Beweis:
Hat die Kante e mit der l. größten Farbe an tex2html_wrap_inline6122 die Farbe p, so ist tex2html_wrap_inline6126 , da die übrigen l-1 Kanten Farben aus dem Intervall (p,j] erhalten müssen. Andererseits können nur noch diese l-1 der Kanten, die ebenfalls an diesem Knoten in Y anliegen, Nachfolger von e in Y sein. In X kann es maximal p-1 Nachfolger geben, da es nur entsprechend viele kleinere Farben gibt. Somit hat e maximal j-(l-1)-1+(l-1)=j-1 Nachfolger. Somit ist tex2html_wrap_inline6148

Man könnte nun also versuchen, die Tatsache, daß nur diese j Farben auftreten damit zu erzwingen, daß man den entsprechenden Kanten in G bei dieser Vorfärbung Listen der Größe tex2html_wrap_inline6154 zuordnet, die nur die ersten tex2html_wrap_inline6154 Farben enthalten. Was zunächst wie ein reiner Zirkelschluß aussieht, liefert dann aber letztlich doch den

Satz1192

Beweis:
tex2html_wrap_inline6168 ist trivial, da der Spezialfall auch zu allen Fällen gehört.
tex2html_wrap_inline6170 ergibt sich, indem man Lemma 4.7 auf jeden Knoten in Y anwendet.

Das Ganze gilt symmetrisch auch für die andere Komponente, wobei hier die j größten Farben verwendet werden müßten. Dieser Satz bestätigt somit die intuitiv klare Tatsache, daß der schlechtestmögliche Fall der ist, wenn alle Lehrer (Klassen) gleichzeitig abwesend sind.

Kor1202

Beweis
Offenbar stellt eine Färbung, in der nur die kleinsten tex2html_wrap_inline6178 Farben in jeder Liste tex2html_wrap_inline6180 auftreten, einen geeigneten (polynomiell überprüfbaren) Beweiskandidaten dar.

Bem1208

equitable colorings

  Häufig wird verlangt, daß sowohl Lehrer als auch Klassen an jedem Tag gleichstark beansprucht werden. Weisen alle Tage gleichviele Stunden auf, so kann dies mit Hilfe von equitable Colorings\([dW96]) erreicht werden. Eine Kantenfärbung wird als equitable (balanciert) bezeichnet, wenn für jeden Knoten die Zahl der inzidenten Kanten jeder Farbe ungefähr gleich ist. Genauer: Ist tex2html_wrap_inline6187 die Häufigkeit des Auftretens von Farbe f an Knoten i, so gilt für alle Knoten i und für alle Paare von Farben tex2html_wrap_inline6195 : tex2html_wrap_inline6197 .
Eine solche Färbung mit k Farben kann gefunden werden, indem jeder Knoten v in tex2html_wrap_inline6203 Hilfsknoten vom Grad k, mit möglicherweise einer Ausnahme, aufgespalten wird und auf dem so gebildeten Graphen eine normale Kantenfärbung vorgenommen wird. Identifiziert man danach alle Hilfsknoten wieder mit dem Original, so erhält man eine Färbung des gewünschten Typs, da mindestens tex2html_wrap_inline6207 mal und höchstens tex2html_wrap_inline6209 mal die gleiche Farbe an einem Knoten vorliegt.

Zusätzlich kann erreicht werden, daß die einzelnen Lehrer-Klassen-Kombinationen gleichmäßiger in der Woche verteilt liegen (vgl. [dWM95]). Ist tex2html_wrap_inline6211 kleiner gleich der Zahl der Zeitstunden an einem Tag l, so kann das equitable Scheduling zu einem normalen Stundenplan erweitert werden, indem der Algorithmus nach K¨ONIG auf die jeweils von den Kanten einer Farbe induzierten Teilgraphen angewandt wird, da deren Maximalgrad dann kleiner als l ist.


next up previous contents
Next: Lineare Programmierung / Ganzzahlige Up: Lösungsansätze Previous: Wissensbasierte Verfahren / Expertensysteme

(c) Martin Loehnertz 1999