Bipartiter Graph Prüfer

Pseudocode

Ein Graph ist genau dann bipartit, wenn er sich mit zwei Farben färben lässt. Der Test ist also ein Durchlauf, der jeden Knoten entgegengesetzt zu seinem Vorgänger färbt und auf einen Konflikt achtet.

istBipartit(graph):
    farbe = {} für alle Knoten

    für jeden Knoten s ohne Farbe:     // jede Komponente
        farbe[s] = 0
        schlange = [s]
        solange die Schlange nicht leer ist:
            u = schlange.entnehmen()
            für jeden Nachbarn v von u:
                wenn v keine Farbe hat:
                    farbe[v] = 1 - farbe[u]
                    schlange.einfügen(v)
                sonst wenn farbe[v] == farbe[u]:
                    gib falsch zurück   // ungerader Zyklus

    gib wahr zurück

Der Konflikt ist kein beliebiges Fehlersignal, sondern ein Beweis. Erhalten zwei benachbarte Knoten dieselbe Farbe, so bilden die Baumwege von beiden zu ihrem gemeinsamen Vorfahren zusammen mit der verbindenden Kante einen Zyklus ungerader Länge. Bipartite Graphen sind genau die Graphen ohne ungeraden Zyklus, die Konfliktkante ist also ein Zertifikat, das du dem Aufrufer zurückgeben kannst.

Durchgerechnetes Beispiel, Schritt für Schritt

Färbe einen Vierer-Zyklus mit zwei Farben, füge dann eine Sehne hinzu und beobachte, wie derselbe Durchlauf ihn ablehnt.

Beispielgraph: Zuerst ein 4-Zyklus A-B, B-C, C-D, D-A. Dann derselbe Graph mit der zusätzlichen Sehne A-C.

1. Den 4-Zyklus von A aus färben. A erhält Farbe 0. Seine Nachbarn B und D erhalten Farbe 1. Von B aus ist der Nachbar C ungefärbt und erhält Farbe 0. Von D aus ist der Nachbar C bereits mit 0 gefärbt, während D die 1 trägt, was ein gültiger Unterschied ist, es entsteht also kein Konflikt.
2. Ergebnis für den 4-Zyklus. Die Farben sind A 0, B 1, C 0, D 1. Der Graph ist bipartit mit den Teilen {A, C} und {B, D}. Jede Kante verläuft zwischen den beiden Teilen und keine innerhalb eines Teils.
3. Die Sehne A-C hinzufügen. A und C tragen beide die Farbe 0, die Sehne verbindet nun also zwei Knoten desselben Teils. Führe den Durchlauf erneut von A aus: A erhält 0, und seine Nachbarn B, D und nun auch C erhalten alle die 1.
4. Der Konflikt tritt zutage. Beim Verarbeiten von B mit Farbe 1 trägt sein Nachbar C ebenfalls die Farbe 1. Das ist eine Kante innerhalb eines Teils, der Algorithmus gibt also an der Kante B-C falsch zurück.
5. Warum die Sehne es bricht. Die Sehne erzeugt das Dreieck A-B-C, einen Zyklus der Länge 3. Ungerade Zyklen lassen sich nicht mit zwei Farben färben: geht man einen ungeraden Zyklus abwechselnd färbend entlang, kommt man am Start an und bräuchte dort die andere Farbe als die bereits vergebene.

Der 4-Zyklus ist bipartit mit den Teilen {A, C} und {B, D}; das Hinzufügen der Sehne A-C macht ihn nicht bipartit, erkannt an der Kante B-C. Beachte die allgemeine Regel, die das zeigt: jeder gerade Zyklus ist bipartit und jeder ungerade nicht, allein die Zykluslänge entscheidet also. Beachte auch, dass der Konflikt an der Kante B-C gemeldet wurde und nicht an der Sehne selbst, was normal ist, denn der Algorithmus meldet dort, wo der Widerspruch zuerst auftritt, nicht dort, wo du die Schuld vermuten würdest.

Komplexität und woher sie kommt

Zeit: O(V + E) · Speicher: O(V)

Das ist eine einzige BFS oder DFS mit einem Vergleich je Kante, kostet also genau einen Durchlauf. Jeder Knoten wird einmal gefärbt und jede Kante von jedem Endpunkt einmal geprüft. Der Speicher ist eine Farbe je Knoten plus Warteschlange oder Rekursionsstapel, beides O(V). Die Schleife über alle Knoten fügt asymptotisch nichts hinzu und ist das, was unzusammenhängende Graphen zum Funktionieren bringt. Es gibt kein schnelleres Verfahren, da die Entscheidung über Bipartitheit jede Kante betrachten muss: eine einzige ungeprüfte Kante könnte genau jene sein, die einen ungeraden Zyklus erzeugt.

Wann Bipartit-Prüfung passt und wann nicht

Bipartitheit ist meist eine Vorbedingung und kein Ziel. Was du danach tust, hängt davon ab, warum du gefragt hast.

Häufige Fehler

• Nur von einem Knoten aus durchlaufen. Ein unzusammenhängender Graph ist nur bipartit, wenn jede Komponente es ist. Von einer einzigen Quelle zu starten prüft eine Komponente und lässt stillschweigend einen Graphen durch, der anderswo einen ungeraden Zyklus enthält. Iteriere über alle Knoten und starte von jedem ungefärbten einen neuen Durchlauf.
• Ungefärbt als Farbe behandeln. Die 0 sowohl für unbesucht als auch für Teil null zu verwenden lässt die Konfliktprüfung fehlgehen. Nutze einen eigenen Platzhalter wie -1 oder das Fehlen in einer Map, damit noch keine Farbe und Farbe 0 unterscheidbar bleiben.
• Vergessen, dass Schleifen fatal sind. Eine Schleife auf sich selbst ist ein ungerader Zyklus der Länge 1 und macht einen Graphen sofort nicht bipartit. Ein Durchlauf, der den Vorgänger überspringt, kann sie völlig übersehen, prüfe Schleifen also ausdrücklich.
• Annehmen, azyklisch sei der interessante Fall. Jeder Baum und jeder Wald ist trivialerweise bipartit, da er überhaupt keine Zyklen hat. Der Test wird erst aussagekräftig, sobald Zyklen existieren, triviale Erfolge auf baumförmigen Eingaben beweisen also sehr wenig.
• Ihn ohne Symmetrisierung auf gerichtete Graphen anwenden. Bipartitheit ist eine ungerichtete Eigenschaft. Bei einem gerichteten Graphen musst du entscheiden, ob eine Einbahnkante als Nachbarschaft zählt, und die Kanten symmetrisch behandeln, sonst ist die Antwort nicht wohldefiniert.

Häufig gestellte Fragen

Was ist ein bipartiter Graph?

Ein bipartiter Graph ist einer, dessen Knoten sich so in zwei Mengen aufteilen lassen, dass jede Kante einen Knoten der einen mit einem Knoten der anderen verbindet und keine Kante innerhalb einer Menge verläuft. Gleichbedeutend ist es ein Graph, der sich korrekt mit zwei Farben färben lässt, und wiederum gleichbedeutend ein Graph ohne Zyklus ungerader Länge.

Wie prüft man, ob ein Graph bipartit ist?

Führe eine BFS oder DFS aus und färbe jeden neu erreichten Knoten entgegengesetzt zu dem Knoten, von dem du kamst. Findest du je eine Kante, deren beide Endpunkte bereits dieselbe Farbe tragen, ist der Graph nicht bipartit. Wiederhole das von jedem ungefärbten Knoten, damit alle Komponenten erfasst werden. Der gesamte Test ist O(V + E).

Warum sind ungerade Zyklen der entscheidende Faktor?

Weil die Farben entlang jedes Weges alternieren müssen. Ein Zyklus gerader Länge führt dich zum Start mit genau der Farbe zurück, mit der du begonnen hast, was konsistent ist. Ein ungerader Zyklus führt dich zurück, wobei du die entgegengesetzte Farbe zur bereits vergebenen bräuchtest, was ein Widerspruch ist. Ein Graph ist also genau dann bipartit, wenn er keinen ungeraden Zyklus hat.

Wie ist die Zeitkomplexität der Bipartitheitsprüfung?

O(V + E) Zeit und O(V) Speicher. Es ist ein einziger Durchlauf mit einem Farbvergleich je Kante. Das ist optimal, denn jede ungeprüfte Kante könnte genau jene sein, die einen ungeraden Zyklus erzeugt, also müssen alle betrachtet werden.

Wofür werden bipartite Graphen verwendet?

Zur Modellierung jeder zweiseitigen Beziehung: Bewerber und Stellen, Studierende und Kurse, Käufer und Verkäufer, Dokumente und Begriffe. Sobald ein Graph als bipartit bekannt ist, wird maximales Matching mit Hopcroft-Karp effizient lösbar, was Zuordnungsprobleme, Ablaufplanung und Empfehlungssysteme trägt.