Nächste Seite:
Das Maximalfluß-Problem
Aufwärts:
Flüsse
Vorherige Seite:
Definitionen: Netzwerke
Definitionen: Flüsse
Für
f
:
E
(
G
)
0
und
x
V
(
G
)
schreibe
f
+
(
y
) =
{
f
(
xy
) |
x
In(
y
)}
,
f
-
(
x
) =
{
f
(
xy
) |
y
Out(
y
)}
,
f
(
x
) =
f
+
(
x
) -
f
-
(
x
)
.
f
:
E
(
G
)
0
heißt
zulässiger Fluß
, wenn
e
E
(
G
) : 0
f
(
e
)
c
(
e
)
x
V
(
G
)
{
q
,
s
} :
f
(
x
) = 0
.
Johannes Waldmann 2005-01-25