Prüfungsplanung mit Methoden der Graphenfärbung

 

 

 

Inhalt

 

 

Beschreibung aus der Sicht des Benutzers

 

        Anwendungsbereich

 

        Prüfungsplanung mit Konfliktgraphentechnik

 

Einfacher sequenzieller Algorithmus

 

Der Algorithmus von Welsh und Powell

 

        Der Input des Programms: Prüfungsmeldungen oder Konfliktmatrix

 

        Der Output: Konfliktmatrix und Prüfungspläne

 

        Die Benutzerführung

 

        Zum Hintergrund der Konfliktgraphentechnik

 

Realisierung

 

        Architektur

 

        Die Klasse ConflictMatrix

 

        Die Klasse Graphenfaerbung

 

 

 

 

 

 

Beschreibung aus der Sicht des Benutzers

 

 

Wir betrachten in diesem ersten Teil nicht nur den Anwendungsbereich und die Benutzeroberfläche, sondern auch die im Programm angewandten Techniken der Konfliktgraphen bzw. der Graphen­färbung.

 

 

 

 

Anwendungsbereich

 

 

Das Programm ist auf folgende Situation zugeschnitten: Gegeben sind

 

 

•  eine Menge von Tests (Prüfungen), die zu schreiben sind.
• eine Menge von Terminen, die für Tests zur Verfügung stehen.

 

 

Das Ergebnis der Planung besteht aus einer Zuordnung der Tests zu Terminen. Dabei sind folgende Prämissen zu beachten:

 

 

• Es gibt Teilnehmer, die an mehreren Prüfungen teilnehmen wollen.
• Kein Teilnehmer soll auf eine Prüfung verzichten müssen.
• Es besteht keine Raumknappheit.
• Die Gesamtheit der Tests soll möglichst schnell abgewickelt werden.

 

 

Die Methoden, welche bei dieser Planung zur Anwendung kommen, beruhen auf Konfliktgraphen. Diese Methoden werden im nächsten Absatz beschrieben.

 

 

 

 

 

 

Prüfungsplanung mit Konfliktgraphentechnik

 

 

Das Programm erstellt zwei alternative Prüfungspläne. Der erste basiert auf dem einfachen sequen­ziellen Konfliktgraphenalgorithmus, der zweite auf dem Algorithmus von Welsh und Powell, der in manchen Fällen ein besseres Ergebnis hervorbringt.

 

 

Beide Algorithmen beruhen auf einem Konfliktgraph der Prüfungen. In diesem Konfliktgraph ist jeder Test durch einen Knoten repräsentiert. Prüfungen, die mindestens einen gemeinsamen Teilnehmer haben, sind durch eine Kante verbunden. Eine Kante zwischen zwei Tests bedeutet also, dass die verbundenen Tests in Konflikt zueinander stehen, weil sie gemeinsame Teilnehmer besitzen und deshalb nicht an demselben Termin abgehalten werden können.

 

 

Das Prinzip der Lösung ist einfach: Man sucht im Graph eine Menge unverbundener Tests, entfernt diese Menge aus dem Graph und weist sie einem Termin zu. Dies wiederholt man so lange, bis der Graph keine Knoten mehr enthält.

 

 

Wenn wir allerdings den Prüfungszeitraum nicht allzu sehr in die Länge ziehen wollen, müssen wir darauf achten, dass die Menge von Tests, die wir jeweils einem Termin zuweisen, nicht unnötig klein ist. Um diesen Gedanken präzisieren zu können, führen wir zwei Begriffe ein:

 

• Eine unabhängige Knotenmenge ist eine Menge von Knoten, zwischen denen es keine Verbindungen gibt.
• Eine maximale unabhängige Knotenmenge (MUK) ist eine unabhängige Knotenmenge, der man keinen zusätzlichen Knoten aus dem Graphen hinzufügen könnte, ohne dass dadurch auch Verbindungen hinzu kämen.

 

 

Ausgerüstet mit diesen Begriffen, können wir nun die beiden Algorithmen präzisieren.

 

 

 

 

 

 

Einfacher sequenzieller Algorithmus

 

Gegeben sind

 

• ein Konfliktgraph G, dessen Knoten Tests repräsentieren,
• eine Liste von Terminen

 

Vorgehen:

 

1.  Finde eine maximale unabhängige Knotenmenge M in G
2. Weise M dem nächsten freien Termin zu und entferne M aus G
3. Falls noch Knoten in G sind, beginne wieder bei Schritt 1, ansonsten ist die Durchführung beendet.

 

So formuliert, ist der Algorithmus übrigens nicht determiniert. Es sind also verschiedene Lösungen möglich. Dies wäre nicht weiter schlimm, wenn diese Lösungen alle dieselbe Anzahl von Terminen aufwiesen. Leider ist dies nicht so.

 

 

Programmiert man den Algorithmus, so ist das Vorgehen notwendigerweise schematisch. Beispiels­weise könnte man die Tests durchnummerieren und bei der Suche nach einer weiteren MUK jeweils beim niedrigsten noch im Graphen befindlichen Knoten beginnen. Man wird in diesem Fall immer dieselbe Lösung bekommen. Ob diese Lösung aber die bestmögliche ist, also die mit den wenigsten Terminen, weiß man nicht.

 

 

Will man sicher gehen, den kürzesten Prüfungsplan zu bekommen, dann kann man den Algorithmus von Welsh und Powell benutzen. Dieser führt stets zur Lösung mit den wenigsten Terminen.

 

 

 

 

 

 

Der Algorithmus von Welsh und Powell

 

 

Wir führen zunächst einen Begriff aus der Graphentheorie ein, der in diesem Algorithmus eine Rolle spielt:

 

Der Grad (englisch: degree) eines Knotens ist die Anzahl der Verbindungen (Kanten), an denen dieser Knoten beteiligt ist.

 

 

Der Algorithmus besteht aus folgenden Schritten:

 

1. Bestimme für jeden Knoten in G seinen Grad
2. Liste die Knoten nach fallenden Graden auf. Haben zwei Knoten denselben Grad, kommt es auf ihre Reihenfolge nicht an.
3. Finde eine maximale unabhängige Knotenmenge M, indem du der Liste folgst. Beginne hierzu beim obersten Knoten der Liste und nimm ihn in M auf. Suche dann, weiter in der Liste nach unten gehend, nach Knoten, welche mit den bereits in M befindlichen nicht verbunden sind. Nimm jeden dieser Knoten in M auf.
4. Weise M dem nächsten freien Termin zu und lösche die Knoten von M aus der Liste
5. Falls noch Knoten in der Liste sind, mache weiter bei Schritt 3, ansonsten ist die Durchführung beendet.

 

 

 

 

 

 

Der Input des Programms: Prüfungsmeldungen oder Konfliktmatrix

 

 

Je nach Wunsch des Benutzers ermittelt das Programm die beiden Prüfungspläne auf der Basis einer tabellarischen Zusammenstellung der Prüfungsanmeldungen (kurz: Prüfungsanmeldungen) oder aus­gehend von einer Konfliktmatrix, welche den oben beschriebenen Konfliktgraphen repräsentiert. Dieser Input (Prüfungsanmeldungen oder Konfliktmatrix) kann sich auf einem beliebigen Arbeitsblatt der Arbeitsmappe befinden. Dieses Arbeitsblatt darf allerdings nicht „Prüfungsplan“ heißen, weil dieser Name für die Ausgabe des zu erstellenden Plans reserviert ist.

 

 

Die folgenden beiden Bilder zeigen den alternativen Input. Das erste Bild enthält die Prüfungs­mel­dungen von 30 Studenten (S) für 10 Prüfungen (P). Sowohl die Studenten als auch die Prüfungen sind mit 1 beginnend durchnummeriert (blaue Bereiche). Nimmt ein Student an einer bestimmten Prüfung teil, so ist im Schnittpunkt seiner Zeile und der Spalte der Prüfung eine 1 eingetragen, nimmt er nicht teil, so steht dort eine 0.

 

 

 

Das zweite Bild zeigt die Konfliktmatrix, die diesen Prüfungsmeldungen entspricht. Die Prüfungen sind sowohl in den Zeilen als auch in den Spalten angetragen. Gibt es einen Konflikt zwischen zwei Prüfungen, so steht an deren Schnittpunkt eine 1, sonst eine 0. Übrigens ist die Matrix sym­metrisch. Gibt es einen Konflikt zwischen den Prüfungen i und j, so gibt es natürlich auch einen zwischen j und i.

 

 

Beachten Sie, dass die blau gefärbten Bereiche der Beschriftungen nicht zur Eingabe gehören. Das Programm benötigt sie nicht. Es geht stattdessen davon aus, dass sowohl die Prüfungen als auch die Prüfungsteilnehmer mit 1 beginnend durchnummeriert werden und in den Tabellen bereits in der richtigen Reihenfolge aufgeführt sind.

 

 

 

 

Der Output: Konfliktmatrix und Prüfungspläne

 

Die Ausgabe des Planungsergebnisses erfolgt auf einem Arbeitsblatt namens Prüfungsplan. Existiert dieses Arbeitsblatt noch nicht, so wird es vom Programm angelegt.

 

Die Ausgabe besteht aus drei Tabellen. Die oberste ist die Konfliktmatrix. Erfolgte die Planung auf der Basis der Konfliktmatrix, so ist dies nur eine Kopie der Eingabe. Falls auf der Grundlage der Prüfungs­anmeldungen geplant wurde, so stellt die Konfliktmatrix ein wichtiges Zwischenergebnis dar, das für den Benutzer zur Interpretation und Überprüfung des Ergebnisses von Bedeutung ist.

 

Unter der Konfliktmatrix befinden sich die beiden Tabellen mit den Prüfungsplänen, oben die nach dem einfachen sequenziellen Algorithmus, unten die nach dem Welsh-Powell-Algorithmus. Diese Tabellen sind nur zweizeilig. Die obere Zeile enthält die Nummern der Prüfungen, die untere Zeile die Nummer des Prüfungstermins, welchem die Prüfung zugeordnet ist.

 

Beachten Sie, dass in dem abgebildeten Beispiel der einfache Algorithmus vier Termine benötigte, während der Welsh-Powell-Algorithmus mit drei Terminen auskam.

 

 

 

 

Die Benutzerführung

 

Man startet das Programm durch Anklicken einer Schaltfläche auf dem Arbeitsblatt Start. Es öffnet sich dann ein recht einfach aufgebautes Formular (s. Bild unten).

 

Auf der linken Seite des Formulars kann zunächst die Art der Eingabe (Prüfungsanmeldungen oder Konfliktmatrix) ausgewählt werden. Die Option Prüfungsanmeldungen ist voreingestellt.

 

Auf der rechten Seite ist dann die Adresse des Bereichs einzugeben, in dem sich die Eingabedaten befinden. Diese Eingabe kann durch Selektieren mit der Maus geschehen. Beachten Sie, dass jeweils nur der Zahlenbereich der Tabelle selektiert werden soll, nicht die Beschriftungen.

 

Die Berechnung des Prüfungsplans wird dann durch Klicken auf die Schaltfläche ausgelöst. Die Ergeb­nisse (s. oben) werden auf das Arbeitsblatt Prüfungsplanung ausgegeben. Existierte dieses Arbeits­blatt bereits vor dem Start des Programms, so werden dort vorhandene Einträge vor der Ausgabe der Planungsergebnisse gelöscht. War das Arbeitsblatt noch nicht vorhanden, so wird es neu angelegt.

 

Das erste der beiden folgenden Bilder zeigt die Benutzerführung mit dem Eingabemodus „Prüfungs­anmeldungen“. Die Tabelle befand sich hier auf dem Arbeitsblatt Prüfungsmeldungen.

 

 

Das zweite Bild zeigt den Eingabemodus „Konfliktmatrix“. Die Konfliktmatrix befand sich in diesem Beispiel auf dem Arbeitsblatt Konfliktmatrix.

 

 

 

Zum Hintergrund der Konfliktgraphentechnik

 

In der Graphentheorie ist die Graphenfärbung  bzw., genauer, die Knoten­färbung eines Graphen ein geläufiges Problem. Die Knoten des Graphen müssen dabei so gefärbt werden, dass verbun­dene Knoten nicht dieselbe Farbe haben. Offensichtlich ist dies eine Aufgabe, welche mit dem zweiten Teil unserer Prüfungsplanung, nämlich der Ermittlung des Prüfungsplans aus dem Konflikt­graphen bzw. der  Konfliktmatrix, strukturgleich ist. Die Termine der Prüfungsplanung entsprechen den Farben der Knotenfärbung.

 

Es gibt noch weitere Fragestellungen, die mit der Knotenfärbung eines Graphen strukturgleich sind. Die bekanntesten sind:

• Die Färbung der Länder einer Landkarte. Länder mit gemeinsamer Grenze sollen nicht dieselbe Farbe haben.
• Das Einladungsproblem. Personen, die sich nicht vertragen, sollen nicht zu demselben Abend eingeladen werden.
• Das Quartierproblem. Personen, zwischen denen Konflikte zu erwarten sind, sollen nicht in demselben Zimmer einquartiert werden.
• Zuordnung der Sendefrequenzen an Mobilfunksender. Sender, deren Sendebereiche einander überlappen, sollen nicht mit derselben Frequenz senden.

 

 

 

 

 

 

Realisierung

 

Das Programm besitzt eine Schichtenarchitektur und ist im Prinzip objektorientiert, wenngleich auch zwei klassische Module zum Einsatz kommen.  Wir betrachten zunächst die Architektur. Anschlie­ßend gehen wir auf die Codierung der Kernbestandteile ein.

 

 

 

Architektur

 

Die Architektur ist dreischichtig (s. Bild unten). Die oberste Schicht besteht aus dem Formularmodul PruefungsplanungForm, welches die Kommunikation mit dem Benutzer steuert und den Ablauf des gesamten Programms koordiniert.

 

Die mittlere Schicht enthält die beiden Klassen ConflictMatrix und Graphenfaerbung, welche den Programmkern ausmachen, sowie das Standardmodul Ausgabe. ConflictMatrix enthält eine Funktion, welche aus einer Anmeldungsübersicht (s. oben) die dazu gehörige Konfliktmatrix erzeugt. Die Kon­flikt­matrix repräsentiert im Programm den Konfliktgraphen.

 

Die Klasse Graphenfaerbung ermittelt aus einer Konfliktmatrix eine Knotenfärbung für den Graphen, welcher der Matrix entspricht. In der Terminologie unserer Prüfungsplanung heißt dies: die Klasse ordnet die Prüfungen den Terminen zu. Es wird dabei wahlweise der simple sequenzielle Algorithmus oder der Welsh-Powell-Algorithmus angewendet. 

 

Das Standardmodul Ausgabe gibt die Ergebnisse der Planung, also die Konfliktmatrix und die Prüfungspläne nach beiden Algorithmen, auf einem Arbeitsblatt aus.

 

 

Die unterste Schicht enthält nur ein Standardmodul GR, welches allgemein anwendbare Hilfs­routinen zur Validierung der Eingaben und zur Formatierung der Ausgaben enthält. Dieses Modul wird nur aus den Modulen PruefungsplanungForm und Ausgabe aufgerufen, nicht aber aus den beiden Klassen des Programmkerns. Diese sind also völlig autonome Einheiten.

 

 

 

 

Die Klasse ConflictMatrix

 

Diese Klasse besitzt keine Instanzenvariablen und besteht lediglich aus einer Funktion KonfliktmatrAusPA, welche aus der im Parameter r enthaltenen Prüfungsmeldungsübersicht die Konfliktmatrix als zweidimensionales,  1-basiertes Integer-Array erzeugt. Weder r noch die Konfliktmatrix ist mit einer Beschriftung versehen. Stattdessen wird stillschweigend angenommen, dass in r sowohl die Prüfungen als auch die Teilnehmer mit 1 beginnend durchnummeriert sind. In der Konfliktmatrix sind die Prüfungen dann so angeordnet wie in den Spalten der Prüfungsmeldungsübersicht.

 

Die äußerste Schleife (i-Schleife) geht alle Zeilen der Prüfungsanmeldungsübersicht durch. In jeder Zeile wird mit Hilfe der beiden inneren Schleifen für jede mögliche Kombination von Prüfungen festgestellt, ob dafür für den betreffenden Teilnehmer Meldungen vorliegen. Wenn dies so ist, werden die entsprechenden Zellen der Konfliktmatrix KM mit einer 1 besetzt. Beachten Sie, dass KM symmetrisch ist und jede Kombination sich in zwei Zellen niederschlägt.

 

 

'Stellt die Konfliktmatrix zusammen, die der Tabelle r

'der Prüfungsmeldungen entspricht

 

Public Function KonfliktmatrAusPA (ByVal r As Range) As Integer()

    Dim KM() As Integer             'Konfliktmatrix

    Dim nC As Integer                'Anzahl der Prüfungen

    Dim nR As Long                   'Anzahl der Teilnehmer

    nC = r.Columns.Count

    nR = r.Rows.Count

    ReDim KM(1 To nC, 1 To nC)

    Dim i As Long, j As Long, k As Long

   

    For i = 1 To nR                     'für alle Teilnehmer

           For j = 1 To nC - 1

                    For k = j + 1 To nC

                            If r(i, j) = 1 And r(i, k) = 1 Then

                                    KM(j, k) = 1

                                    KM(k, j) = 1

                            End If

                    Next k

           Next j

    Next i

   

    KonfliktmatrAusPA = KM

End Function

 

 

 

 

Die Klasse Graphenfaerbung

 

Objekte dieser Klasse erstellen aus einer Konfliktmatrix einen Prüfungsplan in Form eines ein­dimensionalen Arrays  vom Typ Integer. Unten ist ein Beispiel eines solchen Arrays abgebildet. Die Indizes (obere Zeile) dieses Arrays entsprechen den Nummern der Prüfungen, die Werte (untere Zeile) den Terminen bzw. Farben, denen die Prüfungen zugeordnet sind. Im Beispiel ist die Prüfung 1 dem zweiten Termin zugeordnet, die Prüfung zwei dem ersten, usw. 

 

1	2	3	4	5	6	7	8	9	10
2	1	3	2	3	1	2	3	2	3

 

Der Prüfungsplan kann alternativ nach der simplen sequenziellen Methode oder nach der Welsh-Powell-Methode erstellt werden.  Dies ist möglich, weil die beiden Methoden nur Spezialfälle desselben Vorgehensprinzips sind. Bei beiden Methoden werden so lange maximale unabhängige Knotenmengen (MUKs)  aus dem Graphen entnommen und jeweils einem Termin bzw. einer Farbe zugeordnet, bis der Graph leer ist.  Unterschiedlich ist nur die Reihenfolge, in der die Knoten zur Bildung der MUKs herangezogen werden. Bei der simplen sequenziellen Methode ist keine bestimmte Reihenfolge vorgegeben, so dass man gewöhnlich die Knoten in Reihenfolge auf­stei­gender Knotennummern heranzieht. Folgt man dagegen der Welsh-Powell-Methode, so muss man die Knoten in der Reihenfolge absteigender Grade heranziehen.

 

 

 

Methoden

 

Die Klasse enthält zwei Methoden:

• Die Methode setGraph ist eine Prozedur, welche die Konfliktmatrix entgegennimmt, welche der Graphenfärbung zugrundeliegen soll, und diese Matrix in einer Instanzenvariablen (KM) zur weiteren Verwendung ablegt.
• Die Methode Faerbung ist die Funktion, welche den Prüfungsplan in Form des oben beschriebenen Arrays liefert. Faerbung wird mit einem Parameter namens Methode aufgerufen.  Gemeint ist hierbei die Färbungsmethode, welche  entweder „simple“ oder „welsh-powell“ sein kann.

Die Prozedur setGraph braucht im Verlauf des Programms nur einmal aufgerufen zu werden, und zwar zwischen der Erzeugung des Objekts und dem Abruf der Prüfungspläne.  Die Funktion Faerbung wird im Programm zweimal aufgerufen, je einmal für jede der angewandten Färbungsmethoden.

 

 

Instanzenvariablen

 

Die Klasse hat drei Instanzenvariablen:

• Variable KM ist ein Integer-Array, welches die Konfliktmatrix speichert.  Die Variable hat aber noch einen zusätzlichen Zweck. Ihre Diagonale, welche normalerweise nur Nullen enthält, wird benutzt, um den aktuellen Zustand des Konfliktgraphen während der Verarbeitung zu speichern: Befindet sich der Knoten i noch im Graphen, so ist das Element (i, i) von KM mit 1 besetzt, sonst mit 0.
• Eine zweite Instanzenvariable, ko, enthält eine Liste der Knoten des Graphen. Diese Liste gibt die Reihenfolge der Verarbeitung vor. Im Fall des simplen sequenziellen Algorithmus enthält ko die Knoten in der Reihenfolge aufsteigender Knotennummern, wird der Wesh-Powell-Algorithmus durchgeführt, so enthält ko die Knoten in der Reihenfolge absteigender Grade.
• Die dritte Instanzenvariable, nochKnoten, ist eine Indikatorvariable, welche anzeigt, ob der Algorithmus schon an seinem Ende angelangt ist, oder ob noch weitere Knoten  verarbeitet werden müssen.

 

 

Die Methode Faerbung

 

Diese Funktion ist recht übersichtlich und leicht verständlich, weil der größte Teil der Verarbeitungsschritte an Hilfsfunktionen delegiert wird.  Der Ablauf vollzieht sich in gut erkennbaren Etappen.      

1. Die Diagonalenelemente in KM werden auf 1 gesetzt. Wie oben erwähnt, ist eine 1 in der Zelle (i, i) von KM der Indikator dafür dass Knoten i sich noch im Graphen befindet.
2. Mit Hilfe der Prozedur setzeReihenfolge wird in ko eine Liste der Knoten in der Reihenfolge abgelegt, die für die gewünschte Färbungsmethode notwendig ist.
3. Eine MUK nach der anderen wird gefunden, aus dem Graphen entfernt und einem Termin zugewiesen. Die Hauptarbeit dabei ist an die Funktion naeMUK delegiert.

 

In der Funktion naeMUK wird die jeweils nächste MUK unter Berücksichtigung des aktuellen Zustands des Graphen zusammengestellt. Die Zusammenstellung dieser MUK beginnt mit der Suche nach dem ersten noch freien Knoten. Dies erledigt die Do-While-Schleife, welche die Variable i hochzählt, bis ein Knoten gefunden ist. Die Nummer dieses Knotens entspricht i.

 

Ist der erste Knoten der MUK gefunden, dann erfolgt die Suche der weiteren Knoten. Dies geschieht innerhalb der For-j-Schleife. Es kommen nur Knoten in Frage, die sich noch im Graphen befinden und die mit dem Knoten i unverbunden sind.  Für jeden der in Frage kommenden Knoten wir mit Hilfe der For-k-Schleife geprüft, ob ein Konflikt mit einem der Knoten besteht, die bereits in der MUK ent­halten sind. Wenn kein Konflikt gefunden wird, kann der Knoten j der MUK hinzugefügt werden.

 

Jeder der aufgenommen Knoten, einschließlich des Knotens i, muss aus der Graphen entfernt werden, indem das ihm entsprechende Element in der Diagonale von KM auf Null gesetzt wird.

 

Abschließend der Code der Klasse Graphenfaerbung:

 

 

Private KM() As Integer                 'Konfliktmatrix

Private ko() As Integer                   'Anordnung der Knoten für die Verarbeitung

Private nochKnoten As Boolean

 

 

 

'installiert den Konfliktgraph g

 

Public Sub setGraph(ByRef g() As Integer)

    KM = g

End Sub

 

 

 

 

'ermittelt  die Reihenfolge für die Abarbeitung der Knoten

'und legt sie in ko ab; benutzt hierzu maxPos

 

Private Sub setzeReihenfolge(ByVal methode As String)

 

    Dim i As Integer, j As Integer, anzKnoten As Integer, mPos As Integer

    Dim d() As Integer

    Dim degree As Integer

    anzKnoten = UBound(KM, 1)

    ReDim ko(1 To anzKnoten)

    ReDim d(1 To anzKnoten)

   

    'besetze ko mit der anzuwendenden Reihenfolge der Knoten

    If methode = "simple" Then

        For i = 1 To anzKnoten

            ko(i) = i

        Next i

    Else

        'ermittle die Grade aller Knoten und speichere sie in d

        For i = 1 To anzKnoten

           degree = 0

           For j = 1 To anzKnoten

              degree = degree + KM(i, j)

           Next j

           d(i) = degree

        Next i

       'deponiere Anordnung nach fallenden Graden in ko

        For i = 1 To anzKnoten

            mPos = maxPos(d)

            ko(i) = mPos

            d(mPos) = -1

        Next i

    End If

 

End Sub

 

 

 

 

'liefert die Position (den Index) des Elements mit dem höchsten Wert in deg

 

Private Function maxPos(ByRef deg() As Integer) As Integer

 

    Dim i As Integer, mp As Integer

    mp = 1

    For i = 2 To UBound(deg)

        If deg(i) > deg(mp) Then mp = i

    Next i

    maxPos = mp

 

End Function

 

 

 

 

'weist den Knoten die Farben zu

 

Public Function Faerbung(ByVal methode As String) As Integer()

 

    Dim i As Integer

    Dim t As Integer

    Dim p() As Integer

   

    'setze die Elemente der Diagonale auf 1 ("Knoten noch im Graph")

    For i = 1 To UBound(KM, 1)

        KM(i, i) = 1

    Next i

    nochKnoten = True

   

    'besetze Reihenfolge-Array ko je nach Methode

    setzeReihenfolge methode

   

    'suche MUKs und weise sie den Farben zu

    ReDim p(1 To UBound(KM, 1))

    t = 0

    Do While nochKnoten

        t = t + 1

        Dim muk() As Integer

        muk = naeMUK()

        For i = 1 To UBound(muk)

            p(muk(i)) = t

        Next i

    Loop

    Faerbung = p

 

End Function

 

 

 

 

'liefert eine MUK und setzt nochKnoten auf False, falls

'danach keine ungefärbten Knoten mehr existieren

 

Private Function naeMUK() As Integer()

 

    Dim muk() As Integer

    Dim anzKnoten As Integer

    Dim KnotenGefunden As Boolean

    anzKnoten = UBound(KM, 1)

    KnotenGefunden = False

    Dim i As Integer, j As Integer, k As Integer, l As Integer

   

    i = 1

    Do While Not KnotenGefunden And nochKnoten

   

        If KM(ko(i), ko(i)) = 1 Then                   'wenn noch im Graphen

            Dim aMUK As Integer

            aMUK = 1

            ReDim muk(1 To aMUK)

            muk(aMUK) = ko(i)                          'ko(i) der MUK hinzufügen

           

            For j = i + 1 To anzKnoten                 'nach weiteren Knoten suchen

                If KM(ko(j), ko(j)) = 1 And KM(ko(i), ko(j)) = 0 Then

                    'prüfen ob Konflikt zwischen ko(j) und MUK

                    Dim Konflikt As Boolean

                    Konflikt = False

                    For k = 1 To UBound(muk)

                        If KM(muk(k), ko(j)) = 1 Then

                            Konflikt = True

                            Exit For

                        End If

                    Next k

                    'ko(j) in MUK aufnehmen, wenn kein Konflikt

                    If Not Konflikt Then

                        aMUK = aMUK + 1

                        ReDim Preserve muk(1 To aMUK)

                        muk(aMUK) = ko(j)

                        KM(ko(j), ko(j)) = 0           'Knoten ko(j) aus Graph entfernen

                    End If

                End If

            Next j

            KM(ko(i), ko(i)) = 0                       'Knoten ko(i) aus Graph entfernen

            KnotenGefunden = True

        Else

            i = i + 1

        End If

       

        nochKnoten = False                              'noch Knoten im Graphen?

        For l = 1 To anzKnoten

            If KM(l, l) = 1 Then nochKnoten = True

        Next l

       

    Loop

   

    naeMUK = muk

   

End Function