Wiele problemów informatycznych może mieć postać wykresu składającego się z węzłów i linków. Przykładem mogą tu być problemy z przepływem sieci polegające na transportowaniu towarów lub materiałów w sieci, np. w systemie kolejowym.
Możesz przedstawić przepływ danych na wykresie, którego węzły są miastami i których łuki tworzą linie kolejowe. Są to tzw. przepływy, ponieważ ich właściwości są podobne do właściwości przepływającej przez sieć rur.
Głównym ograniczeniem w przepływach sieci jest to, że każdy z nich ma pojemność, czyli maksymalną ilość, jaką można przenieść, wykorzystując do tego określony przedział czasu.
Problem z maksymalnym przebiegiem przepływu określa maksymalną łączną ilość ruchu, jaką można przenieść we wszystkich łukach sieci, z uwzględnieniem ograniczeń pojemności.
Pierwszą osobą, która badała ten problem, był rosyjski matematyk A.N. Tolstoi. Na poniższej mapie przedstawiliśmy rzeczywistą sieć kolejową, dla której chcieliśmy znaleźć maksymalną prędkość.
Narzędzie OR-Tools zawiera kilka rozwiązań problemów z przepływem sieci w jego bibliotekach graph.
Poniżej znajdziesz przykłady problemów z przepływem sieci oraz sposoby ich rozwiązywania: