3223515914

Edmonton Saskatoon

(b)

Rys. 27.1. (a) Sieć G = (V, E) modelująca problem transportu powstały w kanadyjskiej spółce „Szczęśliwy Krążek” produkującej krążki hokejowe. Fabryka w Vancouver jest źródłem s, w którym produkuje się krążki hokejowe. Magazyn w Winnipeg jest ujściem t, do którego transportuje się krążki. Krążki są transportowane w kontenerach. Towar nie jest wysyłany bezpośrednio do Winnipeg, ale wędruje przez punkty przeładunkowe, które znajdują się w kilku miastach. Z miasta u do miasta v można każdego dnia przewieźć tylko c(u, v) kontenerów. Przy każdej krawędzi zaznaczono jej przepustowość, (b) Przepływ / w G o wartości |/| = 19. Pokazano tylko dodatnie przepływy netto. Jeśli /(u, v) > 0, to krawędź (w, v) ma etykietę/(u, v)/c(u, v). (Kreska ukośna nie jest znakiem dzielenia. Separuje ona przepływ netto od przepustowości). Jeśli/(u, v) < 0, to etykietą krawędzi (u, v) jest tylko jej przepustowość