Badania Operacyjne w Logistyce
Wykład 4
Sieci przepływowe
Jacek Rogowski
Instytut Matematyki
Politechnika Łódzka
Jacek Rogowski
Badania Operacyjne w Logistyce
Wykład 4
Sieci przepływowe
Jacek Rogowski
Instytut Matematyki
Politechnika Łódzka
Jacek Rogowski
Sieć przepływowa
Definicja
Grafem skierowanym nazywamy parę (V , E ), w której:
V jest skończonym i niepustym zbiorem, którego elementy
nazywamy wierzchołkami,
E ⊂ V × V ; elementy tego zbioru nazywamy krawędziami.
Jeżeli (u, v ) ∈ E jest krawędzią, to wierzchołek u nazywamy
początkiem, a v końcem tej krawędzi.
Reprezentacją grafu skierowanego jest rysunek, na którym
wierzchołki oznaczane są jako punkty, a krawędzie jako odcinki lub
krzywe. Orientacja krawędzi jest reprezentowana przez
narysowanie strzałki zgodnie z kierunkiem od wierzchołka
początkowego do końcowego.
Jacek Rogowski
Sieć przepływowa
Definicja
Grafem skierowanym nazywamy parę (V , E ), w której:
V jest skończonym i niepustym zbiorem, którego elementy
nazywamy wierzchołkami,
E ⊂ V × V ; elementy tego zbioru nazywamy krawędziami.
Jeżeli (u, v ) ∈ E jest krawędzią, to wierzchołek u nazywamy
początkiem, a v końcem tej krawędzi.
Reprezentacją grafu skierowanego jest rysunek, na którym
wierzchołki oznaczane są jako punkty, a krawędzie jako odcinki lub
krzywe. Orientacja krawędzi jest reprezentowana przez
narysowanie strzałki zgodnie z kierunkiem od wierzchołka
początkowego do końcowego.
Jacek Rogowski
Sieć przepływowa
Definicja
Grafem skierowanym nazywamy parę (V , E ), w której:
V jest skończonym i niepustym zbiorem, którego elementy
nazywamy wierzchołkami,
E ⊂ V × V ;
elementy tego zbioru nazywamy krawędziami.
Jeżeli (u, v ) ∈ E jest krawędzią, to wierzchołek u nazywamy
początkiem, a v końcem tej krawędzi.
Reprezentacją grafu skierowanego jest rysunek, na którym
wierzchołki oznaczane są jako punkty, a krawędzie jako odcinki lub
krzywe. Orientacja krawędzi jest reprezentowana przez
narysowanie strzałki zgodnie z kierunkiem od wierzchołka
początkowego do końcowego.
Jacek Rogowski
Sieć przepływowa
Definicja
Grafem skierowanym nazywamy parę (V , E ), w której:
V jest skończonym i niepustym zbiorem, którego elementy
nazywamy wierzchołkami,
E ⊂ V × V ; elementy tego zbioru nazywamy krawędziami.
Jeżeli (u, v ) ∈ E jest krawędzią, to wierzchołek u nazywamy
początkiem, a v końcem tej krawędzi.
Reprezentacją grafu skierowanego jest rysunek, na którym
wierzchołki oznaczane są jako punkty, a krawędzie jako odcinki lub
krzywe. Orientacja krawędzi jest reprezentowana przez
narysowanie strzałki zgodnie z kierunkiem od wierzchołka
początkowego do końcowego.
Jacek Rogowski
Sieć przepływowa
Definicja
Grafem skierowanym nazywamy parę (V , E ), w której:
V jest skończonym i niepustym zbiorem, którego elementy
nazywamy wierzchołkami,
E ⊂ V × V ; elementy tego zbioru nazywamy krawędziami.
Jeżeli (u, v ) ∈ E jest krawędzią, to wierzchołek u nazywamy
początkiem, a v końcem tej krawędzi.
Reprezentacją grafu skierowanego jest rysunek, na którym
wierzchołki oznaczane są jako punkty, a krawędzie jako odcinki lub
krzywe. Orientacja krawędzi jest reprezentowana przez
narysowanie strzałki zgodnie z kierunkiem od wierzchołka
początkowego do końcowego.
Jacek Rogowski
Sieć przepływowa
Definicja
Grafem skierowanym nazywamy parę (V , E ), w której:
V jest skończonym i niepustym zbiorem, którego elementy
nazywamy wierzchołkami,
E ⊂ V × V ; elementy tego zbioru nazywamy krawędziami.
Jeżeli (u, v ) ∈ E jest krawędzią, to wierzchołek u nazywamy
początkiem, a v końcem tej krawędzi.
Reprezentacją grafu skierowanego jest rysunek, na którym
wierzchołki oznaczane są jako punkty,
a krawędzie jako odcinki lub
krzywe. Orientacja krawędzi jest reprezentowana przez
narysowanie strzałki zgodnie z kierunkiem od wierzchołka
początkowego do końcowego.
Jacek Rogowski
Sieć przepływowa
Definicja
Grafem skierowanym nazywamy parę (V , E ), w której:
V jest skończonym i niepustym zbiorem, którego elementy
nazywamy wierzchołkami,
E ⊂ V × V ; elementy tego zbioru nazywamy krawędziami.
Jeżeli (u, v ) ∈ E jest krawędzią, to wierzchołek u nazywamy
początkiem, a v końcem tej krawędzi.
Reprezentacją grafu skierowanego jest rysunek, na którym
wierzchołki oznaczane są jako punkty, a krawędzie jako odcinki lub
krzywe.
Orientacja krawędzi jest reprezentowana przez
narysowanie strzałki zgodnie z kierunkiem od wierzchołka
początkowego do końcowego.
Jacek Rogowski
Sieć przepływowa
Definicja
Grafem skierowanym nazywamy parę (V , E ), w której:
V jest skończonym i niepustym zbiorem, którego elementy
nazywamy wierzchołkami,
E ⊂ V × V ; elementy tego zbioru nazywamy krawędziami.
Jeżeli (u, v ) ∈ E jest krawędzią, to wierzchołek u nazywamy
początkiem, a v końcem tej krawędzi.
Reprezentacją grafu skierowanego jest rysunek, na którym
wierzchołki oznaczane są jako punkty, a krawędzie jako odcinki lub
krzywe. Orientacja krawędzi jest reprezentowana przez
narysowanie strzałki zgodnie z kierunkiem od wierzchołka
początkowego do końcowego.
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E ) będzie grafem skierowanym.
Wierzchołek w ∈ V
nazywamy
źródłem, jeżeli jest początkiem każdej krawędzi, do której
należy,
ujściem, jeżeli jest końcem każdej krawędzi, do której należy.
Definicja
Drogą o długości n od źródła s do ujścia t w grafie skierowanym
G = (V , E ) nazywamy każdy ciąg krawędzi postaci:
(v
0
, v
1
), (v
1
, v
2
), . . . , (v
n−1
, v
n
),
w którym v
0
= s i v
n
= t.
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E ) będzie grafem skierowanym.Wierzchołek w ∈ V
nazywamy
źródłem, jeżeli jest początkiem każdej krawędzi, do której
należy,
ujściem, jeżeli jest końcem każdej krawędzi, do której należy.
Definicja
Drogą o długości n od źródła s do ujścia t w grafie skierowanym
G = (V , E ) nazywamy każdy ciąg krawędzi postaci:
(v
0
, v
1
), (v
1
, v
2
), . . . , (v
n−1
, v
n
),
w którym v
0
= s i v
n
= t.
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E ) będzie grafem skierowanym.Wierzchołek w ∈ V
nazywamy
źródłem, jeżeli jest początkiem każdej krawędzi, do której
należy,
ujściem, jeżeli jest końcem każdej krawędzi, do której należy.
Definicja
Drogą o długości n od źródła s do ujścia t w grafie skierowanym
G = (V , E ) nazywamy każdy ciąg krawędzi postaci:
(v
0
, v
1
), (v
1
, v
2
), . . . , (v
n−1
, v
n
),
w którym v
0
= s i v
n
= t.
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E ) będzie grafem skierowanym.Wierzchołek w ∈ V
nazywamy
źródłem, jeżeli jest początkiem każdej krawędzi, do której
należy,
ujściem, jeżeli jest końcem każdej krawędzi, do której należy.
Definicja
Drogą o długości n od źródła s do ujścia t w grafie skierowanym
G = (V , E ) nazywamy każdy ciąg krawędzi postaci:
(v
0
, v
1
), (v
1
, v
2
), . . . , (v
n−1
, v
n
),
w którym v
0
= s i v
n
= t.
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E ) będzie grafem skierowanym.
Graf G nazywamy
siecią, jeżeli spełnione są następujące warunki:
w grafie G istnieje dokładnie jedno źródło,
w grafie G istnieje dokładnie jedno ujście,
graf G jest spójny, tzn. każdy wierzchołek v leży na pewnej
drodze od źródła s do ujścia t.
Sieć spełniającą powyższe warunki będziemy zapisywać w postaci
G = (V , E , s, t).
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E ) będzie grafem skierowanym.Graf G nazywamy
siecią, jeżeli spełnione są następujące warunki:
w grafie G istnieje dokładnie jedno źródło,
w grafie G istnieje dokładnie jedno ujście,
graf G jest spójny, tzn. każdy wierzchołek v leży na pewnej
drodze od źródła s do ujścia t.
Sieć spełniającą powyższe warunki będziemy zapisywać w postaci
G = (V , E , s, t).
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E ) będzie grafem skierowanym.Graf G nazywamy
siecią, jeżeli spełnione są następujące warunki:
w grafie G istnieje dokładnie jedno źródło,
w grafie G istnieje dokładnie jedno ujście,
graf G jest spójny, tzn. każdy wierzchołek v leży na pewnej
drodze od źródła s do ujścia t.
Sieć spełniającą powyższe warunki będziemy zapisywać w postaci
G = (V , E , s, t).
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E ) będzie grafem skierowanym.Graf G nazywamy
siecią, jeżeli spełnione są następujące warunki:
w grafie G istnieje dokładnie jedno źródło,
w grafie G istnieje dokładnie jedno ujście,
graf G jest spójny, tzn. każdy wierzchołek v leży na pewnej
drodze od źródła s do ujścia t.
Sieć spełniającą powyższe warunki będziemy zapisywać w postaci
G = (V , E , s, t).
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E ) będzie grafem skierowanym.Graf G nazywamy
siecią, jeżeli spełnione są następujące warunki:
w grafie G istnieje dokładnie jedno źródło,
w grafie G istnieje dokładnie jedno ujście,
graf G jest spójny,
tzn. każdy wierzchołek v leży na pewnej
drodze od źródła s do ujścia t.
Sieć spełniającą powyższe warunki będziemy zapisywać w postaci
G = (V , E , s, t).
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E ) będzie grafem skierowanym.Graf G nazywamy
siecią, jeżeli spełnione są następujące warunki:
w grafie G istnieje dokładnie jedno źródło,
w grafie G istnieje dokładnie jedno ujście,
graf G jest spójny, tzn. każdy wierzchołek v leży na pewnej
drodze od źródła s do ujścia t.
Sieć spełniającą powyższe warunki będziemy zapisywać w postaci
G = (V , E , s, t).
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E ) będzie grafem skierowanym.Graf G nazywamy
siecią, jeżeli spełnione są następujące warunki:
w grafie G istnieje dokładnie jedno źródło,
w grafie G istnieje dokładnie jedno ujście,
graf G jest spójny, tzn. każdy wierzchołek v leży na pewnej
drodze od źródła s do ujścia t.
Sieć spełniającą powyższe warunki będziemy zapisywać w postaci
G = (V , E , s, t).
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E , s, t) będzie siecią ze źródłem s i ujściem t.
Przepustowością w sieci G nazywamy każdą funkcję
c : V × V → R spełniającą następujące warunki:
∀
u, v ∈V
c(u, v ) 0 ,
∀
u, v ∈V
(u, v ) 6∈ E ⇒ c(u, v ) = 0.
Jeżeli c jest przepustowością w sieci G , to parę (G , c) nazywamy
siecią przepływową.
Uwaga: Funkcja przepustowości c określona jest dla wszystkich
par wierzchołków, a nie tylko dla krawędzi grafu G . Tworząc
graficzną reprezentację sieci przepływowej rysujemy tylko te
krawędzie, wzdłuż których przepustowość jest dodatnia i te
wartości zapisujemy obok odpowiednich krawędzi.
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E , s, t) będzie siecią ze źródłem s i ujściem t.
Przepustowością w sieci G nazywamy każdą funkcję
c : V × V → R spełniającą następujące warunki:
∀
u, v ∈V
c(u, v ) 0 ,
∀
u, v ∈V
(u, v ) 6∈ E ⇒ c(u, v ) = 0.
Jeżeli c jest przepustowością w sieci G , to parę (G , c) nazywamy
siecią przepływową.
Uwaga: Funkcja przepustowości c określona jest dla wszystkich
par wierzchołków, a nie tylko dla krawędzi grafu G . Tworząc
graficzną reprezentację sieci przepływowej rysujemy tylko te
krawędzie, wzdłuż których przepustowość jest dodatnia i te
wartości zapisujemy obok odpowiednich krawędzi.
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E , s, t) będzie siecią ze źródłem s i ujściem t.
Przepustowością w sieci G nazywamy każdą funkcję
c : V × V → R spełniającą następujące warunki:
∀
u, v ∈V
c(u, v ) 0 ,
∀
u, v ∈V
(u, v ) 6∈ E ⇒ c(u, v ) = 0.
Jeżeli c jest przepustowością w sieci G , to parę (G , c) nazywamy
siecią przepływową.
Uwaga: Funkcja przepustowości c określona jest dla wszystkich
par wierzchołków, a nie tylko dla krawędzi grafu G . Tworząc
graficzną reprezentację sieci przepływowej rysujemy tylko te
krawędzie, wzdłuż których przepustowość jest dodatnia i te
wartości zapisujemy obok odpowiednich krawędzi.
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E , s, t) będzie siecią ze źródłem s i ujściem t.
Przepustowością w sieci G nazywamy każdą funkcję
c : V × V → R spełniającą następujące warunki:
∀
u, v ∈V
c(u, v ) 0 ,
∀
u, v ∈V
(u, v ) 6∈ E ⇒ c(u, v ) = 0.
Jeżeli c jest przepustowością w sieci G , to parę (G , c) nazywamy
siecią przepływową.
Uwaga: Funkcja przepustowości c określona jest dla wszystkich
par wierzchołków, a nie tylko dla krawędzi grafu G . Tworząc
graficzną reprezentację sieci przepływowej rysujemy tylko te
krawędzie, wzdłuż których przepustowość jest dodatnia i te
wartości zapisujemy obok odpowiednich krawędzi.
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E , s, t) będzie siecią ze źródłem s i ujściem t.
Przepustowością w sieci G nazywamy każdą funkcję
c : V × V → R spełniającą następujące warunki:
∀
u, v ∈V
c(u, v ) 0 ,
∀
u, v ∈V
(u, v ) 6∈ E ⇒ c(u, v ) = 0.
Jeżeli c jest przepustowością w sieci G , to parę (G , c) nazywamy
siecią przepływową.
Uwaga: Funkcja przepustowości c określona jest dla wszystkich
par wierzchołków, a nie tylko dla krawędzi grafu G . Tworząc
graficzną reprezentację sieci przepływowej rysujemy tylko te
krawędzie, wzdłuż których przepustowość jest dodatnia i te
wartości zapisujemy obok odpowiednich krawędzi.
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E , s, t) będzie siecią ze źródłem s i ujściem t.
Przepustowością w sieci G nazywamy każdą funkcję
c : V × V → R spełniającą następujące warunki:
∀
u, v ∈V
c(u, v ) 0 ,
∀
u, v ∈V
(u, v ) 6∈ E ⇒ c(u, v ) = 0.
Jeżeli c jest przepustowością w sieci G , to parę (G , c) nazywamy
siecią przepływową.
Uwaga: Funkcja przepustowości c określona jest dla wszystkich
par wierzchołków,
a nie tylko dla krawędzi grafu G . Tworząc
graficzną reprezentację sieci przepływowej rysujemy tylko te
krawędzie, wzdłuż których przepustowość jest dodatnia i te
wartości zapisujemy obok odpowiednich krawędzi.
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E , s, t) będzie siecią ze źródłem s i ujściem t.
Przepustowością w sieci G nazywamy każdą funkcję
c : V × V → R spełniającą następujące warunki:
∀
u, v ∈V
c(u, v ) 0 ,
∀
u, v ∈V
(u, v ) 6∈ E ⇒ c(u, v ) = 0.
Jeżeli c jest przepustowością w sieci G , to parę (G , c) nazywamy
siecią przepływową.
Uwaga: Funkcja przepustowości c określona jest dla wszystkich
par wierzchołków, a nie tylko dla krawędzi grafu G .
Tworząc
graficzną reprezentację sieci przepływowej rysujemy tylko te
krawędzie, wzdłuż których przepustowość jest dodatnia i te
wartości zapisujemy obok odpowiednich krawędzi.
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E , s, t) będzie siecią ze źródłem s i ujściem t.
Przepustowością w sieci G nazywamy każdą funkcję
c : V × V → R spełniającą następujące warunki:
∀
u, v ∈V
c(u, v ) 0 ,
∀
u, v ∈V
(u, v ) 6∈ E ⇒ c(u, v ) = 0.
Jeżeli c jest przepustowością w sieci G , to parę (G , c) nazywamy
siecią przepływową.
Uwaga: Funkcja przepustowości c określona jest dla wszystkich
par wierzchołków, a nie tylko dla krawędzi grafu G . Tworząc
graficzną reprezentację sieci przepływowej rysujemy tylko te
krawędzie, wzdłuż których przepustowość jest dodatnia
i te
wartości zapisujemy obok odpowiednich krawędzi.
Jacek Rogowski
Sieć przepływowa
Definicja
Niech G = (V , E , s, t) będzie siecią ze źródłem s i ujściem t.
Przepustowością w sieci G nazywamy każdą funkcję
c : V × V → R spełniającą następujące warunki:
∀
u, v ∈V
c(u, v ) 0 ,
∀
u, v ∈V
(u, v ) 6∈ E ⇒ c(u, v ) = 0.
Jeżeli c jest przepustowością w sieci G , to parę (G , c) nazywamy
siecią przepływową.
Uwaga: Funkcja przepustowości c określona jest dla wszystkich
par wierzchołków, a nie tylko dla krawędzi grafu G . Tworząc
graficzną reprezentację sieci przepływowej rysujemy tylko te
krawędzie, wzdłuż których przepustowość jest dodatnia i te
wartości zapisujemy obok odpowiednich krawędzi.
Jacek Rogowski
Sieć przepływowa
Przykład sieci przepływowej:
Liczby przy krawędziach są wartościami przepustowości wzdłuż
tych krawędzi.
Jacek Rogowski
Sieć przepływowa
Przykład sieci przepływowej:
Liczby przy krawędziach są wartościami przepustowości wzdłuż
tych krawędzi.
Jacek Rogowski
Sieć przepływowa
Przykład sieci przepływowej:
Liczby przy krawędziach są wartościami przepustowości wzdłuż
tych krawędzi.
Jacek Rogowski
Przepływ w sieci
Definicja
Przepływem w sieci przepływowej (G , c) nazywamy każdą funkcję
f : V × V → R spełniającą następujące warunki:
1
warunek nieujemności:
∀
u, v ∈V
(u, v ) ∈ E ⇒ f (u, v ) 0,
2
warunek przepustowości:
∀
u, v ∈V
f (u, v ) ¬ c(u, v ),
3
warunek skośnej symetrii:
∀
u, v ∈V
f (u, v ) = −f (v , u),
4
warunek zachowania przepływu:
∀
u∈V \{s, t}
X
v ∈V
f (u, v ) = 0.
Jacek Rogowski
Przepływ w sieci
Definicja
Przepływem w sieci przepływowej (G , c) nazywamy każdą funkcję
f : V × V → R spełniającą następujące warunki:
1
warunek nieujemności:
∀
u, v ∈V
(u, v ) ∈ E ⇒ f (u, v ) 0,
2
warunek przepustowości:
∀
u, v ∈V
f (u, v ) ¬ c(u, v ),
3
warunek skośnej symetrii:
∀
u, v ∈V
f (u, v ) = −f (v , u),
4
warunek zachowania przepływu:
∀
u∈V \{s, t}
X
v ∈V
f (u, v ) = 0.
Jacek Rogowski
Przepływ w sieci
Definicja
Przepływem w sieci przepływowej (G , c) nazywamy każdą funkcję
f : V × V → R spełniającą następujące warunki:
1
warunek nieujemności:
∀
u, v ∈V
(u, v ) ∈ E ⇒ f (u, v ) 0,
2
warunek przepustowości:
∀
u, v ∈V
f (u, v ) ¬ c(u, v ),
3
warunek skośnej symetrii:
∀
u, v ∈V
f (u, v ) = −f (v , u),
4
warunek zachowania przepływu:
∀
u∈V \{s, t}
X
v ∈V
f (u, v ) = 0.
Jacek Rogowski
Przepływ w sieci
Definicja
Przepływem w sieci przepływowej (G , c) nazywamy każdą funkcję
f : V × V → R spełniającą następujące warunki:
1
warunek nieujemności:
∀
u, v ∈V
(u, v ) ∈ E ⇒ f (u, v ) 0,
2
warunek przepustowości:
∀
u, v ∈V
f (u, v ) ¬ c(u, v ),
3
warunek skośnej symetrii:
∀
u, v ∈V
f (u, v ) = −f (v , u),
4
warunek zachowania przepływu:
∀
u∈V \{s, t}
X
v ∈V
f (u, v ) = 0.
Jacek Rogowski
Przepływ w sieci
Definicja
Przepływem w sieci przepływowej (G , c) nazywamy każdą funkcję
f : V × V → R spełniającą następujące warunki:
1
warunek nieujemności:
∀
u, v ∈V
(u, v ) ∈ E ⇒ f (u, v ) 0,
2
warunek przepustowości:
∀
u, v ∈V
f (u, v ) ¬ c(u, v ),
3
warunek skośnej symetrii:
∀
u, v ∈V
f (u, v ) = −f (v , u),
4
warunek zachowania przepływu:
∀
u∈V \{s, t}
X
v ∈V
f (u, v ) = 0.
Jacek Rogowski
Przepływ w sieci
Definicja
Niech f : V × V → R będzie przepływem w sieci (G , c).
Dla każdej pary (u, v ) ∈ V × V liczbę f (u, v ) nazywamy
przepływem (netto) z wierzchołka u do wierzchołka v .
Liczbę
|f | =
X
v ∈V
f (s, v )
nazywamy wartością przepływu f .
W dalszym ciągu wykażemy, że również
|f | =
X
u∈V
f (u, t).
Jacek Rogowski
Przepływ w sieci
Definicja
Niech f : V × V → R będzie przepływem w sieci (G , c).
Dla każdej pary (u, v ) ∈ V × V liczbę f (u, v ) nazywamy
przepływem (netto) z wierzchołka u do wierzchołka v .
Liczbę
|f | =
X
v ∈V
f (s, v )
nazywamy wartością przepływu f .
W dalszym ciągu wykażemy, że również
|f | =
X
u∈V
f (u, t).
Jacek Rogowski
Przepływ w sieci
Definicja
Niech f : V × V → R będzie przepływem w sieci (G , c).
Dla każdej pary (u, v ) ∈ V × V liczbę f (u, v ) nazywamy
przepływem (netto) z wierzchołka u do wierzchołka v .
Liczbę
|f | =
X
v ∈V
f (s, v )
nazywamy wartością przepływu f .
W dalszym ciągu wykażemy, że również
|f | =
X
u∈V
f (u, t).
Jacek Rogowski
Przepływ w sieci
Definicja
Niech f : V × V → R będzie przepływem w sieci (G , c).
Dla każdej pary (u, v ) ∈ V × V liczbę f (u, v ) nazywamy
przepływem (netto) z wierzchołka u do wierzchołka v .
Liczbę
|f | =
X
v ∈V
f (s, v )
nazywamy wartością przepływu f .
W dalszym ciągu wykażemy, że również
|f | =
X
u∈V
f (u, t).
Jacek Rogowski
Przepływ w sieci
Przykład przepływu w sieci przepływowej:
Zapis a/b przy krawędzi oznacza dodatni przepływ netto o
wartości a wzdłuż krawędzi o przepustowości b.
Pojedyncza liczba przy krawędzi oznacza jej przepustowość —
przepływ wzdłuż tej krawędzi jest równy 0.
Jacek Rogowski
Przepływ w sieci
Przykład przepływu w sieci przepływowej:
Zapis a/b przy krawędzi oznacza dodatni przepływ netto o
wartości a wzdłuż krawędzi o przepustowości b.
Pojedyncza liczba przy krawędzi oznacza jej przepustowość —
przepływ wzdłuż tej krawędzi jest równy 0.
Jacek Rogowski
Przepływ w sieci
Przykład przepływu w sieci przepływowej:
Zapis a/b przy krawędzi oznacza dodatni przepływ netto o
wartości a wzdłuż krawędzi o przepustowości b.
Pojedyncza liczba przy krawędzi oznacza jej przepustowość —
przepływ wzdłuż tej krawędzi jest równy 0.
Jacek Rogowski
Przepływ w sieci
Przykład przepływu w sieci przepływowej:
Zapis a/b przy krawędzi oznacza dodatni przepływ netto o
wartości a wzdłuż krawędzi o przepustowości b.
Pojedyncza liczba przy krawędzi oznacza jej przepustowość
—
przepływ wzdłuż tej krawędzi jest równy 0.
Jacek Rogowski
Przepływ w sieci
Przykład przepływu w sieci przepływowej:
Zapis a/b przy krawędzi oznacza dodatni przepływ netto o
wartości a wzdłuż krawędzi o przepustowości b.
Pojedyncza liczba przy krawędzi oznacza jej przepustowość —
przepływ wzdłuż tej krawędzi jest równy 0.
Jacek Rogowski
Przepływ w sieci
Własność 1
∀
u∈V
f (u, u) = 0.
Istotnie, z warunku skośnej symetrii
(f (u, v ) = −f (v , u))
mamy:
f (u, u) = −f (u, u)
⇒
2f (u, u) = 0.
Własność 2
∀
v ∈V \{s, t}
P
u∈V
f (u, v ) = 0.
Istotnie, z warunku skośnej symetrii mamy, zaś z warunku
zachowania przepływu
X
u∈V
f (u, v ) = −
X
u∈V
f (v , u)
= 0
Jacek Rogowski
Przepływ w sieci
Własność 1
∀
u∈V
f (u, u) = 0.
Istotnie, z warunku skośnej symetrii
(f (u, v ) = −f (v , u))
mamy:
f (u, u) = −f (u, u)
⇒
2f (u, u) = 0.
Własność 2
∀
v ∈V \{s, t}
P
u∈V
f (u, v ) = 0.
Istotnie, z warunku skośnej symetrii mamy, zaś z warunku
zachowania przepływu
X
u∈V
f (u, v ) = −
X
u∈V
f (v , u)
= 0
Jacek Rogowski
Przepływ w sieci
Własność 1
∀
u∈V
f (u, u) = 0.
Istotnie, z warunku skośnej symetrii
(f (u, v ) = −f (v , u))
mamy:
f (u, u)
= −f (u, u)
⇒
2f (u, u) = 0.
Własność 2
∀
v ∈V \{s, t}
P
u∈V
f (u, v ) = 0.
Istotnie, z warunku skośnej symetrii mamy, zaś z warunku
zachowania przepływu
X
u∈V
f (u, v ) = −
X
u∈V
f (v , u)
= 0
Jacek Rogowski
Przepływ w sieci
Własność 1
∀
u∈V
f (u, u) = 0.
Istotnie, z warunku skośnej symetrii
(f (u, v ) = −f (v , u))
mamy:
f (u, u) = −f (u, u)
⇒
2f (u, u) = 0.
Własność 2
∀
v ∈V \{s, t}
P
u∈V
f (u, v ) = 0.
Istotnie, z warunku skośnej symetrii mamy, zaś z warunku
zachowania przepływu
X
u∈V
f (u, v ) = −
X
u∈V
f (v , u)
= 0
Jacek Rogowski
Przepływ w sieci
Własność 1
∀
u∈V
f (u, u) = 0.
Istotnie, z warunku skośnej symetrii
(f (u, v ) = −f (v , u))
mamy:
f (u, u) = −f (u, u)
⇒
2f (u, u) = 0.
Własność 2
∀
v ∈V \{s, t}
P
u∈V
f (u, v ) = 0.
Istotnie, z warunku skośnej symetrii mamy, zaś z warunku
zachowania przepływu
X
u∈V
f (u, v ) = −
X
u∈V
f (v , u)
= 0
Jacek Rogowski
Przepływ w sieci
Własność 1
∀
u∈V
f (u, u) = 0.
Istotnie, z warunku skośnej symetrii
(f (u, v ) = −f (v , u))
mamy:
f (u, u) = −f (u, u)
⇒
2f (u, u) = 0.
Własność 2
∀
v ∈V \{s, t}
P
u∈V
f (u, v ) = 0.
Istotnie, z warunku skośnej symetrii mamy, zaś z warunku
zachowania przepływu
X
u∈V
f (u, v ) = −
X
u∈V
f (v , u)
= 0
Jacek Rogowski
Przepływ w sieci
Własność 1
∀
u∈V
f (u, u) = 0.
Istotnie, z warunku skośnej symetrii
(f (u, v ) = −f (v , u))
mamy:
f (u, u) = −f (u, u)
⇒
2f (u, u) = 0.
Własność 2
∀
v ∈V \{s, t}
P
u∈V
f (u, v ) = 0.
Istotnie, z warunku skośnej symetrii mamy
, zaś z warunku
zachowania przepływu
X
u∈V
f (u, v ) = −
X
u∈V
f (v , u)
= 0
Jacek Rogowski
Przepływ w sieci
Własność 1
∀
u∈V
f (u, u) = 0.
Istotnie, z warunku skośnej symetrii
(f (u, v ) = −f (v , u))
mamy:
f (u, u) = −f (u, u)
⇒
2f (u, u) = 0.
Własność 2
∀
v ∈V \{s, t}
P
u∈V
f (u, v ) = 0.
Istotnie, z warunku skośnej symetrii mamy, zaś z warunku
zachowania przepływu
X
u∈V
f (u, v ) = −
X
u∈V
f (v , u) = 0
Jacek Rogowski
Przepływ w sieci
Własność 3
Jeżeli u, v ∈ V oraz (u, v ) 6∈ E i (v , u) 6∈ E , to
f (u, v ) = f (v , u) = 0.
Istotnie, skoro
(u, v ) 6∈ E
oraz
(v , u) 6∈ E ,
to
c(u, v ) = 0
oraz
c(v , u) = 0.
Stąd
f (u, v ) ¬ c(u, v ) = 0
oraz
f (u, v ) = −f (v , u) −c(v , u) = 0
Ponadto
f (v , u) = −f (u, v ) = 0.
Jacek Rogowski
Przepływ w sieci
Własność 3
Jeżeli u, v ∈ V oraz (u, v ) 6∈ E i (v , u) 6∈ E , to
f (u, v ) = f (v , u) = 0.
Istotnie, skoro
(u, v ) 6∈ E
oraz
(v , u) 6∈ E ,
to
c(u, v ) = 0
oraz
c(v , u) = 0.
Stąd
f (u, v ) ¬ c(u, v ) = 0
oraz
f (u, v ) = −f (v , u) −c(v , u) = 0
Ponadto
f (v , u) = −f (u, v ) = 0.
Jacek Rogowski
Przepływ w sieci
Własność 3
Jeżeli u, v ∈ V oraz (u, v ) 6∈ E i (v , u) 6∈ E , to
f (u, v ) = f (v , u) = 0.
Istotnie, skoro
(u, v ) 6∈ E
oraz
(v , u) 6∈ E ,
to
c(u, v ) = 0
oraz
c(v , u) = 0.
Stąd
f (u, v ) ¬ c(u, v ) = 0
oraz
f (u, v ) = −f (v , u) −c(v , u) = 0
Ponadto
f (v , u) = −f (u, v ) = 0.
Jacek Rogowski
Przepływ w sieci
Własność 3
Jeżeli u, v ∈ V oraz (u, v ) 6∈ E i (v , u) 6∈ E , to
f (u, v ) = f (v , u) = 0.
Istotnie, skoro
(u, v ) 6∈ E
oraz
(v , u) 6∈ E ,
to
c(u, v ) = 0
oraz
c(v , u) = 0.
Stąd
f (u, v ) ¬ c(u, v ) = 0
oraz
f (u, v ) = −f (v , u) −c(v , u) = 0
Ponadto
f (v , u) = −f (u, v ) = 0.
Jacek Rogowski
Przepływ w sieci
Własność 3
Jeżeli u, v ∈ V oraz (u, v ) 6∈ E i (v , u) 6∈ E , to
f (u, v ) = f (v , u) = 0.
Istotnie, skoro
(u, v ) 6∈ E
oraz
(v , u) 6∈ E ,
to
c(u, v ) = 0
oraz
c(v , u) = 0.
Stąd
f (u, v ) ¬ c(u, v ) = 0
oraz
f (u, v ) = −f (v , u) −c(v , u) = 0
Ponadto
f (v , u) = −f (u, v ) = 0.
Jacek Rogowski
Przepływ w sieci
Własność 3
Jeżeli u, v ∈ V oraz (u, v ) 6∈ E i (v , u) 6∈ E , to
f (u, v ) = f (v , u) = 0.
Istotnie, skoro
(u, v ) 6∈ E
oraz
(v , u) 6∈ E ,
to
c(u, v ) = 0
oraz
c(v , u) = 0.
Stąd
f (u, v ) ¬ c(u, v ) = 0
oraz
f (u, v ) = −f (v , u) −c(v , u) = 0
Ponadto
f (v , u) = −f (u, v ) = 0.
Jacek Rogowski
Przepływ w sieci
Własność 4
Dla v 6∈ {s, t}:
X
u∈V
f (u,v )>0
f (u, v ) =
X
u∈V
f (v ,u)>0
f (v , u)
Istotnie, dla v ∈ V \ {s, t} mamy:
0 =
X
u∈V
f (u, v ) =
=
X
u∈V
f (u,v )>0
f (u, v ) +
X
u∈V
f (u,v )<0
f (u, v ) =
=
X
u∈V
f (u,v )>0
f (u, v ) −
X
u∈V
f (u,v )<0
f (v , u) =
=
X
u∈V
f (u,v )>0
f (u, v ) −
X
u∈V
f (v ,u)>0
f (v , u).
Jacek Rogowski
Przepływ w sieci
Własność 4
Dla v 6∈ {s, t}:
X
u∈V
f (u,v )>0
f (u, v ) =
X
u∈V
f (v ,u)>0
f (v , u)
Istotnie, dla v ∈ V \ {s, t} mamy:
0 =
X
u∈V
f (u, v ) =
=
X
u∈V
f (u,v )>0
f (u, v ) +
X
u∈V
f (u,v )<0
f (u, v ) =
=
X
u∈V
f (u,v )>0
f (u, v ) −
X
u∈V
f (u,v )<0
f (v , u) =
=
X
u∈V
f (u,v )>0
f (u, v ) −
X
u∈V
f (v ,u)>0
f (v , u).
Jacek Rogowski
Przepływ w sieci
Własność 4
Dla v 6∈ {s, t}:
X
u∈V
f (u,v )>0
f (u, v ) =
X
u∈V
f (v ,u)>0
f (v , u)
Istotnie, dla v ∈ V \ {s, t} mamy:
0 =
X
u∈V
f (u, v )
=
=
X
u∈V
f (u,v )>0
f (u, v ) +
X
u∈V
f (u,v )<0
f (u, v ) =
=
X
u∈V
f (u,v )>0
f (u, v ) −
X
u∈V
f (u,v )<0
f (v , u) =
=
X
u∈V
f (u,v )>0
f (u, v ) −
X
u∈V
f (v ,u)>0
f (v , u).
Jacek Rogowski
Przepływ w sieci
Własność 4
Dla v 6∈ {s, t}:
X
u∈V
f (u,v )>0
f (u, v ) =
X
u∈V
f (v ,u)>0
f (v , u)
Istotnie, dla v ∈ V \ {s, t} mamy:
0 =
X
u∈V
f (u, v ) =
=
X
u∈V
f (u,v )>0
f (u, v ) +
X
u∈V
f (u,v )<0
f (u, v )
=
=
X
u∈V
f (u,v )>0
f (u, v ) −
X
u∈V
f (u,v )<0
f (v , u) =
=
X
u∈V
f (u,v )>0
f (u, v ) −
X
u∈V
f (v ,u)>0
f (v , u).
Jacek Rogowski
Przepływ w sieci
Własność 4
Dla v 6∈ {s, t}:
X
u∈V
f (u,v )>0
f (u, v ) =
X
u∈V
f (v ,u)>0
f (v , u)
Istotnie, dla v ∈ V \ {s, t} mamy:
0 =
X
u∈V
f (u, v ) =
=
X
u∈V
f (u,v )>0
f (u, v ) +
X
u∈V
f (u,v )<0
f (u, v ) =
=
X
u∈V
f (u,v )>0
f (u, v ) −
X
u∈V
f (u,v )<0
f (v , u)
=
=
X
u∈V
f (u,v )>0
f (u, v ) −
X
u∈V
f (v ,u)>0
f (v , u).
Jacek Rogowski
Przepływ w sieci
Własność 4
Dla v 6∈ {s, t}:
X
u∈V
f (u,v )>0
f (u, v ) =
X
u∈V
f (v ,u)>0
f (v , u)
Istotnie, dla v ∈ V \ {s, t} mamy:
0 =
X
u∈V
f (u, v ) =
=
X
u∈V
f (u,v )>0
f (u, v ) +
X
u∈V
f (u,v )<0
f (u, v ) =
=
X
u∈V
f (u,v )>0
f (u, v ) −
X
u∈V
f (u,v )<0
f (v , u) =
=
X
u∈V
f (u,v )>0
f (u, v ) −
X
u∈V
f (v ,u)>0
f (v , u).
Jacek Rogowski
Problem maksymalnego przepływu w sieci
Problem:
Dla danej sieci przepływowej (G , c) należy znaleźć przepływ o
maksymalnej wartości.
Wprowadźmy następujące oznaczenia:
N
−
(u) — zbiór wszystkich wierzchołków, które są początkami
krawędzi o końcu w wierzchołku u,
N
+
(u) — zbiór wszystkich wierzchołków, które są końcami
krawędzi o początku w wierzchołku u,
x
uv
=
(
f (u, v ),
gdy
(u, v ) ∈ E ,
0,
gdy
(u, v ) 6∈ E .
Oczywiście
X
u∈N
−
(v )
x
uv
=
X
u∈V
f (u,v )>0
f (u, v )
i
X
u∈N
+
(v )
x
vu
=
X
u∈V
f (v ,u)>0
f (v , u).
Jacek Rogowski
Problem maksymalnego przepływu w sieci
Problem:
Dla danej sieci przepływowej (G , c) należy znaleźć przepływ o
maksymalnej wartości.
Wprowadźmy następujące oznaczenia:
N
−
(u) — zbiór wszystkich wierzchołków, które są początkami
krawędzi o końcu w wierzchołku u,
N
+
(u) — zbiór wszystkich wierzchołków, które są końcami
krawędzi o początku w wierzchołku u,
x
uv
=
(
f (u, v ),
gdy
(u, v ) ∈ E ,
0,
gdy
(u, v ) 6∈ E .
Oczywiście
X
u∈N
−
(v )
x
uv
=
X
u∈V
f (u,v )>0
f (u, v )
i
X
u∈N
+
(v )
x
vu
=
X
u∈V
f (v ,u)>0
f (v , u).
Jacek Rogowski
Problem maksymalnego przepływu w sieci
Problem:
Dla danej sieci przepływowej (G , c) należy znaleźć przepływ o
maksymalnej wartości.
Wprowadźmy następujące oznaczenia:
N
−
(u) — zbiór wszystkich wierzchołków, które są początkami
krawędzi o końcu w wierzchołku u,
N
+
(u) — zbiór wszystkich wierzchołków, które są końcami
krawędzi o początku w wierzchołku u,
x
uv
=
(
f (u, v ),
gdy
(u, v ) ∈ E ,
0,
gdy
(u, v ) 6∈ E .
Oczywiście
X
u∈N
−
(v )
x
uv
=
X
u∈V
f (u,v )>0
f (u, v )
i
X
u∈N
+
(v )
x
vu
=
X
u∈V
f (v ,u)>0
f (v , u).
Jacek Rogowski
Problem maksymalnego przepływu w sieci
Problem:
Dla danej sieci przepływowej (G , c) należy znaleźć przepływ o
maksymalnej wartości.
Wprowadźmy następujące oznaczenia:
N
−
(u) — zbiór wszystkich wierzchołków, które są początkami
krawędzi o końcu w wierzchołku u,
N
+
(u) — zbiór wszystkich wierzchołków, które są końcami
krawędzi o początku w wierzchołku u,
x
uv
=
(
f (u, v ),
gdy
(u, v ) ∈ E ,
0,
gdy
(u, v ) 6∈ E .
Oczywiście
X
u∈N
−
(v )
x
uv
=
X
u∈V
f (u,v )>0
f (u, v )
i
X
u∈N
+
(v )
x
vu
=
X
u∈V
f (v ,u)>0
f (v , u).
Jacek Rogowski
Problem maksymalnego przepływu w sieci
Problem:
Dla danej sieci przepływowej (G , c) należy znaleźć przepływ o
maksymalnej wartości.
Wprowadźmy następujące oznaczenia:
N
−
(u) — zbiór wszystkich wierzchołków, które są początkami
krawędzi o końcu w wierzchołku u,
N
+
(u) — zbiór wszystkich wierzchołków, które są końcami
krawędzi o początku w wierzchołku u,
x
uv
=
(
f (u, v ),
gdy
(u, v ) ∈ E ,
0,
gdy
(u, v ) 6∈ E .
Oczywiście
X
u∈N
−
(v )
x
uv
=
X
u∈V
f (u,v )>0
f (u, v )
i
X
u∈N
+
(v )
x
vu
=
X
u∈V
f (v ,u)>0
f (v , u).
Jacek Rogowski
Problem maksymalnego przepływu w sieci
Problem:
Dla danej sieci przepływowej (G , c) należy znaleźć przepływ o
maksymalnej wartości.
Wprowadźmy następujące oznaczenia:
N
−
(u) — zbiór wszystkich wierzchołków, które są początkami
krawędzi o końcu w wierzchołku u,
N
+
(u) — zbiór wszystkich wierzchołków, które są końcami
krawędzi o początku w wierzchołku u,
x
uv
=
(
f (u, v ),
gdy
(u, v ) ∈ E ,
0,
gdy
(u, v ) 6∈ E .
Oczywiście
X
u∈N
−
(v )
x
uv
=
X
u∈V
f (u,v )>0
f (u, v )
i
X
u∈N
+
(v )
x
vu
=
X
u∈V
f (v ,u)>0
f (v , u).
Jacek Rogowski
Problem maksymalnego przepływu w sieci
Problem:
Dla danej sieci przepływowej (G , c) należy znaleźć przepływ o
maksymalnej wartości.
Wprowadźmy następujące oznaczenia:
N
−
(u) — zbiór wszystkich wierzchołków, które są początkami
krawędzi o końcu w wierzchołku u,
N
+
(u) — zbiór wszystkich wierzchołków, które są końcami
krawędzi o początku w wierzchołku u,
x
uv
=
(
f (u, v ),
gdy
(u, v ) ∈ E ,
0,
gdy
(u, v ) 6∈ E .
Oczywiście
X
u∈N
−
(v )
x
uv
=
X
u∈V
f (u,v )>0
f (u, v )
i
X
u∈N
+
(v )
x
vu
=
X
u∈V
f (v ,u)>0
f (v , u).
Jacek Rogowski
Problem maksymalnego przepływu w sieci
Problem:
Dla danej sieci przepływowej (G , c) należy znaleźć przepływ o
maksymalnej wartości.
Wprowadźmy następujące oznaczenia:
N
−
(u) — zbiór wszystkich wierzchołków, które są początkami
krawędzi o końcu w wierzchołku u,
N
+
(u) — zbiór wszystkich wierzchołków, które są końcami
krawędzi o początku w wierzchołku u,
x
uv
=
(
f (u, v ),
gdy
(u, v ) ∈ E ,
0,
gdy
(u, v ) 6∈ E .
Oczywiście
X
u∈N
−
(v )
x
uv
=
X
u∈V
f (u,v )>0
f (u, v )
i
X
u∈N
+
(v )
x
vu
=
X
u∈V
f (v ,u)>0
f (v , u).
Jacek Rogowski
Formalizacja problemu maksymalnego przepływu
Funkcja celu:
|f | → max
Ograniczenia:
X
u∈N
−
(v )
x
uv
=
X
w ∈N
+
(v )
x
vw
dla
v ∈ V \ {s, t},
X
v ∈N
+
(s)
x
sv
= |f |,
X
u∈N
−
(t)
x
ut
= |f |,
x
uv
¬ c(u, v )
dla
(u, v ) ∈ V × V .
Warunki brzegowe:
x
uv
0
dla
(u, v ) ∈ V × V .
Jacek Rogowski
Formalizacja problemu maksymalnego przepływu
Funkcja celu:
|f | → max
Ograniczenia:
X
u∈N
−
(v )
x
uv
=
X
w ∈N
+
(v )
x
vw
dla
v ∈ V \ {s, t},
X
v ∈N
+
(s)
x
sv
= |f |,
X
u∈N
−
(t)
x
ut
= |f |,
x
uv
¬ c(u, v )
dla
(u, v ) ∈ V × V .
Warunki brzegowe:
x
uv
0
dla
(u, v ) ∈ V × V .
Jacek Rogowski
Formalizacja problemu maksymalnego przepływu
Funkcja celu:
|f | → max
Ograniczenia:
X
u∈N
−
(v )
x
uv
=
X
w ∈N
+
(v )
x
vw
dla
v ∈ V \ {s, t},
X
v ∈N
+
(s)
x
sv
= |f |,
X
u∈N
−
(t)
x
ut
= |f |,
x
uv
¬ c(u, v )
dla
(u, v ) ∈ V × V .
Warunki brzegowe:
x
uv
0
dla
(u, v ) ∈ V × V .
Jacek Rogowski
Formalizacja problemu maksymalnego przepływu
Funkcja celu:
|f | → max
Ograniczenia:
X
u∈N
−
(v )
x
uv
=
X
w ∈N
+
(v )
x
vw
dla
v ∈ V \ {s, t},
X
v ∈N
+
(s)
x
sv
= |f |,
X
u∈N
−
(t)
x
ut
= |f |,
x
uv
¬ c(u, v )
dla
(u, v ) ∈ V × V .
Warunki brzegowe:
x
uv
0
dla
(u, v ) ∈ V × V .
Jacek Rogowski
Formalizacja problemu maksymalnego przepływu
Funkcja celu:
|f | → max
Ograniczenia:
X
u∈N
−
(v )
x
uv
=
X
w ∈N
+
(v )
x
vw
dla
v ∈ V \ {s, t},
X
v ∈N
+
(s)
x
sv
= |f |,
X
u∈N
−
(t)
x
ut
= |f |,
x
uv
¬ c(u, v )
dla
(u, v ) ∈ V × V .
Warunki brzegowe:
x
uv
0
dla
(u, v ) ∈ V × V .
Jacek Rogowski
Formalizacja problemu maksymalnego przepływu
Funkcja celu:
|f | → max
Ograniczenia:
X
u∈N
−
(v )
x
uv
=
X
w ∈N
+
(v )
x
vw
dla
v ∈ V \ {s, t},
X
v ∈N
+
(s)
x
sv
= |f |,
X
u∈N
−
(t)
x
ut
= |f |,
x
uv
¬ c(u, v )
dla
(u, v ) ∈ V × V .
Warunki brzegowe:
x
uv
0
dla
(u, v ) ∈ V × V .
Jacek Rogowski
Formalizacja problemu maksymalnego przepływu
Funkcja celu:
|f | → max
Ograniczenia:
X
u∈N
−
(v )
x
uv
=
X
w ∈N
+
(v )
x
vw
dla
v ∈ V \ {s, t},
X
v ∈N
+
(s)
x
sv
= |f |,
X
u∈N
−
(t)
x
ut
= |f |,
x
uv
¬ c(u, v )
dla
(u, v ) ∈ V × V .
Warunki brzegowe:
x
uv
0
dla
(u, v ) ∈ V × V .
Jacek Rogowski
Formalizacja problemu maksymalnego przepływu
Funkcja celu:
|f | → max
Ograniczenia:
X
u∈N
−
(v )
x
uv
=
X
w ∈N
+
(v )
x
vw
dla
v ∈ V \ {s, t},
X
v ∈N
+
(s)
x
sv
= |f |,
X
u∈N
−
(t)
x
ut
= |f |,
x
uv
¬ c(u, v )
dla
(u, v ) ∈ V × V .
Warunki brzegowe:
x
uv
0
dla
(u, v ) ∈ V × V .
Jacek Rogowski