0000103

Tak zdefiniowany opływ f noże nieć wiole interpretacji praktycznych (fizycznych). Najprostszą interpretacją Joot ruch wagonów w alecl kolejowej, której odcinki dróg reprezentowane są łukaal grafu C.

Nie w kożdoj alecl latnieja opływ. Zauważmy, że dla 1 ■ O latnlejo zawsze opływ f ■ O. Ola dowolnej funkcji 1 pojawia elą problem stwierdzania istnienia opływu.

Oznaczmy przez F zbiór opływów f danej elecl 8. Dońll F/ p, to powstaje problem metody wyznaczenia dowolnego f€F. Okazuje clą, że aetoda łańcuchów powląkezelnych (zmienielnych), określonych w dowodzie twierdzenia Forda-Fulkeraona, może być wykorzystana'do rozwiązania obu powyższych problemów [lś],

12.1. Algorytm wyznaczania opływu f

(^) Wyznaczamy dowolną funkcją f₀ spełniającą warunek 2° opływu (na przykład f_D« 0).

(^) Oeśll f_e spełnia warunek 1°, to f i ■ f₀ ; KONIEC j CN i . p.

V/ybleramy łuk <o.b> € U, teki że

[ł₀(.,b)<l(..b)] v[f₀(..b)> h(.,b|]

*    ■ I V ■    ■ '    'ST

A    B

De i li A, to skok do    ; Jeśli B, to ekok do (ii) .

@ Cechujemy wierzchołek b cechą (a⁴, t(b)), gdzie C(b) •

• l(e,b) - f₀(o,b). Wierzchołek b ataje alą ocechowany 1 niesprawdzony. Zbiór wiarzchołkó* ocechowanych 1 niesprawdzonych CN i ■ {b} .

0) Wybieramy dowolny wierzchołek x CCN.

Każdemu nieocechowanemu yeP_x\CN, jeśli f(x,y)<. h(x,y), nadajemy cechą (x⁴, min (c(x), h(x,y) - f₀(x,y)J) oraz CN j - CNu{yJ.

Każdemu nieocechowanemu zc r“¹(x)\CN, jeśli f₀(z,x) > l(z,x), nadajemy cechą (x“, min {t(x), f₀(z,x) - l(z,x)j) oraz CN i ■

■ CNv{z} CN I - CN \{x).

Pytamy czy a l CN ?

TAKi Znlonlany f_Q dla łuków utworzonego cyklicznego łańcucha powiejLazalnogo (zmionlolnogo) o wartość Ł(a) i akok do (2^ .

NIE i Pytamy, czy CN / ? ?

TAK - akok do (A2).

NIE - Stop. NIE ISTNIEJE OPŁYW.

@ Cechujemy wierzchołek a cechą (b”, £(a)), gdzie Ł(a) ■

■ f₀(o,b) “ h(a,b). Wiorzchołok a etajo oię ocechowany i niesprawdzony. Zbiór wierzchołków ocechowanych i niesprawdzonych CN 1 ■ (a)t

(02) Wybioramy dowolny wierzchołek x £ CN.

Każdomu nioocochowonomu y£r(x)\CN, Jeśli f₀(x,y) <■ h(x,y), nadajemy cochę (x*,min |e(x), h(x,y) - f₀(*.y)J) oroz CN : - CN <j {y} .

Każdemu nieocechowonemu z 6 r”^ł(x) \ CN, Jośli f_e(z,x)>l(z,x), nadajemy cechę (x",min |t(x), f_Q(z,x) - l(z,x)|) oraz CN 1 ■ CNu{x);

CN 1 - Cn\{x).

Pytamy, czy b tCN ?

TAKj Zmieniamy f_Q dla łuków utworzonego, cyklicznego łańcucha powlękezelnago (zmienialnego) o wartość £(b)

1 akok do (Pj).

NIE 1 Pytamy, czy CN\f p ?

TAKi Skok do (B2).

NIE 1 Stop. NIE ISTNIEJE OPŁYW*

Metodę wyznaczania opływu motamy wykorzyatać do wyznacza -nia przepływu w aiaci z obuetronnyml ograniczeniami przapuato -wości łuków. Chodzi o to, ta w alecl S ■ <0,{a) {l.h}> , gdzla lf»0 nie zawaze ietniejt przepływ f epełnlający warunek M*»y)4 f(x.y) 6 h(x,y). Przypomnijmy, ta w alecl 8 ■<C,{a),{h), omawianej w punkcie dotyczącym przepływów, iatnieje zaweta co najmniej jeden przepływ zerowy. Wprowadzenie dolnego ograniczenia 1 mota apowodować, te zbiór motliwyoh przepływów ataji alf Puety.