Tool guide

Maximaler Fluss, Min-Cut und bipartites Matching

Das Panel Flow & matching deckt drei verwandte Aufgaben auf der gemeinsamen Canvas aus der Graph-Theorie-Workbench ab: einen maximalen Fluss von einer Quelle zu einer Senke mit Dinic oder Edmonds–Karp, einen Bipartit-Check, der den Graphen färbt oder einen ungeraden Zyklus als Gegenbeispiel liefert, und ein ungarisches Maximum-Matching mit der minimalen Knotenüberdeckung nach Kőnig. Flussergebnisse kommen mit der Min-Cut-Kapazität, den Schnittkanten und der Quellseite des Schnitts, sodass die Antwort ihren eigenen Beweis mitbringt.

Updated 5 sources4 min read