Z Wikipedii, wolnej encyklopedii
Sieć przepływowa
G
(
V
,
E
)
{\displaystyle G(V,E)}
graf skierowany , w którym każda krawędź
(
u
,
v
)
{\displaystyle (u,v)}
E
{\displaystyle E}
c
(
u
,
v
)
⩾
0.
{\displaystyle c(u,v)\geqslant 0.}
s
{\displaystyle s}
t
.
{\displaystyle t.}
Przepływem w sieci
G
{\displaystyle G}
f
:
V
×
V
→
R
{\displaystyle f\colon V\times V\to R}
warunek przepustowości: dla wszystkich krawędzi
(
u
,
v
)
∈
E
{\displaystyle (u,v)\in E}
f
(
u
,
v
)
⩽
c
(
u
,
v
)
,
{\displaystyle f(u,v)\leqslant c(u,v),}
warunek skośnej symetryczności: dla wszystkich krawędzi
(
u
,
v
)
∈
E
{\displaystyle (u,v)\in E}
f
(
u
,
v
)
=
−
f
(
v
,
u
)
,
{\displaystyle f(u,v)=-f(v,u),}
warunek zachowania przepływu: dla każdego
u
∈
V
∖
{
s
,
t
}
{\displaystyle u\in V\setminus \{s,t\}}
∑
v
∈
V
f
(
v
,
u
)
=
∑
v
∈
V
f
(
u
,
v
)
.
{\displaystyle \sum _{v\in V}f(v,u)=\sum _{v\in V}f(u,v).}
Przepływ netto to wartość
f
(
u
,
v
)
{\displaystyle f(u,v)}
u
{\displaystyle u}
v
.
{\displaystyle v.}
