Max-Flow- und Min-Cut-Interviewfragen

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Was eine Max-Flow-Frage wirklich prüft

Niemand soll Dinics Algorithmus aus dem Gedächtnis implementieren. Flussfragen sind Modellierungsfragen: Der Interviewer beschreibt eine Situation in einfacher Sprache, und die ganze Übung besteht darin, zu bemerken, dass es ein Netzwerk ist, das richtige zu zeichnen und den Satz zu nennen, der die Sache erledigt.

Deshalb gelten diese Fragen als unfair. Ein Kandidat, der zwanzig Baumprobleme auswendig kennt, kann an „ordnen Sie diese fünf Ingenieure diesen fünf Teams zu“ scheitern, weil er nie den Sprung von einer Geschichte über Menschen zu einem Graphen mit Quelle und Senke macht. Der Algorithmus ist die leichte Hälfte und steht in jeder Bibliothek bereit.

Vier Formulierungen decken fast alles ab, was Ihnen vorgelegt wird.

Alles Folgende wird auf diesem einen Netzwerk mit sechs Knoten oder einer kleinen Variante davon durchgerechnet, und jede Zahl wurde berechnet und mit einer zweiten Methode nachgerechnet, bevor sie gedruckt wurde.

2. Die Vorlage und die zwei Methoden, auf die es ankommt

Schreiben Sie Dinic einmal und behalten Sie ihn. Er umfasst etwa dreißig Zeilen, ist schnell genug für alles, was ein Interview hervorbringt, und liefert den minimalen Schnitt gratis dazu.

from collections import deque

class Dinic:
    def __init__(self, n):
        self.n = n
        self.to, self.cap, self.adj = [], [], [[] for _ in range(n)]

    def add(self, u, v, c):
        self.adj[u].append(len(self.to)); self.to.append(v); self.cap.append(c)
        self.adj[v].append(len(self.to)); self.to.append(u); self.cap.append(0)

    def bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for e in self.adj[u]:
                if self.cap[e] > 0 and self.level[self.to[e]] < 0:
                    self.level[self.to[e]] = self.level[u] + 1
                    q.append(self.to[e])
        return self.level[t] >= 0

    def dfs(self, u, t, f):
        if u == t:
            return f
        while self.it[u] < len(self.adj[u]):
            e = self.adj[u][self.it[u]]
            v = self.to[e]
            if self.cap[e] > 0 and self.level[v] == self.level[u] + 1:
                d = self.dfs(v, t, min(f, self.cap[e]))
                if d > 0:
                    self.cap[e] -= d
                    self.cap[e ^ 1] += d
                    return d
            self.it[u] += 1
        return 0

    def max_flow(self, s, t):
        flow = 0
        while self.bfs(s, t):
            self.it = [0] * self.n
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f
        return flow

Zwei Details darin sollten Sie erklären können, denn genau die fragt ein guter Interviewer ab.

Das erste sind die gepaarten Kanten. Jede Vorwärtskante wird direkt neben ihrer Rückwärtskante gespeichert, sodass e ^ 1 zwischen beiden wechselt. Die Rückwärtskante beginnt mit Kapazität null und wächst, wenn Fluss geschoben wird. Sie existiert, damit der Algorithmus eine schlechte Entscheidung rückgängig machen kann: Fluss rückwärts entlang dieser Kante zu schicken, hebt Fluss auf, der vorwärts geschickt wurde. Ohne sie kann der gierig gewählte erste Pfad Sie unterhalb des Optimums festhalten, und das ist das Häufigste, was Kandidaten nicht erklären können.

Das zweite ist self.it, die Current-Arc-Optimierung. Ist eine Kante in dieser Phase erschöpft, wird sie nie wieder geprüft, und genau das bringt Dinic von quadratisch auf seine angegebene Schranke. Wer diese eine Zeile löscht, bekommt weiterhin korrekte Antworten und zerstört die Komplexität.

Führen Sie ihn auf dem Netzwerk der Abbildung aus, und die Antwort ist 16. Edmonds-Karp liefert auf demselben Netzwerk ebenfalls 16, und das ist die billigste verfügbare Plausibilitätsprüfung: zwei verschiedene Algorithmen, eine Antwort.

3. Maximales bipartites Matching

Das ist die Frage, die Ihnen am wahrscheinlichsten gestellt wird, meist als Planungsproblem verkleidet. „Fünf Ingenieure, fünf Teams, jeder Ingenieur kann in einigen davon arbeiten, maximieren Sie die Zahl der untergebrachten Personen.“

Die Reduktion ist mechanisch. Fügen Sie eine Quelle mit einer Kante der Kapazität 1 zu jedem Ingenieur hinzu, eine Senke mit einer Kante der Kapazität 1 aus jedem Team und Kanten der Kapazität 1 für jede erlaubte Zuordnung. Da die Kapazitäten ganzzahlig sind, liefert Max Flow eine ganzzahlige Lösung, und ein ganzzahliger Fluss vom Wert k ist genau ein Matching der Größe k: Kapazität 1 aus der Quelle verhindert, dass jemand zweimal verwendet wird.

def max_matching(left, right, can):
    n = len(left) + len(right) + 2
    s, t = 0, n - 1
    g = Dinic(n)
    for i in range(len(left)):
        g.add(s, 1 + i, 1)
    for j in range(len(right)):
        g.add(1 + len(left) + j, t, 1)
    for i, l in enumerate(left):
        for r in can[l]:
            g.add(1 + i, 1 + len(left) + right.index(r), 1)
    return g.max_flow(s, t)

Auf der Instanz der Abbildung ist die Antwort 4, nicht 5. Ada, Ben, Cleo und Dan erreichen zusammen nur backend, data und infra, also müssen drei Rollen vier Personen aufnehmen, und eine davon bleibt ohne Platz. Das ist Halls Bedingung, die verletzt ist, und sie zu benennen, ist mehr wert als der Code: Ein Matching, das jeden linken Knoten unterbringt, existiert genau dann, wenn jede Teilmenge der linken Seite mindestens so viele Nachbarn hat, wie sie Mitglieder hat. Der knappste Zeuge ist hier noch kleiner: Ada, Cleo und Dan erreichen zusammen nur backend und data, drei Personen für zwei Rollen. Halls Bedingung betrifft das Sättigen einer Seite und fällt nur dann mit einem perfekten Matching zusammen, wenn beide Seiten gleich groß sind, wie es hier zufällig der Fall ist.

Sucht der Interviewer die schnellstmögliche Antwort statt der am besten wiederverwendbaren, läuft Hopcroft-Karp in O(E√V), indem entlang vieler kürzester Pfade gleichzeitig augmentiert wird. Sagen Sie, dass es ihn gibt, und verwenden Sie dann Dinic, der auf Graphen mit Einheitskapazitäten ohnehin dieselbe Schranke erreicht.

4. Die Überdeckung, die im Matching steckt

Eine gute Nachfrage, an der die meisten Kandidaten scheitern: „Nennen Sie mir jetzt die kleinste Menge von Personen und Teams, die jede mögliche Zuordnung berührt.“

Das ist eine minimale Knotenüberdeckung, die in allgemeinen Graphen NP-schwer ist. In einem bipartiten Graphen ist sie das nicht, und der Satz von König besagt, dass sie genau so groß ist wie das maximale Matching. Sie brauchen keinen zweiten Algorithmus; Sie lesen die Überdeckung an dem Schnitt ab, den Sie schon haben. Führen Sie im Residualgraphen eine Suche von der Quelle aus und nehmen Sie die linken Knoten, die sie nicht erreicht, plus die rechten Knoten, die sie sehr wohl erreicht.

Auf dieser Instanz ergibt das Ben, Eve, backend und data, vier Knoten, und eine Prüfung von Hand bestätigt, dass alle neun Kanten berührt werden. Das Komplement einer Knotenüberdeckung ist eine unabhängige Menge, also ist die größte unabhängige Menge 10 − 4 = 6. Drei getrennte Fragen, ein Max-Flow-Aufruf.

5. Der minimale Schnitt: die Kanten, nicht nur die Zahl

„Welche Verbindungen muss man am billigsten kappen, damit kein Verkehr das Rechenzentrum erreicht?“ Der Wert ist nach dem Satz der maximale Fluss. Aber Interviewer fragen, welche Verbindungen, und das ist ein anderer, leichterer Schritt, den viele Kandidaten nie gelernt haben.

Ist der Fluss maximal, führen Sie eine Suche von der Quelle über Kanten aus, die noch Residualkapazität haben. Sei R die Menge, die sie erreicht. Der minimale Schnitt besteht aus jeder ursprünglichen Kante von R in ihr Komplement.

def min_cut(self, s):
    seen = [False] * self.n
    seen[s] = True
    q = deque([s])
    while q:
        u = q.popleft()
        for e in self.adj[u]:
            if self.cap[e] > 0 and not seen[self.to[e]]:
                seen[self.to[e]] = True
                q.append(self.to[e])
    return [(self.to[e ^ 1], self.to[e])
            for e in range(0, len(self.to), 2)
            if seen[self.to[e ^ 1]] and not seen[self.to[e]]]

Auf dem durchgerechneten Netzwerk ist die erreichbare Menge {S, A, B}, und der Schnitt ist A→C mit 7 plus B→D mit 9, zusammen 16, der Wert des Flusses. Brute Force über alle sechzehn möglichen Teilmengen auf der Quellseite bestätigt, dass es keinen billigeren Schnitt gibt.

Hier lauern zwei Fallen. Zählen Sie nur Kanten, die von der erreichbaren Menge zur nicht erreichbaren führen; Kanten, die zurückzeigen, gehören nicht zum Schnitt. Und der minimale Schnitt ist oft nicht eindeutig. Werden Sie also nach „dem“ Schnitt gefragt, sagen Sie, dass Sie einen von möglicherweise mehreren zurückgeben und dass alle denselben Wert haben.

6. Disjunkte Pfade und der Satz von Menger

„Wie viele unabhängige Routen gibt es vom Büro zum Rechenzentrum?“ ist eine Flussfrage, bei der jede Kapazität 1 ist.

Setzen Sie jede Kapazität auf 1, und der maximale Fluss zählt kantendisjunkte Pfade, weil eine Flusseinheit keine Kante mit einer anderen teilen kann. Der Satz von Menger besagt dann, dass diese Zahl gleich der minimalen Anzahl von Kanten ist, deren Entfernung die beiden Knoten trennt. Max-Flow-Min-Cut ist die gewichtete Verallgemeinerung genau dieser Aussage.

Auf dem durchgerechneten Netzwerk mit Einheitskapazitäten ist die Antwort 2, und ein minimaler Schnitt sind die zwei Kanten, die die Quelle verlassen, obwohl sechs verschiedene Kantenpaare das erreichen. Das sollte man ansprechen statt verstecken: Mit Einheitskapazitäten ist die Antwort oft nur eine Gradschranke, und das zu sagen, zeigt, dass Sie verstehen, was die Zahl bedeutet, und nicht nur, wie man sie berechnet.

Heißt es in der Frage stattdessen knotendisjunkt, lässt sich das mit Kapazitäten auf Kanten nicht ausdrücken, und Sie brauchen den ersten Modellierungstrick unten. Hier ergibt das ebenfalls 2, und wenn man C und D entfernt, ist T tatsächlich nicht mehr erreichbar. Eine Voraussetzung sollten Sie laut aussprechen: Die Knotenform des Satzes von Menger verlangt, dass die beiden Endpunkte nicht benachbart sind, und das sind sie hier nicht, weil es keine direkte Kante von S nach T gibt.

7. Drei Modellierungstricks, die aus einer Geschichte ein Netzwerk machen

Fast jede Flussfrage im Interview ist eine dieser Transformationen um denselben Löser herum.

Ein Knoten hat eine Kapazität. „Dieser Router schafft 3 Einheiten.“ Kapazitäten liegen auf Kanten, also teilen Sie den Knoten: Ersetzen Sie v durch v_ein und v_aus, verbunden durch eine Kante der Kapazität 3, leiten Sie jeden Bogen, der bei v ankam, nach v_ein um, und lassen Sie jeden Bogen, der v verlässt, bei v_aus beginnen. Die innere Kapazität auf 1 zu setzen, ist der Weg, knotendisjunkte Pfade zu zählen.

Viele Quellen, viele Senken. „Drei Lager beliefern zwei Läden.“ Fügen Sie eine Superquelle mit Kanten unendlicher Kapazität zu jeder echten Quelle hinzu und eine Supersenke, die von jeder echten Senke gespeist wird. Ein Löseraufruf ersetzt die Aufzählung, mit der ein Kandidat sonst beginnen würde.

Die Kante ist ungerichtet. Fügen Sie beide Richtungen mit voller Kapazität hinzu. Das sieht so aus, als erlaube es den doppelten Verkehr, tut es aber nicht, weil die Residualbuchführung in entgegengesetzte Richtungen geschickten Fluss aufhebt. Halten Sie diese Antwort bereit, denn der Einwand liegt nahe und die Antwort ist kurz.

Der vierte Fall ist der, an dem viele scheitern: eine untere Schranke. „Jeder Fahrer muss mindestens zwei Schichten übernehmen“ ist keine Kapazität, und der Standardlöser kann sie nicht ausdrücken. Sie braucht eine Konstruktion für eine zulässige Zirkulation, und der nützliche Zug im Interview ist, das Wort „muss“ laut zu bemerken, statt das Ganze zu programmieren.

8. Projektauswahl, oder warum ein Schnitt eine Teilmenge wählen kann

Diese Frage wirkt, als müsste sie dynamische Programmierung sein, und ist es nicht, weshalb sie so beliebt ist.

„Jedes Projekt bringt einen bekannten Gewinn. Jedes Projekt braucht bestimmte Maschinen. Jede Maschine kostet einen festen Betrag und wird von allem geteilt, was sie braucht. Wählen Sie die profitabelste Teilmenge.“

Die Falle ist Gier: jedes Projekt mit positivem Gewinn nehmen oder nach Gewinn pro Maschine sortieren. Beides ist falsch, weil Maschinen geteilt werden, sodass die echten Kosten eines Projekts davon abhängen, welche anderen Projekte Sie nehmen.

Die Konstruktion ist kurz. Quelle zu jedem Projekt mit Kapazität gleich seinem Gewinn; jede Maschine zur Senke mit Kapazität gleich ihren Kosten; Projekt zu Maschine mit unendlicher Kapazität, damit diese Kante nie geschnitten werden kann. Dann ist die Antwort

maximaler Gewinn = (Summe aller Gewinne) − (minimaler Schnitt)

, und die zu nehmenden Projekte sind die auf der Quellseite des Schnitts. Die unendlichen Kanten erzwingen die Konsistenz: Bleibt ein Projekt auf der Quellseite, müssen auch seine Maschinen dort sein, sonst wäre der Schnitt unendlich. Das ist die Definition einer abgeschlossenen Menge, und das hier ist das Problem des maximalen Abschlusses.

Auf der Instanz der Abbildung ergeben die Gewinne zusammen 235, der minimale Schnitt ist 195, und das Bestmögliche ist 40, indem man alpha, beta und gamma nimmt und delta weglässt. Delta bringt 30, ist aber das einzige Projekt, das fab braucht, und fab kostet 50. Es zu den drei anderen hinzuzufügen, kostet also 20 mehr, als es einbringt. Brute Force über alle sechzehn Teilmengen bestätigt das.

9. Baseball-Elimination

Ein Klassiker, und ungewöhnlich darin, dass die naive Antwort nicht nur langsam, sondern falsch ist.

Kann eine Mannschaft angesichts der Tabelle und der verbleibenden Spiele noch Erster werden? Die naheliegende Prüfung ist, ob ihre bestmögliche Gesamtzahl noch die aktuelle Gesamtzahl jedes Rivalen übertrifft. Das erfasst die einfachen Fälle und verfehlt die interessanten, denn Rivalen müssen gegeneinander spielen, und jemand muss diese Spiele gewinnen.

Hier ist eine Tabelle, bei der die naive Prüfung nichts Verdächtiges findet:

Die Ducks können 79 erreichen, und kein Rivale hat bisher 79 Siege, also eliminiert sie kein Einzelvergleich. Aber unter den verbleibenden Spielen treffen die Aces zweimal auf die Bolts, die Aces einmal auf die Comets und die Bolts dreimal auf die Comets. Sechs Spiele unter den drei Rivalen, und jedes davon beschert jemandem einen Sieg.

Bauen Sie ein Netzwerk: eine Quelle zu einem Knoten pro verbleibendem Paar, mit der Anzahl der Spiele, die sie noch bestreiten; jeder Paarknoten zu seinen beiden Mannschaften mit unendlicher Kapazität; jede Mannschaft zur Senke mit Kapazität gleich der Zahl weiterer Siege, die sie sich leisten kann, bevor sie den besten Fall der Ducks von 79 überholt. Die Ducks überleben nur, wenn alle sechs Spiele aufgenommen werden können, also nur, wenn der maximale Fluss die Quelle sättigt.

Das tut er nicht. Der Fluss beträgt 5 gegenüber 6 Spielen, also hat ein Spiel keinen Platz, und die Ducks sind eliminiert. Die Aufzählung aller 2⁹ Ausgänge jedes verbleibenden Spiels der Liga bestätigt es: Es gibt kein Szenario, in dem die Ducks Erster werden, und für jede der anderen drei Mannschaften gibt es eines.

Das Defizit sagt Ihnen auch, warum: Die gesättigten Mannschaftskanten benennen die Gruppe von Rivalen, die zusammen mehr Spiele gewinnen müssen, als sie sich leisten können. Interviewer, die dieses Problem kennen, fragen immer nach dieser Erklärung.

10. Minimale Pfadüberdeckung in einem DAG

„Wie viele Arbeiter braucht man mindestens, um all diese Aufgaben zu erledigen, wenn ein Arbeiter nur zwischen aufeinanderfolgenden Aufgaben wechseln kann?“

Das ist eine minimale Pfadüberdeckung: die wenigsten knotendisjunkten Pfade, die jeden Knoten eines gerichteten azyklischen Graphen überdecken. Sie reduziert sich mit einem merkenswerten Trick auf Matching. Teilen Sie jeden Knoten in eine Ausgangskopie links und eine Eingangskopie rechts, setzen Sie für jede Kante des DAG eine Kante in den bipartiten Graphen und suchen Sie ein maximales Matching. Dann gilt

minimale Pfadüberdeckung = Anzahl der Knoten − maximales Matching

, weil jede zugeordnete Kante zwei Pfadstücke verbindet und damit einen Pfad aus der Zählung entfernt. Auf einem DAG mit sechs Knoten und sieben Kanten ist das maximale Matching 4, also ist die minimale Pfadüberdeckung 6 − 4 = 2, und eine erschöpfende Suche über jede Teilmenge von Kanten bestätigt das.

Eine Einschränkung ist wichtig und wird oft vergessen: Das zählt knotendisjunkte Pfade. Dürfen die Pfade Knoten teilen, bilden Sie zuerst den transitiven Abschluss des DAG und wenden dann dieselbe Reduktion an.

11. Wenn es Min-Cost-Flow ist und nicht Max Flow

Die häufigste Nachfrage im ganzen Thema: „Jetzt hat jede Zuordnung Kosten, und ich will den billigsten Weg, alle unterzubringen.“

Max Flow kann das nicht beantworten. Er maximiert die Menge und ist zwischen zwei Lösungen gleicher Größe indifferent, liefert also bereitwillig das teuerste perfekte Matching. Was Sie brauchen, ist Min-Cost-Max-Flow: unter allen Flüssen mit maximalem Wert denjenigen mit den geringsten Gesamtkosten finden.

Die Änderung am Modell ist klein. Jede Kante erhält neben ihrer Kapazität Kosten pro Einheit, und der Algorithmus augmentiert wiederholt entlang des billigsten Pfades im Residualgraphen statt des kürzesten oder irgendeines Pfades. Da Residualkanten negative Kosten tragen, ist einfacher Dijkstra nicht direkt anwendbar, daher verwenden Standardimplementierungen entweder Bellman-Ford, was den Successive-Shortest-Path-Algorithmus ergibt, oder führen Potenziale im Stil von Johnson, damit Dijkstra nutzbar bleibt.

Drei Dinge sollten Sie darüber sagen können.

Der Spezialfall hat einen Namen. Ein vollständiger bipartiter Graph mit Kosten auf jeder Zuordnung und der Forderung, dass jeder zugeordnet wird, ist das Zuordnungsproblem, und die Ungarische Methode löst es in O(n³). Lautet das Problem des Interviewers genau „n Arbeiter, n Aufgaben, minimiere die Gesamtkosten“, ist die Ungarische Methode die erwartete Antwort.

Die Ganzzahligkeit gilt weiterhin. Bei ganzzahligen Kapazitäten kann der Min-Cost-Max-Flow weiterhin ganzzahlig gewählt werden, und genau das hält die Matching-Deutung gültig, wenn Kosten hinzukommen.

Die Falle ist, etwas anderes zu maximieren. „Maximiere den Gesamtwert“ und „maximiere die Zahl der Zuordnungen“ sind nicht dasselbe Ziel, und eine Lösung kann für das eine optimal und für das andere schlecht sein. Fragen Sie, welches gewünscht ist, bevor Sie etwas schreiben, denn der Interviewer ist oft absichtlich mehrdeutig, um zu sehen, ob Sie es bemerken.

Eine nützliche Grenze zum Aussprechen: Gibt es keine Kosten, nehmen Sie Max Flow; gibt es Kosten, aber jede Einheit muss fließen, ist es Min-Cost-Flow; liegen die Kosten auf den Knoten statt auf den Zuordnungen, sind Sie wahrscheinlich wieder im Abschluss-Terrain aus Abschnitt 8.

12. Die Komplexitätsantworten

Halten Sie diese bereit, und sagen Sie auch, welche Sie tatsächlich verwenden würden.

Die Warnung sollte man genau formulieren, denn sie ist eine häufige Nachfrage. Ford-Fulkerson ist das einzige Verfahren, dessen Laufzeit von den Kapazitätswerten statt von der Größe des Graphen abhängt. Jeder augmentierende Pfad erhöht den Fluss um mindestens 1, also läuft die Schleife höchstens maxflow Mal, und betragen die Kapazitäten eine Milliarde, sind das eine Milliarde Iterationen auf einem Graphen mit vier Knoten. Da eine Kapazität von einer Milliarde zehn Ziffern Eingabe sind, ist die Laufzeit exponentiell in der Eingabegröße. Edmonds-Karp behebt das, indem immer ein kürzester augmentierender Pfad gewählt wird, was die Abhängigkeit von den Kapazitäten vollständig beseitigt.

Zwei weitere Fakten bringen Pluspunkte. Ganzzahligkeit: Ist jede Kapazität ganzzahlig, gibt es einen ganzzahligen maximalen Fluss, und genau das rechtfertigt die Reduktionen auf Matching und disjunkte Pfade. Und die Kosten der Reduktion: Wenn Sie aus einer Geschichte ein Netzwerk bauen, geben Sie die Komplexität für das gebaute Netzwerk an, nicht für die ursprüngliche Eingabe. Ein bipartites Matching auf n Personen und m Rollen baut einen Graphen mit n + m + 2 Knoten, und das zu sagen, zeigt, dass Sie die Transformation verstanden haben.

13. Fehler, an denen das Interview scheitert

Die Rückwärtskanten vergessen. Der häufigste fatale Fehler, und er führt nicht zum Absturz, sondern liefert nur eine zu kleine Zahl. Wenn Sie nicht erklären können, warum ein Algorithmus seine eigenen früheren Entscheidungen zurücknehmen können muss, haben Sie den Algorithmus nicht verstanden.

Das Löserobjekt wiederverwenden. Ein zweiter Aufruf von max_flow auf derselben Instanz liefert 0, weil der Residualgraph bereits gesättigt ist. Das erwischt Leute, die einen Fluss berechnen, den Wert für eine Ausgabe erneut haben wollen und daraus schließen, ihr Code sei kaputt. Bauen Sie ein neues Objekt oder speichern Sie das Ergebnis.

Den Wert nennen, wenn nach der Menge gefragt ist. „Welche Verbindungen würden Sie kappen?“ wird nicht mit „16“ beantwortet. Rekonstruieren Sie die erreichbare Menge und listen Sie die Kanten auf.

Eine untere Schranke als Kapazität lesen. „Höchstens drei Schichten“ ist eine Kapazität. „Mindestens zwei Schichten“ ist keine und braucht eine andere Konstruktion. Achten Sie auf „muss“ und „mindestens“.

Knotengrenzen als Kantengrenzen modellieren. Liegt die Beschränkung auf einer Maschine statt auf einer Verbindung, teilen Sie den Knoten. Wer das überspringt, bekommt eine Antwort, die stillschweigend zu groß ist.

Ford-Fulkerson als Komplexität nennen. Das ist die eine Schranke, die in der Eingabegröße exponentiell sein kann. Nennen Sie Dinic und erklären Sie den Unterschied.

Zu Fluss greifen, wenn das Problem kein Flussproblem ist. Max Flow ist das falsche Werkzeug für kürzeste Wege, für Spannbäume und für alles, bei dem die Antwort eine einzelne Route statt einer geteilten Menge ist. Wird nichts aufgeteilt oder geteilt, schauen Sie zuerst auf BFS, Dijkstra oder Union-Find. Ein Kandidat, der zum schwersten Hammer im Kasten greift, verrät dem Interviewer etwas.

Stilles Modellieren. Die Reduktion ist die Antwort. Zeichnen Sie das Netzwerk an das Whiteboard, sagen Sie „Quelle zu jedem Ingenieur mit Kapazität eins, weil niemand zwei Jobs übernehmen kann“, und lassen Sie den Interviewer das Modell korrigieren, bevor Sie dreißig Zeilen gegen das falsche geschrieben haben.

15. Literatur

Die Ergebnisse hinter diesen Fragen, in chronologischer Reihenfolge.

1. Menger, K. (1927). “Zur allgemeinen Kurventheorie.” Fundamenta Mathematicae, 10, 96–115.
2. König, D. (1931). “Gráfok és mátrixok.” Matematikai és Fizikai Lapok, 38, 116–119.
3. Hall, P. (1935). “On representatives of subsets.” Journal of the London Mathematical Society, 10(1), 26–30.
4. Ford, L. R. und Fulkerson, D. R. (1956). “Maximal flow through a network.” Canadian Journal of Mathematics, 8, 399–404.
5. Ford, L. R. und Fulkerson, D. R. (1962). Flows in Networks. Princeton University Press.
6. Schwartz, B. L. (1966). “Possible winners in partially completed tournaments.” SIAM Review, 8(3), 302–308.
7. Dinic, E. A. (1970). “Algorithm for solution of a problem of maximum flow in networks with power estimation.” Soviet Mathematics Doklady, 11, 1277–1280.
8. Edmonds, J. und Karp, R. M. (1972). “Theoretical improvements in algorithmic efficiency for network flow problems.” Journal of the ACM, 19(2), 248–264.
9. 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–231.
10. Picard, J.-C. (1976). “Maximal closure of a graph and applications to combinatorial problems.” Management Science, 22(11), 1268–1272.
11. Goldberg, A. V. und Tarjan, R. E. (1988). “A new approach to the maximum-flow problem.” Journal of the ACM, 35(4), 921–940.
12. Ahuja, R. K., Magnanti, T. L. und Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.
13. Wayne, K. D. (2001). “A new property and a faster algorithm for baseball elimination.” SIAM Journal on Discrete Mathematics, 14(2), 223–229.
14. Kleinberg, J. und Tardos, É. (2005). Algorithm Design, Kapitel 7. Addison-Wesley.
15. Cormen, T. H., Leiserson, C. E., Rivest, R. L. und Stein, C. (2009). Introduction to Algorithms, 3. Auflage, Kapitel 26. MIT Press.