Netwerkstromen

Netwerkstromen verwijzen naar de hoeveelheid materiaal of informatie die door een netwerk beweegt gedurende een bepaalde periode. In informatica en telecommunicatie gaat het meestal om datapakketten en de benutting van verbindingen, terwijl in operationsonderzoek netwerkstromen een wiskundig model vormen van stromen op een gerichte graaf.

Een basismodel gebruikt een netwerk G met knopen V en gerichte randen E. Elke rand e heeft een capaciteit c_e die de maximale stroom langs die rand bepaalt. Een stroom f is een toewijzing van waarden aan de randen die voldoet aan 0 ≤ f_e ≤ c_e. Er is een bron s en een sink t; op elk knooppunt behalve s en t geldt de stroombehoud-constante: de som van de binnenkomende stromen is gelijk aan de som van de uitgaande stromen.

Het maximum-flowprobleem zoekt de grootste mogelijke stroom van s naar t onder de randvoorwaarden. Het min-cut-theorema stelt dat de maximale stroom gelijk is aan de capaciteit van de minimaal s-t-scheiding. Bekende algoritmes om de oplossing te vinden zijn Ford-Fulkerson en zijn varianten zoals Edmonds-Karp, Dinic en push-relabel. Deze algoritmes verschillen in tijdscomplexiteit en toepasbaarheidsvoorwaarden.

Toepassingen liggen op het gebied van netwerkontwerp en routing, verkeers- en congestiebeheer, en logistiek of water- en energienetwerken. In de praktijk worden netwerkstromen gebruikt om knelpunten te identificeren, capaciteitsplannen te optimaliseren en bronnen effectief toe te wijzen.

Daarnaast bestaan er varianten zoals multi-commodity flows (meerdere soorten stromen met verschillende bronnen en doelen) en dynamische of tijdsafhankelijke netwerken waarin vraag en capaciteit in de tijd veranderen.