- Definition:
Basic Network
- basic network =
a directed graph N
with the following properties:
- Graph N has
exactly one source node
- Source node = a node with
0 (zero) in-degree edges
- Source node = a node with
0 (zero) in-degree edges
- Graph N has
exactly one sink node
- Sink node =
a node with
0 (zero) out-degree edges
- Sink node =
a node with
0 (zero) out-degree edges
- Each edge e of N
has a positive capacity c(e)
- c(e) = the maximum amount of commodity that can flow through the edge e in a given time
- Graph N has
exactly one source node
- basic network =
a directed graph N
with the following properties:
- Example:
- Definition: flow
- Flow = an
assignment f(e) to
each edge e of the network that satisfies:
- The feasibility condition:
- f(e) ≤ c(e)
I.e.: flow on an edge cannot exceed the capacity of the edge
- The flow conservation law:
Total flow going into node x = Total flow going out from node xNote:
- The source node and the sink node are except from the flow conservation law !!!
- The feasibility condition:
- Flow = an
assignment f(e) to
each edge e of the network that satisfies:
- Example:
It represents the following transportation of a commodity:
- Saturated edge
- An edge e
is saturated if:
f(e) = c(e) (flow through edge = capacity of edge)
Example:
- An edge e
is saturated if:
- Unsaturated edge
- An edge e
is unsaturated if:
f(e) < c(e) (flow through edge = capacity of edge)
- An edge e
is unsaturated if:
- Maximum flow problem:
- For a given basic network, find a flow of the largest possible value from the source node S to sink node T