Bipartite Graphen erklärt

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Was einen Graphen bipartit macht

Ein Graph ist bipartit, wenn sich seine Knoten so in zwei Gruppen aufteilen lassen, dass jede Kante von einer Gruppe zur anderen verläuft. Keine Kante darf innerhalb einer Gruppe bleiben. Die beiden Gruppen heißen die Seiten oder Teile des Graphen, und die Aufteilung selbst ist eine Bipartition.

Formal ist ein Graph G = (V, E) bipartit, wenn es disjunkte Mengen U und W mit U ∪ W = V gibt, sodass jede Kante ein Ende in U und das andere in W hat. Viele Lehrbücher schreiben den Graphen als G = (U, W, E), um die Aufteilung im Blick zu behalten. Nichts verlangt, dass jede mögliche Kante zwischen den Seiten vorhanden ist, und nichts verlangt gleich große Seiten. Die einzige Regel ist ein Verbot: Es gibt keine Kante innerhalb von U und keine Kante innerhalb von W. In der Sprache des Leitfadens zu Knoten und Kanten sind beide Seiten unabhängige Mengen.

Die Eigenschaft ist leicht zu formulieren und überraschend leicht zu übersehen. Der Graph links in der folgenden Abbildung ist das durchgehende Beispiel dieses ganzen Artikels: acht Knoten, neun Kanten. Als Ring mit einer Sehne gezeichnet, sieht er nach nichts Besonderem aus. Sortiert man dieselben Knoten in zwei Spalten, ist die Struktur offensichtlich.

Die Kantenliste ist kurz genug, um sie im Kopf zu behalten:

V = {A, B, C, D, E, F, G, H}
E = {AB, AD, AF, BC, CF, DE, EH, FG, GH}          9 Kanten

U = {A, C, E, G}      W = {B, D, F, H}             jede Kante verbindet U mit W

Zwei Sonderfälle sollte man gleich zu Beginn klären. Eine Schleife verbindet einen Knoten mit sich selbst, also liegen beide Enden auf derselben Seite, und ein Graph mit einer Schleife ist nie bipartit. Parallele Kanten ändern nichts: Eine zweite Kante zwischen u und v verläuft genauso zwischen den Seiten wie die erste. Das ist eine der Eigenschaften, die der Leitfaden zu einfachen Graphen und Multigraphen als unabhängig von der Vielfachheit aufführt. Bei einem gerichteten Graphen stellt man die Frage für den zugrunde liegenden ungerichteten Graphen, denn die Definition achtet nie darauf, in welche Richtung eine Kante zeigt.

2. Zwei Farben, eine Bipartition

Färben Sie die Knoten von U blau und die Knoten von W orange. Die Definition besagt dann, dass die beiden Enden jeder Kante verschiedene Farben haben, und das ist genau eine zulässige Färbung mit zwei Farben. Die beiden Beschreibungen sind austauschbar:

Ein Graph ist genau dann bipartit, wenn er sich zulässig mit zwei Farben färben lässt. Seine chromatische Zahl ist dann höchstens 2: genau 2, wenn er mindestens eine Kante hat, und 1, wenn er keine hat.

Die Färbungssicht erklärt eine Tatsache, die die Mengensicht verbirgt. In einem zusammenhängenden bipartiten Graphen ist die Bipartition eindeutig, bis auf das Vertauschen der Namen der beiden Seiten. Färben Sie irgendeinen Knoten blau, und jeder andere Knoten ist festgelegt: Ein Nachbar muss orange sein, ein Nachbar eines Nachbarn blau, und allgemein wird ein Knoten genau dann blau, wenn sein Abstand zum Startknoten gerade ist. Nirgends bleibt eine Wahl. Im durchgehenden Beispiel ist {A, C, E, G} gegen {B, D, F, H} die einzig mögliche Aufteilung.

Ein Graph mit mehreren Komponenten verhält sich anders, weil sich jede Komponente für sich umfärben lässt. Bei k Komponenten gibt es 2k zulässige Zweifärbungen und 2k−1 verschiedene Bipartitionen, wobei jeder isolierte Knoten als eigene Komponente zählt. Die Frage „Auf welcher Seite liegt der Knoten v?“ ist also innerhalb einer Komponente sinnvoll und zwischen Komponenten willkürlich. Code, der für jeden Knoten eine einzige globale Seite speichert und dann Seiten zwischen nicht verbundenen Teilen vergleicht, vergleicht Etiketten, die unabhängig voneinander gewählt wurden.

3. Bipartite Graphen, die Sie schon kennen

Bipartite Graphen sind kein Spezialthema, das in einem späteren Kapitel versteckt ist. Mehrere der bekanntesten Familien sind bipartit, manche aus Gründen, die man erst auf den zweiten Blick sieht.

• Bäume und Wälder. Ein Baum hat überhaupt keine Kreise, also kann nichts schiefgehen: Wurzeln Sie ihn irgendwo und färben Sie jeden Knoten danach, ob seine Tiefe gerade oder ungerade ist. Jeder Baum ist bipartit, eine weitere Folge der Struktur, die im Leitfaden zu Bäumen in der Graphentheorie entwickelt wird.
• Wege und gerade Kreise. Ein Weg wechselt die Farben entlang seiner Länge ab. Ein Kreis mit einer geraden Anzahl von Knoten tut das auch und schließt sich korrekt. Ein Kreis mit einer ungeraden Anzahl tut es nicht, wie der nächste Abschnitt beweist.
• Gitter und Schachbretter. Färben Sie das Feld in Zeile r und Spalte c nach der Parität von r + c, und Sie erhalten das Schachbrettmuster. Ein Schritt auf ein Nachbarfeld ändert die Parität, also ist der Gittergraph bipartit. Ein Springerzug ändert eine Koordinate um 1 und die andere um 2, insgesamt eine ungerade Zahl, also landet ein Springer immer auf der anderen Farbe, und auch der Springergraph ist bipartit.
• Hyperwürfel. Der Würfelgraph Qn hat die n-Bit-Folgen als Knoten, mit einer Kante zwischen zwei Folgen, die sich in genau einem Bit unterscheiden. Ein Bit umzudrehen ändert die Anzahl der Einsen um eins, also funktioniert die Färbung nach der Parität dieser Anzahl.
• Alles, was aus zwei Arten von Dingen besteht. Bewerber und Stellen, Nutzer und Produkte, Autoren und Artikel, Studierende und Kurse. Wenn jede Kante die eine Art mit der anderen verbindet, ist der Graph schon durch seine Konstruktion bipartit.

Das Schachbrettbeispiel hat eine klassische Pointe. Entfernen Sie zwei diagonal gegenüberliegende Ecken eines 8-mal-8-Bretts. Lassen sich die übrigen 62 Felder mit 31 Dominosteinen auslegen? Jeder Dominostein bedeckt zwei benachbarte Felder, eines von jeder Farbe. Die beiden entfernten Ecken haben dieselbe Farbe, also hat das Brett jetzt 30 Felder der einen und 32 der anderen Farbe, und keine Auslegung kann existieren. In der Sprache der Graphen ist eine Dominoauslegung ein perfektes Matching im Gittergraphen, ein perfektes Matching in einem bipartiten Graphen braucht gleich große Seiten, und diese Seiten sind ungleich. Das Rätsel wurde 1946 von dem Philosophen Max Black diskutiert und später durch Martin Gardner berühmt; es ist das kürzeste Argument überhaupt dafür, dass es sich lohnt, auf Bipartitheit zu achten.

Ebenso nützlich sind die Graphen, die nicht bipartit sind. Jeder Graph mit einem Dreieck scheitert, denn drei paarweise benachbarte Knoten brauchen drei Farben. Das schließt jeden vollständigen Graphen Kn mit n ≥ 3 aus, und auch die sieben Brücken von Königsberg: Das Nordufer, die Insel und die östliche Insel bilden ein Dreieck. Der Petersen-Graph scheitert, ohne überhaupt ein Dreieck zu enthalten, weil er voller Kreise der Länge 5 ist.

4. Der Satz von Kőnig: keine ungeraden Kreise

Dreiecke sind ein Hindernis, aber nicht das eigentliche. Das eigentliche Hindernis ist jeder Kreis ungerader Länge, und es ist das einzige Hindernis, das es gibt.

Satz. Ein Graph ist genau dann bipartit, wenn er keinen Kreis ungerader Länge enthält.

Das Ergebnis geht auf Dénes Kőnig zurück. Asratian, Denley und Häggkvist führen es auf seine Arbeit von 1916 in der Zeitschrift Mathematische Annalen zurück, und mit Beweis erscheint es 1936 in seinem Buch Theorie der endlichen und unendlichen Graphen, dem ersten Lehrbuch der Graphentheorie (demselben Buch, das im Artikel über endliche und unendliche Graphen besprochen wird). Beide Richtungen des Beweises sind kurz, und die zweite ist ein verkleideter Algorithmus.

Bipartit heißt: kein ungerader Kreis. Gehen Sie einen Kreis v0, v1, …, vk−1 entlang und zurück zu v0. Jeder Schritt wechselt die Farbe, also hat vi dieselbe Farbe wie v0 genau dann, wenn i gerade ist. Die schließende Kante von vk−1 nach v0 verbindet nur dann zwei verschiedene Farben, wenn k − 1 ungerade ist, also nur, wenn die Kreislänge k gerade ist.

Kein ungerader Kreis heißt: bipartit. Arbeiten Sie eine Komponente nach der anderen ab und wählen Sie eine beliebige Wurzel r. Färben Sie jeden Knoten nach der Parität seines Abstands von r. Angenommen, eine Kante uv verbände zwei Knoten derselben Farbe, sodass d(u) und d(v) dieselbe Parität haben. Folgen Sie einem kürzesten Weg von r nach u, überqueren Sie die Kante nach v und folgen Sie einem kürzesten Weg von v zurück nach r. Dieser geschlossene Kantenzug hat die Länge d(u) + d(v) + 1, und die ist ungerade.

Ein geschlossener Kantenzug ist noch kein Kreis, weil er Knoten mehrfach besuchen kann, und genau diesen Schritt überspringen nachlässige Beweise. Repariert wird er durch ein kleines Lemma: Jeder geschlossene Kantenzug ungerader Länge enthält einen Kreis ungerader Länge. Wiederholt der Kantenzug einen Knoten, teilen Sie ihn dort in zwei kürzere geschlossene Kantenzüge; ihre Längen ergeben zusammen eine ungerade Zahl, also ist einer von beiden ungerade, und Induktion über die Länge erledigt den Rest. Der ungerade Kreis widerspricht der Annahme, also gibt es keine solche Kante, und die Abstandsfärbung ist zulässig.

Das mittlere Feld der Abbildung enthält die Falle, die man sich merken sollte. Der 5-Kreis ist dreiecksfrei und trotzdem nicht bipartit. „Keine Dreiecke“ ist eine notwendige Bedingung und bei Weitem keine hinreichende. Jede ungerade Länge zählt.

Das durchgehende Beispiel besteht den Test. Seine Kreise haben die Längen 4 (A, B, C, F), 6 (A, D, E, H, G, F) und 8 (der äußere Ring), alle gerade. Zwei einfache Folgerungen sollte man parat haben. Das Löschen von Kanten oder Knoten kann nie einen ungeraden Kreis erzeugen, also ist jeder Teilgraph eines bipartiten Graphen bipartit. Das Hinzufügen einer einzigen Kante kann die Eigenschaft dagegen zerstören, wie der nächste Abschnitt zeigt.

5. Ein Test in linearer Zeit

Die zweite Hälfte des Beweises ist ein Verfahren. Starten Sie eine Breitensuche von einem beliebigen Knoten, geben Sie jedem neu entdeckten Knoten die Farbe, die der seines Elternknotens entgegengesetzt ist, und beobachten Sie jede Kante, die Sie untersuchen. Hat irgendeine Kante an beiden Enden dieselbe Farbe, ist der Graph nicht bipartit. Endet die Suche, ohne dass das passiert, bilden die Farben eine gültige Bipartition. Wiederholen Sie das von einem ungefärbten Knoten aus, bis jede Komponente durchsucht ist.

Ein guter Test leistet mehr als Ja oder Nein. Er liefert ein Zertifikat, das sich unabhängig prüfen lässt: die Zweifärbung, wenn die Antwort Ja lautet, und einen tatsächlichen ungeraden Kreis, wenn sie Nein lautet. Die folgende Funktion tut beides.

from collections import deque

def bipartite_or_odd_cycle(graph):
    """Liefert (True, colour) oder (False, odd_cycle) für einen ungerichteten Graphen."""
    colour, parent, depth = {}, {}, {}
    for start in graph:                      # jede Komponente, nicht nur eine
        if start in colour:
            continue
        colour[start], parent[start], depth[start] = 0, None, 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if v not in colour:          # Baumkante: v bekommt die andere Farbe
                    colour[v], parent[v], depth[v] = 1 - colour[u], u, depth[u] + 1
                    queue.append(v)
                elif colour[v] == colour[u]: # gleiche Farbe an beiden Enden: ungerader Kreis
                    return False, odd_cycle(u, v, parent, depth)
    return True, colour

def odd_cycle(u, v, parent, depth):
    # u und v liegen in derselben BFS-Tiefe; aufsteigen, bis sich die Wege treffen.
    left, right = [u], [v]
    while u != v:
        u, v = parent[u], parent[v]
        left.append(u)
        right.append(v)
    return left + right[-2::-1]              # u ... Treffpunkt ... v, geschlossen durch die Kante v-u

graph = {
    'A': ['B', 'D', 'F'], 'B': ['A', 'C'], 'C': ['B', 'F'], 'D': ['A', 'E'],
    'E': ['D', 'H'], 'F': ['A', 'C', 'G'], 'G': ['F', 'H'], 'H': ['E', 'G'],
}
ok, colour = bipartite_or_odd_cycle(graph)
print(ok, sorted(v for v in colour if colour[v] == 0))
# True ['A', 'C', 'E', 'G']

graph['C'].append('E'); graph['E'].append('C')   # eine zusätzliche Kante
print(bipartite_or_odd_cycle(graph))
# (False, ['C', 'B', 'A', 'D', 'E'])

Die Extraktion des Kreises beruht auf einer Eigenschaft der Breitensuche: Jede Kante verbindet zwei Knoten, deren Tiefen sich um höchstens eins unterscheiden. Zwei Knoten derselben Farbe haben Tiefen derselben Parität, also verbindet eine Konfliktkante immer zwei Knoten in derselben Tiefe. Steigt man ihre Elternzeiger im Gleichschritt hinauf, erreicht man den Treffpunkt deshalb von beiden Seiten im selben Moment. Brauchen die beiden Aufstiege je t Schritte, hat der Kreis 2t + 1 Kanten, was nach Konstruktion ungerade ist.

So läuft es im durchgehenden Beispiel ab, und danach mit einer zusätzlichen Kante von C nach E:

BFS ab A          Ebene 0: A    Ebene 1: B, D, F    Ebene 2: C, E, G    Ebene 3: H
                  jede Kante verbindet benachbarte Ebenen   → bipartit, Farbe 0 = {A, C, E, G}

Kante C-E dazu    C und E liegen beide in Ebene 2, haben also dieselbe Farbe
                  Aufstieg ab C: C, B, A    Aufstieg ab E: E, D, A    Treffpunkt A
                  ungerader Kreis C, B, A, D, E    5 Kanten

Jeder Knoten wird einmal in die Warteschlange gestellt und jede Kante zweimal untersucht, einmal von jedem Ende, also läuft der Test in O(V + E) Zeit. Das ist so schnell wie das Einlesen des Graphen. Eine Tiefensuche funktioniert im Prinzip genauso, aber eine rekursive DFS in Python stößt auf einem langen Weg an das voreingestellte Rekursionslimit von 1.000, und das ist ein Grund, warum die iterative Breitensuche die sicherere Standardwahl ist.

Eine Variante sollte man kennen. Wenn Kanten einzeln eintreffen und Sie nach jedem Einfügen wissen müssen, ob der Graph noch bipartit ist, ist ein erneuter Suchlauf verschwenderisch. Eine Union-Find-Struktur, die zusätzlich die Parität jedes Knotens relativ zu seiner Wurzel speichert, beantwortet die Frage in nahezu konstanter amortisierter Zeit pro Kante: Zwei Knoten, die schon eine gemeinsame Wurzel haben, dürfen nur verbunden werden, wenn ihre Paritäten verschieden sind.

6. Vollständig bipartite Graphen und die Obergrenze n²/4

Der vollständig bipartite Graph Km,n hat m Knoten auf der einen Seite, n auf der anderen und alle m × n möglichen Kanten zwischen den Seiten. Er ist für bipartite Graphen, was Kn für Graphen allgemein ist: das dichteste Mitglied der Familie bei gegebenen Seitengrößen.

Zwei Mitglieder haben eigene Namen. K1,n ist der Stern, ein Zentrum, das mit n Blättern verbunden ist, und zugleich ein Baum. K3,3 ist der Versorgungsgraph aus dem alten Rätsel, bei dem drei Häuser so mit drei Versorgern verbunden werden sollen, dass sich keine Leitungen kreuzen. Das Rätsel hat keine Lösung: Der Satz von Kuratowski aus dem Jahr 1930 besagt, dass ein Graph genau dann planar ist, wenn er keine Unterteilung von K5 oder K3,3 enthält, und K3,3 ist eine der beiden verbotenen Formen.

Die Bipartitheit liefert einen sehr kurzen Beweis dafür, dass K3,3 nicht planar ist. In einer kreuzungsfreien Zeichnung ist jede Fläche von einem geschlossenen Kantenzug umgeben. Ein bipartiter Graph hat keine Dreiecke, also hat in einem einfachen, zusammenhängenden, planaren bipartiten Graphen mit mindestens drei Knoten jeder Flächenrand mindestens 4 Kanten. Jede Kante wird über alle Flächenränder insgesamt zweimal gezählt, und das ergibt 4f ≤ 2m. Eingesetzt in die Eulersche Formel v − m + f = 2 ergibt sich

m ≤ 2v − 4        für einen einfachen, zusammenhängenden, planaren bipartiten Graphen mit v ≥ 3

K3,3:   v = 6,  m = 9,  aber 2v − 4 = 8        also gibt es keine planare Zeichnung

Eine zweite klassische Schranke betrifft die Dichte. Hat eine Seite k Knoten und die andere n − k, gibt es höchstens k(n − k) Kanten, und dieses Produkt ist am größten, wenn die Seiten so gleich groß wie möglich sind. Ein bipartiter Graph mit n Knoten hat also höchstens ⌊n²/4⌋ Kanten, erreicht von K⌊n/2⌋,⌈n/2⌉. Mantel bewies 1907, dass dieselbe Obergrenze für jeden dreiecksfreien Graphen gilt, wobei der ausgeglichene vollständig bipartite Graph der einzige Graph ist, der sie erreicht. Das passt verblüffend zur Falle aus Abschnitt 4: Dreiecksfreie Graphen müssen nicht bipartit sein, doch der dichteste dreiecksfreie Graph ist es immer. Das durchgehende Beispiel hat 9 Kanten bei einer Obergrenze von 16, der Kantenzahl von K4,4.

Die Grade gehorchen einer schärferen Version des Handschlaglemmas. Jede Kante hat genau ein Ende auf jeder Seite, also

∑ deg(u) über u in U  =  |E|  =  ∑ deg(w) über w in W

Beispiel:  3 + 2 + 2 + 2  =  9  =  2 + 2 + 3 + 2

Eine schnelle Folgerung: Hat jeder Knoten denselben Grad k ≥ 1, dann gilt k|U| = k|W|, also hat ein regulärer bipartiter Graph immer zwei gleich große Seiten. Diese Tatsache ist der erste Schritt zu den Matching-Ergebnissen im nächsten Abschnitt.

7. Matchings: warum bipartite Graphen wichtig sind

Ein Matching ist eine Menge von Kanten, von denen keine zwei einen Knoten gemeinsam haben. In einem bipartiten Graphen ist es eine Zuordnung: Jeder Bewerber bekommt höchstens eine Stelle und jede Stelle höchstens einen Bewerber. Ein Matching ist perfekt, wenn es jeden Knoten überdeckt. Dass bipartite Graphen ganze Lehrbücher füllen, liegt vor allem daran, dass Matching-Probleme auf ihnen zugleich wichtig und effizient lösbar sind und die Theorie exakte Zertifikate mitliefert.

Das erste Zertifikat sagt, wann jeder auf einer Seite bedient werden kann.

Heiratssatz von Hall (1935). Ein bipartiter Graph G = (U, W, E) hat genau dann ein Matching, das jeden Knoten von U überdeckt, wenn jede Teilmenge S ⊆ U mindestens |S| Nachbarn in W hat.

Lesen Sie die Voraussetzung genau, denn sie wird oft falsch zitiert. Halls Bedingung betrifft das Überdecken einer Seite, nicht ein perfektes Matching. Beides fällt nur zusammen, wenn |U| = |W| gilt. Die Notwendigkeit ist offensichtlich: Sind zwei Bewerber jeweils nur für eine einzige Stelle geeignet, und zwar für dieselbe, können nicht beide untergebracht werden. Halls Beitrag ist, dass diese Art lokaler Knappheit das Einzige ist, was schiefgehen kann. Eine Folgerung, die Kőnig 1916 bewies: Jeder k-reguläre bipartite Graph mit k ≥ 1 hat ein perfektes Matching.

Das zweite Zertifikat beweist, dass sich ein Matching nicht verbessern lässt. Eine Knotenüberdeckung ist eine Menge von Knoten, die jede Kante berührt. Jede Kante eines Matchings braucht ihren eigenen Überdeckungsknoten, also ist kein Matching größer als irgendeine Überdeckung. In bipartiten Graphen treffen sich beide:

Satz von Kőnig und Egerváry (1931). In einem bipartiten Graphen ist die Größe eines größten Matchings gleich der Größe einer kleinsten Knotenüberdeckung.

Außerhalb bipartiter Graphen scheitert das bei der ersten Gelegenheit: Ein Dreieck hat ein größtes Matching der Größe 1 und eine kleinste Knotenüberdeckung der Größe 2. Im durchgehenden Beispiel gibt es ein Matching der Größe 4, und {A, C, E, G} ist eine Knotenüberdeckung der Größe 4, also bescheinigt jedes dem anderen ohne jede Suche, optimal zu sein.

Ein größtes Matching findet man mit augmentierenden Wegen: Ein solcher Weg beginnt an einem freien Knoten, wechselt zwischen Kanten außerhalb und innerhalb des Matchings ab und endet an einem anderen freien Knoten. Vertauscht man entlang des Weges die beiden Kantenarten, wächst das Matching um eins. Berge bewies 1957, dass ein Matching genau dann ein größtes ist, wenn kein augmentierender Weg existiert. In einem bipartiten Graphen ist die Suche nach einem solchen Weg eine einfache Tiefensuche, und das ergibt die kurze Methode, die oft Kuhns Algorithmus genannt wird:

def max_matching(left, adj):
    """Kuhns Algorithmus mit augmentierenden Wegen. adj ordnet jedem linken Knoten seine rechten Nachbarn zu."""
    match_of = {}                            # rechter Knoten -> linker Knoten

    def augment(u, seen):
        for v in adj[u]:
            if v in seen:
                continue
            seen.add(v)
            # v ist frei, oder sein Partner kann zu einem anderen rechten Knoten wechseln
            if v not in match_of or augment(match_of[v], seen):
                match_of[v] = u
                return True
        return False

    size = sum(augment(u, set()) for u in left)
    return size, {u: v for v, u in match_of.items()}

adj = {'A': ['B', 'D', 'F'], 'C': ['B', 'F'], 'E': ['D', 'H'], 'G': ['F', 'H']}
size, pairs = max_matching(['A', 'C', 'E', 'G'], adj)
print(size, dict(sorted(pairs.items())))
# 4 {'A': 'D', 'C': 'B', 'E': 'H', 'G': 'F'}

Das Ergebnis ist ein perfektes Matching, A–D, C–B, E–H, G–F. Es ist nicht das einzige: Dieser Graph hat genau drei perfekte Matchings. Die Methode läuft in O(V · E) Zeit und braucht wie jede rekursive Suche in Python für sehr tiefe Graphen eine iterative Umschreibung. Für große Instanzen ist der Hopcroft-Karp-Algorithmus von 1973 die Standardwahl; er findet pro Phase viele kürzeste augmentierende Wege und läuft in O(E √V).

Drei verwandte Probleme sollte man beim Namen kennen:

• Gewichtete Zuordnung. Hat jede Kante Kosten und suchen Sie das billigste perfekte Matching, löst die Ungarische Methode von Kuhn (1955) das Problem effizient. Der Leitfaden zur Arbeitszuordnung wendet sie auf echte Personalentscheidungen an.
• Matching als Fluss. Fügen Sie eine Quelle hinzu, die mit jedem Knoten von U verbunden ist, und eine Senke, zu der jeder Knoten von W führt, geben Sie jeder Kante die Kapazität 1, und ein maximaler Fluss ist ein größtes Matching. Der Satz von Kőnig und Egerváry wird dann zu einem Spezialfall von maximaler Fluss gleich minimalem Schnitt.
• Stabiles Matching. Wenn beide Seiten einander in eine Rangfolge bringen, zeigten Gale und Shapley (1962), dass immer ein Matching ohne ein Paar existiert, das lieber zusammen wäre, und gaben den Algorithmus an, der es findet.

8. Kantenfärbung und Stundenpläne

Färbt man die Kanten eines Graphen so, dass Kanten mit einem gemeinsamen Ende verschiedene Farben bekommen, braucht man mindestens Δ Farben, wobei Δ der Maximalgrad ist, denn die Kanten an einem Knoten mit höchstem Grad kollidieren alle miteinander. Für allgemeine Graphen reicht das nicht immer: Ein Dreieck hat Δ = 2 und braucht 3 Farben, und Vizing bewies 1964, dass Δ + 1 für einfache Graphen immer genügt. Bipartite Graphen brauchen die zusätzliche Farbe nie.

Kantenfärbungssatz von Kőnig (1916). Die Kanten jedes bipartiten Graphen, Multigraphen eingeschlossen, lassen sich mit genau Δ Farben färben.

Eine Begründung nutzt den Satz von Hall: Ein bipartiter Graph lässt sich mit zusätzlichen Knoten und Kanten zu einem Δ-regulären bipartiten Multigraphen auffüllen, der dann in Δ perfekte Matchings zerfällt, eines pro Farbe. Das durchgehende Beispiel hat Δ = 3, bei den Knoten A und F, und drei Farben genügen.

Das ist der Satz hinter Stundenplänen an Schulen. Setzen Sie die Lehrkräfte auf die eine Seite und die Klassen auf die andere, und zeichnen Sie eine Kante für jede Unterrichtsstunde, die eine Lehrkraft einer Klasse pro Woche gibt, mit parallelen Kanten, wenn dieselbe Lehrkraft dieselbe Klasse mehrmals sieht. Eine Farbe ist ein Zeitfenster, und eine zulässige Kantenfärbung ist ein Stundenplan, in dem keine Lehrkraft und keine Klasse an zwei Orten zugleich ist. Der Satz von Kőnig besagt, dass die Zahl der benötigten Zeitfenster gleich der höchsten Wochenlast einer einzelnen Lehrkraft oder Klasse ist, nie mehr. Echte Stundenpläne fügen Räume und Wünsche hinzu, die die saubere bipartite Struktur aufbrechen, und dort wird das Problem schwer, aber der Kern der Zuordnung ist eine bipartite Kantenfärbung.

9. Die Matrixsicht

Listen Sie zuerst die Knoten von U und danach die von W auf, und die Adjazenzmatrix eines bipartiten Graphen zerfällt in Blöcke. Beide Diagonalblöcke sind null, weil es innerhalb einer Seite keine Kanten gibt:

A  =  [ 0    B ]            B ist die |U| × |W|-Biadjazenzmatrix
      [ Bᵀ   0 ]

B für das Beispiel     B  D  F  H
                   A [ 1  1  1  0 ]
                   C [ 1  0  1  0 ]
                   E [ 0  1  0  1 ]
                   G [ 0  0  1  1 ]

Der Nebendiagonalblock B, die Biadjazenzmatrix, enthält die gesamte Information, deshalb speichern Programme nur ihn. Eine Bewertungstabelle aus Nutzern und Artikeln ist genau eine gewichtete Biadjazenzmatrix, weshalb Empfehlungssysteme von Natur aus Graphenprobleme sind; die Abwägungen zwischen Speicherformaten behandelt der Artikel zur Darstellung von Graphen.

Die Blockstruktur hinterlässt einen Fingerabdruck in den Eigenwerten. Erfüllt ein Vektor (x, y), nach Seiten aufgeteilt, die Gleichung A(x, y) = λ(x, y), dann erfüllt (x, −y) dieselbe Gleichung mit −λ. Das Spektrum eines bipartiten Graphen ist also symmetrisch um null, und auch die Umkehrung gilt: Ein Graph, dessen Adjazenzspektrum symmetrisch um null ist, ist bipartit. Die Eigenwerte des durchgehenden Beispiels sind ±2,356, ±1,477, ±1,095 und ±0,262, in perfekten Paaren. Fügen Sie die Kante von C nach E hinzu, und die Paarung bricht, mit dem größten Eigenwert bei 2,592 und dem kleinsten bei −2,281. Für einen zusammenhängenden Graphen entscheidet eine einzige Zahl: Der Graph ist genau dann bipartit, wenn das Negative seines größten Eigenwerts ebenfalls ein Eigenwert ist. Der 5-Kreis zum Beispiel hat den Eigenwert 2, aber nicht −2.

Chemiker fanden das, bevor Graphentheoretiker es benannten. 1940 zeigten Coulson und Rushbrooke, dass bei alternierenden Kohlenwasserstoffen, deren Kohlenstoffatome sich in zwei Mengen mit Bindungen nur zwischen den Mengen aufteilen, die Energieniveaus der π-Elektronen in Paaren auftreten, die symmetrisch um die Mitte liegen. Dieser Paarungssatz ist die Spektralsymmetrie bipartiter Graphen, formuliert für Moleküle. Der weitere Zusammenhang zwischen Eigenwerten und Struktur ist Thema der spektralen Graphentheorie.

10. Wo bipartite Graphen vorkommen

Bipartite Graphen sind das ehrliche Modell, wann immer ein System zwei verschiedene Arten von Objekten in Beziehung setzt und nie zwei Objekte derselben Art direkt.

Zwei Zeilen verdienen einen genaueren Blick. In der Codierungstheorie führte Tanner 1981 den heute nach ihm benannten Graphen ein, mit Codebits auf der einen und Paritätsprüfungen auf der anderen Seite. Moderne LDPC-Codes (Low-Density Parity-Check), die in WLAN und 5G eingesetzt werden, werden decodiert, indem Nachrichten entlang der Kanten genau dieses bipartiten Graphen hin- und hergeschickt werden. Und jeder Hypergraph, in dem eine Kante mehr als zwei Knoten verbinden kann, lässt sich verlustfrei als bipartiter Inzidenzgraph speichern, sodass gewöhnliche Graphenalgorithmen auf ihm laufen können.

Die Kooperationszeile verbirgt einen häufigen Modellierungsfehler. Analysten projizieren einen bipartiten Graphen oft auf eine Seite und verbinden zwei Autoren, sobald sie einen gemeinsamen Artikel haben. Die Projektion wirft Information weg. Drei Autoren, die einen Artikel gemeinsam geschrieben haben, und drei Autoren, die paarweise drei getrennte Artikel geschrieben haben, ergeben in der Projektion dasselbe Dreieck, obwohl die zugrunde liegenden Kooperationen völlig verschieden sind. Behalten Sie den bipartiten Graphen als maßgebliche Quelle und projizieren Sie nur für eine konkrete Frage.

11. Leicht zu testen, schwer zu reparieren

Bipartitheit liegt genau auf der Grenze zwischen leichten und schweren Problemen, und es lohnt sich, genau hinzusehen, wo die Linie verläuft.

• Zwei Farben: lineare Zeit. Abschnitt 5 erledigt das in O(V + E).
• Drei Farben: NP-vollständig. Zu entscheiden, ob sich ein Graph zulässig mit drei Farben färben lässt, ist eines der klassischen NP-vollständigen Probleme im Katalog von Garey und Johnson. Eine Farbe mehr macht aus einer Breitensuche ein Problem ohne bekannten Polynomialzeitalgorithmus, wie der Leitfaden zur Graphenfärbung erklärt.
• Einen nicht bipartiten Graphen reparieren: NP-schwer. Die wenigsten Kanten zu löschen, um einen Graphen bipartit zu machen, ist dasselbe, wie die meisten Kanten zu behalten, die eine Aufteilung der Knoten kreuzen, und das ist das Max-Cut-Problem, eines von Karps 21 NP-vollständigen Problemen von 1972. Auch das Löschen der wenigsten Knoten, das Odd-Cycle-Transversal-Problem, ist NP-schwer.

Der ungerade Kreis, den der Test liefert, ist also billig zu finden, sagt aber nichts über den billigsten Weg, alle ungeraden Kreise zu beseitigen. Im durchgehenden Beispiel mit der zusätzlichen Kante stellt das Löschen von C–E die Bipartitheit wieder her, aber in einem großen Graphen mit vielen ineinandergreifenden ungeraden Kreisen ist die minimale Reparatur wirklich schwer zu berechnen.

12. Häufige Fehler

13. Glossar

15. Quellen

Die Definitionen, Sätze und Zuschreibungen oben stammen aus diesen Quellen, in chronologischer Reihenfolge.

1. Mantel, W. (1907). "Problem 28." Wiskundige Opgaven 10, 60 bis 61. Die ⌊n²/4⌋-Schranke für dreiecksfreie Graphen.
2. Kőnig, D. (1916). "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre." Mathematische Annalen 77(4), 453 bis 465. Der Kantenfärbungssatz für bipartite Graphen und perfekte Matchings in regulären bipartiten Graphen.
3. Kuratowski, K. (1930). "Sur le problème des courbes gauches en topologie." Fundamenta Mathematicae 15, 271 bis 283. Planarität und die verbotenen Graphen K5 und K3,3.
4. Egerváry, J. (1931). "Matrixok kombinatorius tulajdonságairól." Matematikai és Fizikai Lapok 38, 16 bis 28.
5. Kőnig, D. (1931). "Gráfok és mátrixok." Matematikai és Fizikai Lapok 38, 116 bis 119. Mit Egerváry die Gleichheit von größten Matchings und kleinsten Knotenüberdeckungen.
6. Hall, P. (1935). "On Representatives of Subsets." Journal of the London Mathematical Society 10(1), 26 bis 30.
7. Kőnig, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaft. Das erste Lehrbuch der Graphentheorie, mit der Charakterisierung über ungerade Kreise.
8. Coulson, C. A. und Rushbrooke, G. S. (1940). "Note on the Method of Molecular Orbitals." Proceedings of the Cambridge Philosophical Society 36(2), 193 bis 200. Der Paarungssatz für alternierende Kohlenwasserstoffe.
9. Kuhn, H. W. (1955). "The Hungarian Method for the Assignment Problem." Naval Research Logistics Quarterly 2, 83 bis 97.
10. Berge, C. (1957). "Two Theorems in Graph Theory." Proceedings of the National Academy of Sciences 43(9), 842 bis 844. Augmentierende Wege charakterisieren größte Matchings.
11. Gale, D. und Shapley, L. S. (1962). "College Admissions and the Stability of Marriage." American Mathematical Monthly 69(1), 9 bis 15.
12. Vizing, V. G. (1964). "On an Estimate of the Chromatic Class of a p-Graph." Diskretnyi Analiz 3, 25 bis 30.
13. Karp, R. M. (1972). "Reducibility Among Combinatorial Problems." In Complexity of Computer Computations, 85 bis 103. New York: Plenum. Max-Cut unter den 21 NP-vollständigen Problemen.
14. Hopcroft, J. E. und Karp, R. M. (1973). "An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs." SIAM Journal on Computing 2(4), 225 bis 231.
15. Garey, M. R. und Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman. Die 3-Färbbarkeit von Graphen als NP-vollständiges Problem.
16. Cvetković, D. M., Doob, M. und Sachs, H. (1980). Spectra of Graphs: Theory and Application. New York: Academic Press. Symmetrische Spektren charakterisieren bipartite Graphen.
17. Tanner, R. M. (1981). "A Recursive Approach to Low Complexity Codes." IEEE Transactions on Information Theory 27(5), 533 bis 547.
18. Asratian, A. S., Denley, T. M. J. und Häggkvist, R. (1998). Bipartite Graphs and Their Applications. Cambridge Tracts in Mathematics 131. Cambridge: Cambridge University Press. Quelle für die Zuschreibung des Satzes über ungerade Kreise an die Arbeit von 1916.
19. Diestel, R. (2017). Graph Theory, 5. Auflage. Graduate Texts in Mathematics 173. Berlin: Springer.