Badania Operacyjne w Logistyce
Wykład 4
Sieci przepływowe
Jacek Rogowski
Instytut Matematyki
Politechnika A
ódzka
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Definicja
Grafem skierowanym nazywamy parę (V , E), w której:
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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,
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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 ;
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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,
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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 BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Definicja
Niech G = (V , E) będzie grafem skierowanym.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Definicja
Niech G = (V , E) będzie grafem skierowanym.Wierzchołek w " V
nazywamy
z
ródłem, jeżeli jest początkiem każdej krawędzi, do której
należy,
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Definicja
Niech G = (V , E) będzie grafem skierowanym.Wierzchołek w " V
nazywamy
z
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.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Definicja
Niech G = (V , E) będzie grafem skierowanym.Wierzchołek w " V
nazywamy
z
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 z
ródła s do ujścia t w grafie skierowanym
G = (V , E) nazywamy każdy ciąg krawędzi postaci:
(v0, v1), (v1, v2), . . . , (vn-1, vn),
w którym v0 = s i vn = t.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Definicja
Niech G = (V , E) będzie grafem skierowanym.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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:
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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 z
ródło,
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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 z
ródło,
w grafie G istnieje dokładnie jedno ujście,
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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 z
ródło,
w grafie G istnieje dokładnie jedno ujście,
graf G jest spójny,
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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 z
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 z
ródła s do ujścia t.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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 z
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 z
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 BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Definicja
Niech G = (V , E, s, t) będzie siecią ze z
ródłem s i ujściem t.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Definicja
Niech G = (V , E, s, t) będzie siecią ze z
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:
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Definicja
Niech G = (V , E, s, t) będzie siecią ze z
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 ,
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Definicja
Niech G = (V , E, s, t) będzie siecią ze z
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) " E Ò! c(u, v) = 0.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Definicja
Niech G = (V , E, s, t) będzie siecią ze z
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) " E Ò! c(u, v) = 0.
Jeżeli c jest przepustowością w sieci G, to parę (G, c) nazywamy
siecią przepływową.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Definicja
Niech G = (V , E, s, t) będzie siecią ze z
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) " 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,
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Definicja
Niech G = (V , E, s, t) będzie siecią ze z
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) " 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.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Definicja
Niech G = (V , E, s, t) będzie siecią ze z
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) " 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
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Definicja
Niech G = (V , E, s, t) będzie siecią ze z
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) " 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 BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Przykład sieci przepływowej:
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Przykład sieci przepływowej:
Liczby przy krawędziach są wartościami przepustowości wzdłuż
tych krawędzi.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Sieć przepływowa
Przykład sieci przepływowej:
Liczby przy krawędziach są wartościami przepustowości wzdłuż
tych krawędzi.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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:
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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,
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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),
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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),
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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} f (u, v) = 0.
v"V
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Definicja
Niech f : V × V R bÄ™dzie przepÅ‚ywem w sieci (G, c).
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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 | = f (s, v)
v"V
nazywamy wartością przepływu f .
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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 | = f (s, v)
v"V
nazywamy wartością przepływu f .
W dalszym ciągu wykażemy, że również

|f | = f (u, t).
u"V
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Przykład przepływu w sieci przepływowej:
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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ść
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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 BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 1
"u"V f (u, u) = 0.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 1
"u"V f (u, u) = 0.
Istotnie, z warunku skośnej symetrii
mamy:
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 1
"u"V f (u, u) = 0.
Istotnie, z warunku skośnej symetrii
mamy:
f (u, u)
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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)
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
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.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 1
"u"V f (u, u) = 0.
Istotnie, z warunku skośnej symetrii
mamy:
f (u, u) = -f (u, u) Ò! 2f (u, u) = 0.
Własność 2

"v"V \{s, t} u"V f (u, v) = 0.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 1
"u"V f (u, u) = 0.
Istotnie, z warunku skośnej symetrii
mamy:
f (u, u) = -f (u, u) Ò! 2f (u, u) = 0.
Własność 2

"v"V \{s, t} u"V f (u, v) = 0.
Istotnie, z warunku skośnej symetrii mamy

f (u, v) = - f (v, u)
u"V u"V
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 1
"u"V f (u, u) = 0.
Istotnie, z warunku skośnej symetrii
mamy:
f (u, u) = -f (u, u) Ò! 2f (u, u) = 0.
Własność 2

"v"V \{s, t} u"V f (u, v) = 0.
Istotnie, z warunku skośnej symetrii mamy, zaś z warunku
zachowania przepływu

f (u, v) = - f (v, u) = 0
u"V u"V
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 3
Jeżeli u, v " V oraz (u, v) " E i (v, u) " E, to
f (u, v) = f (v, u) = 0.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 3
Jeżeli u, v " V oraz (u, v) " E i (v, u) " E, to
f (u, v) = f (v, u) = 0.
Istotnie, skoro
(u, v) " E oraz (v, u) " E ,
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 3
Jeżeli u, v " V oraz (u, v) " E i (v, u) " E, to
f (u, v) = f (v, u) = 0.
Istotnie, skoro
(u, v) " E oraz (v, u) " E ,
to
c(u, v) = 0 oraz c(v, u) = 0.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 3
Jeżeli u, v " V oraz (u, v) " E i (v, u) " E, to
f (u, v) = f (v, u) = 0.
Istotnie, skoro
(u, v) " E oraz (v, u) " E ,
to
c(u, v) = 0 oraz c(v, u) = 0.
StÄ…d
f (u, v) c(u, v) = 0
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 3
Jeżeli u, v " V oraz (u, v) " E i (v, u) " E, to
f (u, v) = f (v, u) = 0.
Istotnie, skoro
(u, v) " E oraz (v, u) " 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
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 3
Jeżeli u, v " V oraz (u, v) " E i (v, u) " E, to
f (u, v) = f (v, u) = 0.
Istotnie, skoro
(u, v) " E oraz (v, u) " 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 BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 4
Dla v " {s, t}:

f (u, v) = f (v, u)
u"V u"V
f (u,v)>0 f (v,u)>0
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 4
Dla v " {s, t}:

f (u, v) = f (v, u)
u"V u"V
f (u,v)>0 f (v,u)>0
Istotnie, dla v " V \ {s, t} mamy:
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 4
Dla v " {s, t}:

f (u, v) = f (v, u)
u"V u"V
f (u,v)>0 f (v,u)>0
Istotnie, dla v " V \ {s, t} mamy:

0 = f (u, v)
u"V
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 4
Dla v " {s, t}:

f (u, v) = f (v, u)
u"V u"V
f (u,v)>0 f (v,u)>0
Istotnie, dla v " V \ {s, t} mamy:

0 = f (u, v) =
u"V

= f (u, v) + f (u, v)
u"V u"V
f (u,v)>0 f (u,v)<0
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 4
Dla v " {s, t}:

f (u, v) = f (v, u)
u"V u"V
f (u,v)>0 f (v,u)>0
Istotnie, dla v " V \ {s, t} mamy:

0 = f (u, v) =
u"V

= f (u, v) + f (u, v) =
u"V u"V
f (u,v)>0 f (u,v)<0

= f (u, v) - f (v, u)
u"V u"V
f (u,v)>0 f (u,v)<0
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Przepływ w sieci
Własność 4
Dla v " {s, t}:

f (u, v) = f (v, u)
u"V u"V
f (u,v)>0 f (v,u)>0
Istotnie, dla v " V \ {s, t} mamy:

0 = f (u, v) =
u"V

= f (u, v) + f (u, v) =
u"V u"V
f (u,v)>0 f (u,v)<0

= f (u, v) - f (v, u) =
u"V u"V
f (u,v)>0 f (u,v)<0

= f (u, v) - f (v, u).
u"V u"V
f (u,v)>0 f (v,u)>0
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Problem maksymalnego przepływu w sieci
Problem:
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Problem maksymalnego przepływu w sieci
Problem:
Dla danej sieci przepływowej (G, c) należy znalez
ć przepływ o
maksymalnej wartości.
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Problem maksymalnego przepływu w sieci
Problem:
Dla danej sieci przepływowej (G, c) należy znalez
ć przepływ o
maksymalnej wartości.
Wprowadz
my następujące oznaczenia:
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Problem maksymalnego przepływu w sieci
Problem:
Dla danej sieci przepływowej (G, c) należy znalez
ć przepływ o
maksymalnej wartości.
Wprowadz
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,
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Problem maksymalnego przepływu w sieci
Problem:
Dla danej sieci przepływowej (G, c) należy znalez
ć przepływ o
maksymalnej wartości.
Wprowadz
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,
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Problem maksymalnego przepływu w sieci
Problem:
Dla danej sieci przepływowej (G, c) należy znalez
ć przepływ o
maksymalnej wartości.
Wprowadz
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,

f (u, v), gdy (u, v) " E ,
xuv =
0, gdy (u, v) " E .
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Problem maksymalnego przepływu w sieci
Problem:
Dla danej sieci przepływowej (G, c) należy znalez
ć przepływ o
maksymalnej wartości.
Wprowadz
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,

f (u, v), gdy (u, v) " E ,
xuv =
0, gdy (u, v) " E .
Oczywiście

xuv = f (u, v)
u"V
u"N-(v)
f (u,v)>0
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Problem maksymalnego przepływu w sieci
Problem:
Dla danej sieci przepływowej (G, c) należy znalez
ć przepływ o
maksymalnej wartości.
Wprowadz
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,

f (u, v), gdy (u, v) " E ,
xuv =
0, gdy (u, v) " E .
Oczywiście

xuv = f (u, v) i xvu = f (v, u).
u"V
u"N-(v) u"N+(v) u"V
f (u,v)>0 f (v,u)>0
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Formalizacja problemu maksymalnego przepływu
Funkcja celu:
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Formalizacja problemu maksymalnego przepływu
Funkcja celu:
|f | max
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Formalizacja problemu maksymalnego przepływu
Funkcja celu:
|f | max
Ograniczenia:
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Formalizacja problemu maksymalnego przepływu
Funkcja celu:
|f | max
Ograniczenia:

xuv = xvw dla v " V \ {s, t},
u"N-(v) w"N+(v)
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Formalizacja problemu maksymalnego przepływu
Funkcja celu:
|f | max
Ograniczenia:

xuv = xvw dla v " V \ {s, t},
u"N-(v) w"N+(v)

xsv = |f |,
v"N+(s)
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Formalizacja problemu maksymalnego przepływu
Funkcja celu:
|f | max
Ograniczenia:

xuv = xvw dla v " V \ {s, t},
u"N-(v) w"N+(v)

xsv = |f |,
v"N+(s)

xut = |f |,
u"N-(t)
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Formalizacja problemu maksymalnego przepływu
Funkcja celu:
|f | max
Ograniczenia:

xuv = xvw dla v " V \ {s, t},
u"N-(v) w"N+(v)

xsv = |f |,
v"N+(s)

xut = |f |,
u"N-(t)
xuv c(u, v) dla (u, v) " V × V .
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe
Formalizacja problemu maksymalnego przepływu
Funkcja celu:
|f | max
Ograniczenia:

xuv = xvw dla v " V \ {s, t},
u"N-(v) w"N+(v)

xsv = |f |,
v"N+(s)

xut = |f |,
u"N-(t)
xuv c(u, v) dla (u, v) " V × V .
Warunki brzegowe:
xuv 0 dla (u, v) " V × V .
Jacek Rogowski BOwL Wykład 4: Sieci przepływowe