So führen Sie eine Fluss- oder Matching-Abfrage aus 01 Das Netzwerk aufbauen. Das Preset Flow network S→T ist ein gerichtetes Netzwerk mit 6 Knoten; Bipartit-Tests akzeptieren auch das Preset Bipartite K₃,₃ und jedes Gitter. 02 Dinic max-flow oder Edmonds–Karp wählen , Source S und Sink T setzen und maximalen Fluss, Min-Cut-Kapazität, die Gegenprüfungszeile und die Tabelle Fluss/Kapazität je Kante ablesen. 03 Beim Bipartite check das Urteil, die linke und rechte Menge und — wenn die Antwort Nein lautet — den Zeugen des ungeraden Zyklus ablesen. 04 Beim Hungarian matching einen bipartiten Graphen laden und Matching-Größe, Paare, minimale Knotenüberdeckung und nicht gematchte Knoten ablesen. 05 Den Lauf schrittweise ausführen , um zu sehen, wie augmentierende Pfade den Flusswert erhöhen.
Durchgerechnete Messwerte
Setup
Messwert
Fluss-Preset, Dinic S → T
maximaler Fluss 19 ; Min-Cut-Kapazität 19 ; Gegenprüfung (Edmonds–Karp) 19 ; Schnittkanten S→A, B→D ; Quellseite S, B
Fluss-Preset, Kantenflüsse
S→A 10/10 , S→B 9/10 , A→C 4/4 , A→D 6/8 , B→D 9/9 , C→T 9/10 , D→C 5/6 , D→T 10/10
Bipartite K₃,₃, Hungarian matching
maximales Matching 3 ; Paare L1–R3, L2–R2, L3–R1 ; minimale Knotenüberdeckung L1, L2, L3 ; ohne Partner —
Zyklus C₅, Bipartite check
bipartit Nein ; Zeuge des ungeraden Zyklus C → B → A → E → D → C
Gitter 4 × 5, Bipartite check
bipartit Ja ; links 10 Knoten beginnend 1-1, 1-3, 1-5, 2-2; rechts 10 beginnend 1-2, 1-4, 2-1
Die beiden Flussalgorithmen stimmen bei 19 überein, und die Schnittkanten bestätigen die Schranke: S→A führt 10 und B→D führt 9 , zusammen der maximale Fluss. Die Senke erhält 9 über C→T und 10 über D→T, wieder 19 .
Warum der Schnitt den Fluss beweist Max-Flow-Min-Cut besagt, dass der beste Fluss gleich dem günstigsten Engpass ist. Dinic stoppt, wenn kein augmentierender Pfad mehr übrig ist; das Panel zeigt dann die von S aus noch erreichbaren Knoten — die Quellseite S, B — und die Kanten, die sie verlassen, S→A und B→D , deren Kapazitäten 10 und 9 sich zum Fluss addieren. Jede Einheit muss diesen Schnitt überqueren, also existiert kein größerer Fluss. Auf der Matching-Seite liefert das Theorem von Kőnig denselben Beweisstil: ein Matching der Größe 3 und eine Knotenüberdeckung der Größe 3 legen sich gegenseitig fest.
Grenzen
Matching braucht einen bipartiten Graphen. Führen Sie Hungarian matching auf dem Preset Petersen aus, und das Panel verweigert mit "Graph is not bipartite (odd cycle O3 → O2 → O1 → O5 → O4 → O3) — the Hungarian/Kuhn algorithm does not apply", statt eine Teillösung zurückzugeben. Ein Matching für allgemeine Graphen wird nicht angeboten.
Ein Quelle-Senke-Paar auf einmal, keine Kosten. Es gibt keinen min-cost flow, keinen multi-commodity flow und keine Untergrenzen auf Kanten; führen Sie Paare nacheinander aus und vergleichen Sie die Quellseiten. Was es nicht tut. Es zählt keine Schnitte über das gemeldete Minimum hinaus auf und importiert keine Netzwerkdateien. Bauen Sie das Netzwerk auf der Canvas und nehmen Sie die Adjazenzmatrix für weitere Algebra mit zu math tools oder listen Sie Erreichbarkeit mit Components auf.
Die Richtungsfalle Schnittkanten werden als gerichtete Paare ausgegeben. Im gerichteten Flow-Preset sind sie S→A und B→D ; im ungerichteten Standardgraphen gibt Dinic A→F die Kanten A→B, A→C mit Quellseite A aus. Die Quellseite ist der stabile Messwert über Läufe hinweg — alles, was von S aus noch erreichbar ist, wenn der Algorithmus stoppt —, vergleichen Sie also diese Zeile, nicht die Pfeilrichtung, wenn Sie einen Schnitt von Hand nachprüfen.
Wo es nützlich ist Kapazitätsplanung Das Flow-Preset zeigt, wie viel von einem Bedarf von 19 Einheiten durchgehen kann und wo der Engpass sitzt: S→B behält 1 Einheit Spielraum, während A→D 2 übrig lässt, aber der Schnitt S→A / B→D ist gesättigt. Erhöhen Sie die Kapazität einer Schnittkante, und der Flusswert bewegt sich; erhöhen Sie eine Kante im Inneren des Netzwerks, und er tut es meist nicht.
Zuordnungsprobleme Auf Bipartite K₃,₃ paart das Hungarian-Panel alle drei linken Knoten und gibt eine Überdeckung derselben Größe aus, sodass die Zuordnung beweisbar maximal ist. Gitter antworten mit Ja auf den Bipartit-Check bei einer gleichen 10/10-Teilung, während C₅ mit Nein antwortet und den ungeraden Zyklus zurückgibt — das Zertifikat, dass keine 2-Färbung existiert. Das Panel Traversal kann dann die Farbgruppen Knoten für Knoten zeigen.
Datenschutz Alle Fluss-, Färbungs- und Matching-Berechnungen laufen in Ihrem Browser; nichts wird hochgeladen.
Referenzen
Wikipedia, Maximum flow problem , en.wikipedia.org (访问日期:2026-10-07)— augmentierende Pfade und Flusswert.
Wikipedia, Max-flow min-cut theorem , en.wikipedia.org (访问日期:2026-10-07)— Fluss gleich Schnittkapazität.
Wikipedia, Bipartite graph , en.wikipedia.org (访问日期:2026-10-07)— 2-Färbung und ungerade Zyklen.
Wikipedia, Maximum cardinality matching , en.wikipedia.org (访问日期:2026-10-07)— Matching über augmentierende Pfade.
Wikipedia, Kőnig's theorem (graph theory) , en.wikipedia.org (访问日期:2026-10-07)— Matching gleich Knotenüberdeckung in bipartiten Graphen.
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
Updated 2026-10-07