VL 03: Flows in Networks Flashcards
How does the Adjacency Matrix look like?
- [n x n] matrix
- Specifies which nodes i and j are linked
- Entries are binary {0,1}
- There is a reading direction (column to row)
How does the Incidence Matrix look like?
- [n x m] matrix
- hiej specifies which edge ej is linked with node i
- Entries are {-1,0,1} (-1 node is ending point, 1 node is staring point, 0 otherwise)
True or false?
The Adjacency and the Incidence Matrix contain the same information.
True!
How do the degree functions deg(i), outdeg(i), indeg(i) work?
deg(i): number of edges connected to node i
outdeg(i): number of edges going out of node i
indeg(i): number of edges going into node i
What is a walk?
- walk (“Kette”)
- Is a certain connection from node i to node j which may goes over certain nodes and edges
- Nodes and edges may be travelled more than once
What is a trail?
- trail (“Pfad”)
- It is a walk in which no edge is travelled more than once
What is a path?
- path (“Weg”)
- It is a trail in which no edge and no node is travelled more than once
What is a cycle?
- cycle/circuit (“Kreis”)
- It is a trail with identical start- and ending point
- Trail: no edge is travelled more than once
Flow conditions
Which conditions have to be satisfied by the raw flow function g(e)?
The raw flow function g(e) satisfies the following constraints:
1) Flow conservation/mass balance
- -> applies to all the nodes except the source/sink
2) Capacity contraints
- -> g(e) <= u(e); for all e
compare s. 6
Flow conditions
Which conditions have to be satisfied by the net flow function f(i,j)?
compare s. 6
–> net flow function definition
–> the net flow is antisymmetric, f(i,j) = -f(j,i)
ATTENTION: These conditions are not needed when using net flows in GAMS! In GAMS you only need the conditions given on s. 16
True or false?
Every trail is a path.
False!
Every path is a trail.
- -> A Trail is a walk in which no edge is travelled more than once.
- -> A path is a walk in which no edge and no node is travelled more than once.
What is the Max Flow Min Cut Theorem?
Cut
- -> Cuts the network in two parts
- -> One part contains the source, the other one contains the sink
Max Flow Min Cut Theorem
- If:
- -> There is a cut of G with capacity |f| or
- -> There is a cut with no augmenting path in the residual network
- Then:
- -> f is a maximum flow of G
Formulate the Max Flow Problem with the Raw Flow Function as a LP.
compare s. 15
Formulate the Max Flow Problem with the Net Flow Function as a LP.
compare s. 16
What is the goal of the Ford Fulkerson Algorithm?
The Ford Fulkerson Algorithm either shows that the max. flow is already found or it finds an augmenting path.
How do you implement super sources and super sinks
- Link the super source to all sources by adding edges with unlimited capacity and costs of 0.
(analog for super sinks)
What is the Minimum Cost Flow Problem used for?
Finding the cost-minimizing flow option for a given injection/flow.
The given injection/flow is specified by the parameter b(i).
Set the Minimum Cost Flow Problem.
Compare s. 21-22
What is the max flow problem as min cost flow problem used for?
Finding the max. flow.
Set the Max Flow Problem as Min Cost Flow Problem.
Compare s. 22-23
How does the Ford-Fulkerson Algorithm work?
1) Start at the s and label all nodes with positive residual flow (+,predecessor-node)
- -> If you reach t –> There is an augmenting path
- -> If you don’t reach t –> Max flow is found
If t was reached:
2) Move backwards from t and label all edges with positiv residual flow e(i,j) = remaining capacity
- -> The augmenting path from s to t is min(e(i,j))
