maxflödet

Maxflödet, eller maximum flow, är ett grundläggande begrepp inom grafteori och operations research. I en riktad graf med kapaciteter på kanter och en särskild källa s samt ett mål t uppgiften att hitta det största genomflödet som kan överföras från s till t utan att överstiga kantkapaciteterna.

Formellt består problemet av en riktad graf G=(V,E) med en kapacitetsfunktion c:E→R_+. En s-t-flöde f:E→R_+ uppfyller 0≤f(u,v)≤c(u,v) för alla kanter och flödesbevarande i varje v≠s,t: summan av inflöde till v är lika med summan av utflöde från v. Flödets värde |f| definieras som summan av f(s,v) över kanter som lämnar s. Maxflödet är det flöde som maximerar |f|.

Maxflödet kopplas till min-kutteoremet: det största genomflödet från s till t är lika med den minsta totala kapaciteten hos de kanter som avskärsnar s från t, det s.k. s-t-min-cut. Denna dualitet förklarar varför maximalt flöde och minimalt avskärningsmått är två sidor av samma problem.

Algoritmer för att beräkna maxflödet inkluderar Ford-Fulkerson-metoden för att successivt hitta augmenting paths i residualgrafen, samt förbättringar som Edmonds-Karp (val av kortaste väg) och Dinics som använder nivåstrukturer för effektivare flödesfinishing. För heltalskapaciteter är det maximala flödet ofta heltal.

Användningar omfattar optimering av nätverkstrafik, bipartita matchningar via flöderekologi, projektval och bildseparering inom bildbehandling och datorsyn. Andra varianter omfattar flera källor och mål, multi-commodity-flöden och dynamiska nätverk.