Minimaler Schnitt

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Was ein Schnitt ist

Ein Schnitt zerlegt die Knoten eines Graphen in zwei nichtleere Gruppen, S und den Rest, V \ S. Die Kanten mit je einem Ende in jeder Gruppe kreuzen den Schnitt, und ihr Entfernen trennt die beiden Gruppen voneinander. In einem gewichteten Graphen ist das Gewicht eines Schnitts, auch seine Kapazität genannt, das Gesamtgewicht der kreuzenden Kanten; in einem ungewichteten Graphen ist es einfach ihre Anzahl. Ein minimaler Schnitt ist ein Schnitt mit kleinstem Gewicht: die billigste Art, den Graphen in zwei Teile zu zerlegen.

Das durchgehende Beispiel ist ein kleines Computernetz aus 8 Routern mit 15 Verbindungen. Jedes Gewicht ist die Kapazität einer Verbindung in Gigabit pro Sekunde. Die Router A bis D stehen in einem Gebäude, E bis H in einem anderen:

Gebäude 1:   A-B 4   A-C 3   A-D 2   B-C 2   B-D 3   C-D 3
Gebäude 2:   E-F 3   E-G 2   E-H 3   F-G 4   F-H 2   G-H 3
dazwischen:  C-E 2   D-F 1   B-G 1

8 Router, 15 Verbindungen, Gesamtkapazität 38

Das Durchtrennen der drei Verbindungen zwischen den Gebäuden, C-E, D-F und B-G, kostet 2 + 1 + 1 = 4 und zerlegt das Netz in zwei Teile. Das ist der minimale Schnitt, und er ist der einzige Schnitt mit Gewicht 4. Er ist zugleich die Schwachstelle des Netzes: Mehr als 4 Gigabit pro Sekunde können die beiden Gebäude nicht austauschen, wie auch immer der Rest des Netzes konfiguriert ist. Der nächstbilligste Schnitt isoliert den Router H, zu Kosten von 8, der Summe seiner eigenen Verbindungen.

2. Zwei Probleme mit demselben Namen

„Minimaler Schnitt“ bezeichnet zwei verwandte Probleme, und die meiste Verwirrung um das Thema entsteht, wenn man sie verwechselt:

• Minimaler s-t-Schnitt. Zwei Knoten sind gegeben, eine Quelle s und eine Senke t, und der Schnitt muss sie trennen: s in S, t außerhalb. Das ist der Schnitt im Max-Flow-Min-Cut-Theorem aus Abschnitt 4. Im Beispiel ist der minimale Schnitt, der A von H trennt, der Gebäudeschnitt mit Gewicht 4, aber der minimale Schnitt, der A von B trennt, hat Gewicht 9: Da beide im selben Gebäude liegen, ist es am billigsten, A allein abzutrennen.
• Globaler minimaler Schnitt. Es sind keine Knoten vorgegeben; der Schnitt darf zwei beliebige Gruppen trennen. Sein Gewicht ist das kleinste aller minimalen s-t-Schnitte, und in einem ungewichteten Graphen ist es gleich dem Kantenzusammenhang λ(G), der kleinsten Anzahl von Kanten, deren Entfernen den Graphen unzusammenhängend macht. Die Abschnitte 5 bis 7 berechnen ihn.

Eine einfache Schranke verbindet beide Ideen. Einen einzelnen Knoten abzutrennen kostet die Summe seiner Verbindungsgewichte, seinen gewichteten Grad, also kann der globale minimale Schnitt nie größer sein als der kleinste Grad. Hassler Whitney bewies 1932 die ungewichtete Version: Knotenzusammenhang ≤ Kantenzusammenhang ≤ Minimalgrad. Im Beispiel ist der kleinste gewichtete Grad 8, bei H, und der minimale Schnitt von 4 liegt deutlich darunter: Die Schwachstelle ist ein Bündel von Verbindungen zwischen zwei Gruppen, nicht ein einzelner schlecht angebundener Router. Ohne die Gewichte ist die Schranke hier scharf: Jeder Router hat mindestens 3 Verbindungen, und 3 Verbindungen sind die wenigsten, die das Netz trennen.

3. Warum das Durchprobieren aller Schnitte nicht skaliert

Ein Graph mit n Knoten hat 2n-1 - 1 Schnitte: Jeder Knoten außer einem festen ersten kommt auf eine der beiden Seiten, und die Aufteilung, bei der alles auf einer Seite liegt, ist kein Schnitt. Das Beispiel hat 27 - 1 = 127, wenig genug, um sie aufzulisten.

from itertools import combinations

LINKS = [('A', 'B', 4), ('A', 'C', 3), ('A', 'D', 2), ('B', 'C', 2), ('B', 'D', 3), ('C', 'D', 3),
         ('E', 'F', 3), ('E', 'G', 2), ('E', 'H', 3), ('F', 'G', 4), ('F', 'H', 2), ('G', 'H', 3),
         ('C', 'E', 2), ('D', 'F', 1), ('B', 'G', 1)]

def cut_weight(side, links):
    """Gesamtgewicht der Verbindungen mit genau einem Ende in side."""
    return sum(w for u, v, w in links if (u in side) != (v in side))

def all_cuts(links):
    """Jede Aufteilung der Knoten in zwei nichtleere Seiten, jede einmal gezählt."""
    vertices = sorted({x for u, v, _ in links for x in (u, v)})
    first, rest = vertices[0], vertices[1:]
    for r in range(len(rest)):                 # side enthält immer den ersten Knoten
        for others in combinations(rest, r):
            side = {first, *others}
            yield cut_weight(side, links), ''.join(sorted(side))

cuts = sorted(all_cuts(LINKS))
print(len(cuts), 'cuts')
# 127 cuts
for weight, side in cuts[:4]:
    print(weight, side)
# 4 ABCD
# 8 ABCDEFG
# 9 A
# 9 ABCEFGH

Die Anzahl verdoppelt sich mit jedem Knoten: 50 Knoten ergeben bereits mehr als 560 Billionen Schnitte. Der Rest dieses Leitfadens handelt von Algorithmen, die das Minimum finden, ohne sich die meisten davon anzusehen. Der Leitfaden zur Komplexität von Graphalgorithmen erklärt, warum ein solches exponentielles Wachstum eine Brute-Force-Suche ausschließt.

4. Minimale s-t-Schnitte aus dem maximalen Fluss

Das Max-Flow-Min-Cut-Theorem, das Lester Ford und Delbert Fulkerson 1954 in einem RAND-Bericht formulierten und 1956 veröffentlichten, im selben Jahr, in dem Peter Elias, Amiel Feinstein und Claude Shannon einen anderen Beweis gaben, besagt, dass der größte Fluss, der von s nach t geschickt werden kann, gleich dem Gewicht des kleinsten Schnitts ist, der sie trennt. Eine Richtung ist einfach: Jede Flusseinheit muss jeden s-t-Schnitt kreuzen, also kann kein Fluss irgendeinen Schnitt übersteigen. Der Gehalt des Theorems ist, dass sich beide immer treffen. Der Leitfaden zu Netzwerkflüssen und dem Max-Flow-Min-Cut-Theorem beweist es mit erweiternden Pfaden.

Die Frage hatte einen militärischen Ursprung. 1955 modellierten T. E. Harris und F. S. Ross von der RAND Corporation die Eisenbahnen der westlichen Sowjetunion und Osteuropas als Netz mit 44 Knoten und 105 Kanten, um die billigste Menge zu unterbrechender Strecken zu finden. Sie interessierten sich mehr für den Schnitt als für den Fluss: Ihr Bericht markiert einen minimalen Schnitt von 163.000 Tonnen als „den Engpass“. Er wurde erst 1999 freigegeben.

Für die Berechnung von Schnitten kommt es darauf an, wie sich der Schnitt aus einem maximalen Fluss ergibt. Wenn kein erweiternder Pfad von s nach t mehr übrig ist, sammeln Sie jeden Knoten, den s über Kanten mit freier Kapazität noch erreichen kann, also im Restgraphen. Diese Menge ist die Seite S eines minimalen Schnitts, und die vollen Kanten, die sie verlassen, bilden den Schnitt. Das folgende Programm führt den Edmonds-Karp-Algorithmus aus, der immer entlang eines kürzesten Pfades erweitert, und liest dann den Schnitt ab. Jede ungerichtete Verbindung kann Fluss in beide Richtungen tragen.

from collections import deque

LINKS = [('A', 'B', 4), ('A', 'C', 3), ('A', 'D', 2), ('B', 'C', 2), ('B', 'D', 3), ('C', 'D', 3),
         ('E', 'F', 3), ('E', 'G', 2), ('E', 'H', 3), ('F', 'G', 4), ('F', 'H', 2), ('G', 'H', 3),
         ('C', 'E', 2), ('D', 'F', 1), ('B', 'G', 1)]

def min_st_cut(links, s, t):
    """Maximaler Fluss nach Edmonds-Karp, dann der minimale s-t-Schnitt, abgelesen am Restgraphen."""
    cap = {}
    for u, v, w in links:                      # eine ungerichtete Verbindung trägt Fluss in beide Richtungen
        cap.setdefault(u, {})[v] = cap.get(u, {}).get(v, 0) + w
        cap.setdefault(v, {})[u] = cap.get(v, {}).get(u, 0) + w
    flow = 0
    while True:
        parent, queue = {s: None}, deque([s])
        while queue and t not in parent:       # kürzester erweiternder Pfad per Breitensuche
            u = queue.popleft()
            for v, c in cap[u].items():
                if c > 0 and v not in parent:
                    parent[v] = u
                    queue.append(v)
        if t not in parent:
            break
        path, v = [], t
        while parent[v] is not None:
            path.append((parent[v], v))
            v = parent[v]
        push = min(cap[u][v] for u, v in path)
        for u, v in path:                      # Kapazität verbrauchen, Gegenrichtung öffnen
            cap[u][v] -= push
            cap[v][u] += push
        flow += push
    side = set(parent)                         # im Restgraphen noch von s aus erreichbar
    cut = [(u, v, w) for u, v, w in links if (u in side) != (v in side)]
    return flow, ''.join(sorted(side)), cut

print(min_st_cut(LINKS, 'A', 'H'))
# (4, 'ABCD', [('C', 'E', 2), ('D', 'F', 1), ('B', 'G', 1)])
print(min_st_cut(LINKS, 'A', 'B'))
# (9, 'A', [('A', 'B', 4), ('A', 'C', 3), ('A', 'D', 2)])

Von A nach H beträgt der maximale Fluss 4, und er lässt sich in drei Pfade mit 2, 1 und 1 Einheiten aufteilen. Danach sind die drei Verbindungen zwischen den Gebäuden voll, A erreicht noch B, C und D und nichts darüber hinaus, und der Schnitt ist genau der Gebäudeschnitt. Von A nach B beträgt der Fluss 9, und der Schnitt isoliert A. Edmonds-Karp benötigt O(V E2) Zeit; es gibt schnellere Flussalgorithmen, aber jeder korrekte liefert auf diese Weise einen minimalen s-t-Schnitt.

Für ungewichtete Graphen hat das Theorem eine berühmte kombinatorische Form, meist nach Karl Menger benannt, dessen Satz von 1927 die Version für Knoten ist: Die größte Anzahl von Pfaden ohne gemeinsame Kante von u nach v ist gleich der kleinsten Anzahl von Kanten, deren Entfernen u von v trennt. Diese Kantenform des Satzes von Menger folgt aus dem Max-Flow-Min-Cut-Theorem. Im Beispiel gibt es, ohne Gewichte, drei kantendisjunkte Pfade von A nach H und drei Verbindungen zwischen den Gebäuden.

5. Globale minimale Schnitte mit maximalen Flüssen

Ein globaler minimaler Schnitt trennt irgendein Paar von Knoten, also ist er der kleinste s-t-Schnitt über alle Paare. Weniger Paare genügen. Legen Sie einen beliebigen Knoten s fest: Wie auch immer der minimale Schnitt aussieht, irgendein Knoten t liegt auf seiner anderen Seite, also wird er vom Minimum über die n - 1 Möglichkeiten für t gefunden. Legt man im Beispiel s = A fest, so liefern die vier Läufe mit t im anderen Gebäude alle 4.

Ralph Gomory und T. C. Hu zeigten 1961, dass n - 1 maximale Flüsse viel mehr verraten: Sie bauen einen Baum auf denselben Knoten, heute als Gomory-Hu-Baum bezeichnet, in dem der minimale Schnitt zwischen zwei beliebigen Knoten gleich dem kleinsten Kantengewicht auf dem Baumpfad zwischen ihnen ist. Für das Beispiel tragen die sieben Kanten des Baums die Werte 4, 8, 9, 9, 10, 10 und 10, sodass sich der Wert jedes der 28 paarweisen minimalen Schnitte daran ablesen lässt, und die kleinste Kante, 4, ist der globale minimale Schnitt.

Flussbasierte Methoden funktionieren auch für gerichtete Graphen, und sie sind das richtige Werkzeug, wenn es auf den minimalen Schnitt zwischen bestimmten Knoten ankommt. Für den globalen minimalen Schnitt eines ungerichteten Graphen sind die nächsten beiden Algorithmen einfacher und schneller.

6. Der Stoer-Wagner-Algorithmus

1997 veröffentlichten Mechthild Stoer und Frank Wagner einen Algorithmus, der den globalen minimalen Schnitt eines ungerichteten Graphen mit nichtnegativen Gewichten ganz ohne Flüsse findet, aufbauend auf früheren Arbeiten von Hiroshi Nagamochi und Toshihide Ibaraki. Er läuft in n - 1 Phasen. Jede Phase tut drei Dinge:

1. Beginnen Sie bei einem beliebigen Knoten und fügen Sie die Knoten einzeln hinzu, wobei Sie immer den wählen, der am stärksten mit den bereits hinzugefügten verbunden ist: den mit dem größten Gesamtgewicht der Verbindungen in die wachsende Menge. Diese Reihenfolge heißt Maximum-Adjacency-Suche.
2. Wenn der letzte Knoten t hinzugefügt wird, ist das Gewicht seiner Verbindungen zu allem anderen der Schnitt der Phase. Ein kurzes Argument zeigt, dass er ein minimaler Schnitt ist, der t von s trennt, also von dem unmittelbar vor t hinzugefügten Knoten.
3. Verschmelzen Sie s und t zu einem Knoten, addieren Sie dabei die Gewichte paralleler Verbindungen, und beginnen Sie die nächste Phase auf dem kleineren Graphen.

Entweder trennt der globale minimale Schnitt s von t, und dann hat diese Phase ihn gefunden, oder er hält beide auf derselben Seite, und dann geht durch das Verschmelzen nichts verloren. Nach n - 1 Phasen ist der kleinste Schnitt der Phase die Antwort.

LINKS = [('A', 'B', 4), ('A', 'C', 3), ('A', 'D', 2), ('B', 'C', 2), ('B', 'D', 3), ('C', 'D', 3),
         ('E', 'F', 3), ('E', 'G', 2), ('E', 'H', 3), ('F', 'G', 4), ('F', 'H', 2), ('G', 'H', 3),
         ('C', 'E', 2), ('D', 'F', 1), ('B', 'G', 1)]

def stoer_wagner(links):
    """Globaler minimaler Schnitt: n - 1 Phasen, jede endet mit einem Schnitt der Phase und einer Verschmelzung."""
    w = {}
    for u, v, c in links:
        w.setdefault(u, {})[v] = w.get(u, {}).get(v, 0) + c
        w.setdefault(v, {})[u] = w.get(v, {}).get(u, 0) + c
    groups = {v: v for v in w}                 # verschmolzene Knoten merken sich, was sie enthalten
    best, phase = (float('inf'), ''), 0
    while len(w) > 1:
        phase += 1
        start = min(w)
        order, attached = [start], {v: w[start].get(v, 0) for v in w if v != start}
        while attached:                        # als Nächstes den am stärksten verbundenen Knoten hinzufügen
            v = max(sorted(attached), key=attached.get)
            phase_cut = attached.pop(v)
            order.append(v)
            for x, c in w[v].items():
                if x in attached:
                    attached[x] += c
        s, t = order[-2], order[-1]
        side = ''.join(sorted(groups[t]))
        print(f'phase {phase}: cut of the phase {phase_cut:2}, side {side}')
        best = min(best, (phase_cut, side))
        for x, c in w.pop(t).items():          # t mit s verschmelzen
            if x != s:
                w[s][x] = w[s].get(x, 0) + c
                w[x][s] = w[x].get(s, 0) + c
            del w[x][t]
        groups[s] += groups.pop(t)
    return best

print(stoer_wagner(LINKS))
# phase 1: cut of the phase  8, side H
# phase 2: cut of the phase 10, side F
# phase 3: cut of the phase 10, side FGH
# phase 4: cut of the phase  4, side EFGH
# phase 5: cut of the phase 10, side C
# phase 6: cut of the phase 10, side B
# phase 7: cut of the phase  9, side BCDEFGH
# (4, 'EFGH')

Im Beispiel endet die erste Phase bei H mit einem Schnitt von 8, den Kosten, H zu isolieren. Während die Phasen Knoten verschmelzen, wachsen die Gruppen: In Phase 4 ist der zuletzt hinzugefügte Knoten die verschmolzene Gruppe E, F, G, H, und ihr Schnitt der Phase ist der Gebäudeschnitt, 4. Die übrigen Phasen finden nur größere Schnitte. Mit einem Fibonacci-Heap für die Wahl des „am stärksten verbundenen“ Knotens benötigt jede Phase O(E + V log V) und der ganze Algorithmus O(V E + V2 log V); die einfache Version oben, die nach dem Maximum sucht, benötigt O(V3).

7. Kargers zufällige Kontraktion

David Kargers Algorithmus von 1993 ist einer der berühmtesten randomisierten Algorithmen. Er ist fast zu einfach, um zu funktionieren:

1. Wählen Sie zufällig eine Verbindung, mit einer Wahrscheinlichkeit proportional zu ihrem Gewicht, und kontrahieren Sie sie: Verschmelzen Sie ihre beiden Enden zu einem Knoten und verwerfen Sie die Verbindungen zwischen ihnen.
2. Wiederholen Sie das, bis nur noch zwei verschmolzene Knoten übrig sind.
3. Die Verbindungen zwischen diesen beiden Knoten bilden einen Schnitt. Geben Sie ihn aus.

Ein einzelner Lauf kann leicht scheitern: Kontrahiert er jemals eine Verbindung des minimalen Schnitts, ist dieser Schnitt verloren. Das Überraschende ist, dass er selten genug scheitert. Ein minimaler Schnitt ist leicht, also meiden zufällige Wahlen tendenziell seine Verbindungen, und Karger bewies, dass ein einzelner Lauf einen gegebenen minimalen Schnitt mit einer Wahrscheinlichkeit von mindestens 2 / (n (n - 1)) liefert. Wiederholt man den Lauf und behält den leichtesten Schnitt, sinkt die Fehlerwahrscheinlichkeit so schnell, wie man möchte.

import math, random

LINKS = [('A', 'B', 4), ('A', 'C', 3), ('A', 'D', 2), ('B', 'C', 2), ('B', 'D', 3), ('C', 'D', 3),
         ('E', 'F', 3), ('E', 'G', 2), ('E', 'H', 3), ('F', 'G', 4), ('F', 'H', 2), ('G', 'H', 3),
         ('C', 'E', 2), ('D', 'F', 1), ('B', 'G', 1)]

def contract(links, rnd):
    """Ein Lauf von Kargers Algorithmus: die Enden zufälliger Verbindungen verschmelzen, bis zwei Gruppen übrig sind."""
    group = {x: x for u, v, _ in links for x in (u, v)}
    def find(x):
        while group[x] != x:
            x = group[x]
        return x
    groups = len(group)
    while groups > 2:
        alive = [(u, v, w) for u, v, w in links if find(u) != find(v)]
        u, v, _ = rnd.choices(alive, weights=[w for *_, w in alive])[0]   # schwerere Verbindungen werden öfter verschmolzen
        group[find(u)] = find(v)
        groups -= 1
    side = ''.join(sorted(x for x in group if find(x) == find('A')))
    return sum(w for u, v, w in links if find(u) != find(v)), side

rnd = random.Random(2026)
runs = [contract(LINKS, rnd) for _ in range(10_000)]
hits = sum(weight == 4 for weight, _ in runs)
print(f'minimum cut found in {hits} of 10,000 runs')
print(f'guaranteed at least 2 / (n (n - 1)) = {2 / (8 * 7):.4f} per run')
best_of_10 = [min(runs[i:i + 10]) for i in range(0, 10_000, 10)]
print(f'best of 10 runs is the minimum cut {sum(c[0] == 4 for c in best_of_10)} times out of 1,000')
print(f'runs needed for 99% with only the guarantee: {math.ceil(math.log(100) / -math.log(1 - 2 / 56))}')
# minimum cut found in 3228 of 10,000 runs
# guaranteed at least 2 / (n (n - 1)) = 0.0357 per run
# best of 10 runs is the minimum cut 978 times out of 1,000
# runs needed for 99% with only the guarantee: 127

In 10.000 Läufen am Beispiel kam der minimale Schnitt 3.228-mal heraus, etwa 32 %, das Neunfache der garantierten 3,6 %. Der beste von je 10 Läufen fand ihn in 978 von 1.000 Versuchen. Die Garantie beschreibt den schlechtesten Fall: Allein auf sie gestützt bräuchte man bei 8 Knoten 127 Läufe für 99 % Sicherheit. Kargers Schranke hat auch eine bemerkenswerte Folge. Jeder minimale Schnitt wird mit einer Wahrscheinlichkeit von mindestens 2 / (n (n - 1)) gefunden, und diese Ereignisse können nicht gleichzeitig eintreten, also kann ein Graph höchstens n (n - 1) / 2 minimale Schnitte haben. Ein Kreis auf n Knoten hat genau so viele: Das Entfernen zweier beliebiger seiner Kanten ist ein minimaler Schnitt.

David Karger und Clifford Stein verbesserten die Methode 1996, indem sie nur teilweise kontrahierten und dann auf zwei Kopien rekursiv weitermachten, was mit hoher Wahrscheinlichkeit einen minimalen Schnitt in O(n2 log3 n) Zeit findet. Karger gab später einen Algorithmus an, der in nahezu linearer Zeit in der Anzahl der Kanten läuft.

8. Welcher Algorithmus wann

In der Praxis: Für den Schnitt zwischen zwei gegebenen Knoten berechnen Sie einen maximalen Fluss. Für den globalen minimalen Schnitt eines ungerichteten Graphen ist Stoer-Wagner die übliche deterministische Wahl und das, was Bibliotheken wie NetworkX implementieren. Zu Kargers Algorithmus greift man, wenn der Graph groß ist, wenn sich die Berechnung auf viele Maschinen verteilen lässt oder wenn man jeden minimalen Schnitt braucht statt nur einen.

9. Gerichtete Graphen und Knotenschnitte

In einem gerichteten Graphen zählt ein Schnitt (S, V \ S) nur die Bögen, die von S zur anderen Seite führen; zurücklaufende Bögen helfen nicht beim Trennen. Stoer-Wagner und Kargers Algorithmus beruhen auf Symmetrie und sind hier nicht anwendbar. Der globale minimale Schnitt lässt sich weiterhin mit maximalen Flüssen finden, von einem festen Knoten zu jedem anderen und zurück, und Jianxiu Hao und James Orlin zeigten 1994, wie das in etwa der Zeit einer einzigen Flussberechnung geht.

Manchmal lautet die Frage, welche Knoten statt welcher Kanten zu entfernen sind: die Router, deren Ausfall das Netz spalten würde. Die kleinste solche Menge ergibt den Knotenzusammenhang, und ein Standardtrick führt ihn auf Kantenschnitte zurück, indem jeder Knoten in eine Eingangs- und eine Ausgangskopie aufgeteilt wird, die durch eine Kante der Kapazität 1 verbunden sind. Ein einzelner Knoten, dessen Entfernen den Graphen unzusammenhängend macht, ist ein Artikulationspunkt, und eine einzelne Kante mit dieser Wirkung ist eine Brücke. Beide lassen sich ohne Flüsse in linearer Zeit finden, wie der Leitfaden zu Zusammenhangskomponenten, Brücken und Artikulationspunkten erklärt.

10. Wo minimale Schnitte eingesetzt werden

• Netzzuverlässigkeit. Der globale minimale Schnitt eines Kommunikations- oder Stromnetzes ist seine Schwachstelle: die wenigsten Verbindungen oder die geringste Kapazität, deren Ausfall es spaltet. Der minimale s-t-Schnitt ist der Engpass zwischen zwei Standorten, wie im Beispiel.
• Bildsegmentierung. Machen Sie jedes Pixel zu einem Knoten, der mit seinen Nachbarn verbunden ist, mit schweren Verbindungen zwischen ähnlichen Pixeln, und fügen Sie eine Quelle für „Objekt“ und eine Senke für „Hintergrund“ hinzu. Ein minimaler s-t-Schnitt trennt das Objekt vom Hintergrund entlang der Grenze, die die schwächsten Verbindungen durchschneidet. D. M. Greig, B. T. Porteous und A. H. Seheult setzten minimale Schnitte 1989 erstmals in der Bildanalyse ein, um verrauschte Binärbilder zu restaurieren, Zhenyu Wu und Richard Leahy wandten sie 1993 auf die Segmentierung an, und Yuri Boykovs interaktive Graph Cuts machten die Methode zu einem Standardwerkzeug des maschinellen Sehens.
• Clustering. Ein minimaler Schnitt zerlegt einen Ähnlichkeitsgraphen an seiner schwächsten Stelle. Für sich allein neigt er dazu, einige wenige lose angebundene Punkte abzutrennen, weshalb Jianbo Shi und Jitendra Malik den normalisierten Schnitt einführten, der das Schnittgewicht durch die Größe jeder Seite teilt.
• Projektauswahl. Projekte auszuwählen, die Geld einbringen, aber kostspielige Voraussetzungen erfordern, ist ein verkapptes Problem des minimalen Schnitts: Profitable Projekte hängen an der Quelle, Kosten an der Senke, und Voraussetzungen werden zu Bögen mit unendlicher Kapazität. Der Leitfaden zur Investitionsplanung löst ein solches Portfolio auf diese Weise.
• Ausscheiden im Sport. Ob ein Team angesichts der verbleibenden Spiele noch Erster werden kann, ist eine Frage des maximalen Flusses, und der minimale Schnitt belegt ein „Nein“, wie Benjamin Schwartz 1966 für Baseball zeigte.

Das entgegengesetzte Problem, der maximale Schnitt, der die Aufteilung mit möglichst vielen kreuzenden Kanten sucht, sieht ähnlich aus, ist aber NP-schwer. Einen Schnitt zu minimieren ist leicht, weil es dual zu einem Fluss ist; das Maximieren hat keine solche Struktur.

11. Neuere Fortschritte

Bei minimalen Schnitten gab es einige der bemerkenswertesten jüngeren Fortschritte der Algorithmik. 2015 fanden Ken-ichi Kawarabayashi und Mikkel Thorup einen deterministischen Algorithmus für den globalen minimalen Schnitt eines einfachen ungewichteten Graphen, der in nahezu linearer Zeit läuft. 2021 erweiterte Jason Li deterministische fast lineare Laufzeit auf gewichtete Graphen. Und 2022 zeigten Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg und Sushant Sachdeva, dass der maximale Fluss mit ganzzahligen Kapazitäten, und mit ihm der minimale s-t-Schnitt, in fast linearer Zeit m1 + o(1) berechnet werden kann, ein Ergebnis, das auf der FOCS 2022 den Best Paper Award gewann. Diese Algorithmen sind noch nicht das, was praktische Software verwendet, aber sie klären, wie schnell sich die Probleme im Prinzip lösen lassen.

12. Häufige Fehler

13. Glossar

15. Quellen

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

1. Menger, K. (1927). "Zur allgemeinen Kurventheorie." Fundamenta Mathematicae 10, 96 bis 115.
2. Whitney, H. (1932). "Congruent Graphs and the Connectivity of Graphs." American Journal of Mathematics 54(1), 150 bis 168.
3. Harris, T. E. und Ross, F. S. (1955). Fundamentals of a Method for Evaluating Rail Net Capacities. Research Memorandum RM-1573. Santa Monica: RAND Corporation.
4. Elias, P., Feinstein, A. und Shannon, C. E. (1956). "A Note on the Maximum Flow Through a Network." IRE Transactions on Information Theory 2(4), 117 bis 119.
5. Ford, L. R. und Fulkerson, D. R. (1956). "Maximal Flow Through a Network." Canadian Journal of Mathematics 8, 399 bis 404.
6. Gomory, R. E. und Hu, T. C. (1961). "Multi-Terminal Network Flows." Journal of the Society for Industrial and Applied Mathematics 9(4), 551 bis 570.
7. Schwartz, B. L. (1966). "Possible Winners in Partially Completed Tournaments." SIAM Review 8(3), 302 bis 308.
8. Edmonds, J. und Karp, R. M. (1972). "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems." Journal of the ACM 19(2), 248 bis 264.
9. Greig, D. M., Porteous, B. T. und Seheult, A. H. (1989). "Exact Maximum A Posteriori Estimation for Binary Images." Journal of the Royal Statistical Society, Series B 51(2), 271 bis 279.
10. Nagamochi, H. und Ibaraki, T. (1992). "Computing Edge-Connectivity in Multigraphs and Capacitated Graphs." SIAM Journal on Discrete Mathematics 5(1), 54 bis 66.
11. Karger, D. R. (1993). "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-cut Algorithm." In Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms, 21 bis 30.
12. Wu, Z. und Leahy, R. (1993). "An Optimal Graph Theoretic Approach to Data Clustering: Theory and Its Application to Image Segmentation." IEEE Transactions on Pattern Analysis and Machine Intelligence 15(11), 1101 bis 1113.
13. Hao, J. und Orlin, J. B. (1994). "A Faster Algorithm for Finding the Minimum Cut in a Directed Graph." Journal of Algorithms 17(3), 424 bis 446.
14. Karger, D. R. und Stein, C. (1996). "A New Approach to the Minimum Cut Problem." Journal of the ACM 43(4), 601 bis 640.
15. Stoer, M. und Wagner, F. (1997). "A Simple Min-Cut Algorithm." Journal of the ACM 44(4), 585 bis 591.
16. Karger, D. R. (2000). "Minimum Cuts in Near-Linear Time." Journal of the ACM 47(1), 46 bis 76.
17. Shi, J. und Malik, J. (2000). "Normalized Cuts and Image Segmentation." IEEE Transactions on Pattern Analysis and Machine Intelligence 22(8), 888 bis 905.
18. Boykov, Y. und Jolly, M.-P. (2001). "Interactive Graph Cuts for Optimal Boundary and Region Segmentation of Objects in N-D Images." In Proceedings of the 8th IEEE International Conference on Computer Vision, 105 bis 112.
19. Schrijver, A. (2002). "On the History of the Transportation and Maximum Flow Problems." Mathematical Programming 91(3), 437 bis 445.
20. Kawarabayashi, K. und Thorup, M. (2015). "Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time." In Proceedings of the 47th ACM Symposium on Theory of Computing, 665 bis 674.
21. Li, J. (2021). "Deterministic Mincut in Almost-Linear Time." In Proceedings of the 53rd ACM Symposium on Theory of Computing, 384 bis 395.
22. Chen, L., Kyng, R., Liu, Y. P., Peng, R., Probst Gutenberg, M. und Sachdeva, S. (2022). "Maximum Flow and Minimum-Cost Flow in Almost-Linear Time." In Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science, 612 bis 623.