flödesproblem

Ett flödesproblem är ett optimeringsproblem som vanligtvis modelleras på en riktad graf där varje kant har en kapacitet som anger den maximala mängd som får flyta per tidsenhet. Grafen har två speciella noder: en källa s och en sänka t. Flödet f(u,v) på kanten från u till v är begränsat av kapaciteten c(u,v) och uppfyller flödeskonservans: för alla noder utom s och t är summan av in-flödet lika med summan av ut-flödet. Alla flöden är icke-negativa.

Målet med ett flödesproblem är att maximera den totala mängden flöde som når t från s, dvs värdet av flödet, definierat som utflödet från s (eller inflödet till t). Flödet måste följa kapacitetsbegränsningarna och konserveringsvillkoren vid samtliga noder.

Flödesproblem är nära kopplade till minsta-skärningsproblem; enligt max-flöde/min-skärning-teoremet är det största möjliga flödet lika med värdet av den minsta s-t-skärningen i grafen. Denna koppling ger både teoretisk förståelse och praktiska lösningar.

Vanliga algoritmer för flödesproblem inkluderar Ford-Fulkerson och dess variant Edmonds–Karp, som har praktisk robusthet även om teoretisk tidskomplexitet kan vara högre i vissa fall. Mer effektiva metoder är Dinics algoritm och preflow-push-algoritmer, vilka används för större nätverk i praktiken.

Tillämpningar av flödesproblem är många och inkluderar transport- och logistikplanering, telekommunikation, vattenförsörjning och bipartit matchning, där speciella fall förenklar modellen till maxflöde eller relaterade optimisationer. Varianta modeller omfattar dynamiska flöden via tidsutvidgade nätverk och cirkulationer med krav.