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 Graphenfä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 sequenziellen 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:
- Finde eine maximale unabhängige Knotenmenge M in G
- Weise M dem nächsten freien Termin zu und entferne M aus G
- 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. Beispielsweise 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:
- Bestimme für jeden Knoten in G seinen Grad
- Liste die Knoten nach fallenden Graden auf. Haben zwei Knoten denselben Grad, kommt es auf ihre Reihenfolge nicht an.
- 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.
- Weise M dem nächsten freien Termin zu und lösche die Knoten von M aus der Liste
- 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 ausgehend 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üfungsmeldungen 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 symmetrisch. 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üfungsanmeldungen 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 Ergebnisse (s. oben) werden auf das Arbeitsblatt Prüfungsplanung ausgegeben. Existierte dieses Arbeitsblatt 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üfungsanmeldungen“. 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 Knotenfärbung eines Graphen ein geläufiges Problem. Die Knoten des Graphen müssen dabei so gefärbt werden, dass verbundene 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 Konfliktgraphen 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 Konfliktmatrix 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 Hilfsroutinen 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 eindimensionalen 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 aufsteigender 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.
- 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.
- 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.
- 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 enthalten 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