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
Wyszukiwarka
Podobne podstrony:
Wyklad 04 2014 2015
BOwL wyklad 03 Beamer 2014
BOwL wyklad 01 Beamer 2014
BOwL wyklad 02 Beamer 2014
Wyklad 04 2014 2015
sedymentologia wykład" 04 2015
POP wykład 04 2015
Sedymentologia wykład 6 8 04 2015
Wykład 04
Wyklad 04
biofizyka wyklad 04
Gwinty, wyklad 04 polaczenia srubowe CRC A717D1E6
Prawo konkurencji wykład 7 - 04.12, WPiA UŁ, Prawo ochrony konkurencji i konsumentów (T. Ławicki)
Młoda Polska WYKŁAD (04 06 2014)
Fundusze inwestycyjne i emerytalne wykład 6 23 03 2015
Podstawy Systemów Okrętowych wykład 04 Przeciw Pożarnicze
msg ce wyklad 04
DSP Wyk%b3ad 04 UWM
Wykład 2.04, I rok, BPZ
więcej podobnych podstron