nätverksflöde

Nätverksflöde, eller network flow på engelska, är ett begrepp inom datavetenskap och grafteori som beskriver hur data eller resurser förflyttas genom ett nätverk. Ett nätverk representeras som en riktad graf där kanter har en kapacitet, vilket begränsar hur mycket som kan flöda genom dem. Målet med nätverksflödesproblem är ofta att maximera flödet från en källa till en sänka, eller att hitta en optimal fördelning av resurser givet vissa begränsningar.

Grundläggande koncept inom nätverksflöde inkluderar källan (source), en nod där flödet startar, och sänkan (sink), en nod där flödet slutar. Kapaciteten på en kant anger den maximala mängden som kan passera den per tidsenhet. Ett maximalt flöde är det största möjliga flödet som kan skickas från källan till sänkan utan att överskrida kapaciteten på någon kant.

Det finns flera algoritmer för att lösa nätverksflödesproblem, varav några av de mest kända är Ford-Fulkerson-algoritmen och Edmonds-Karp-algoritmen. Dessa algoritmer bygger på principen att successivt öka flödet längs återvändande vägar (augmenting paths) tills inget mer flöde kan skickas.

Nätverksflödesmodeller används inom en mängd olika tillämpningar. Exempel inkluderar optimering av kommunikationsnätverk, schemaläggning av uppgifter, transportproblem, och resurstilldelning. Förståelsen av nätverksflöde är därför fundamental för många områden inom datavetenskap och operationsanalys.