VL 03: Flows in Networks

Question 1

How does the Adjacency Matrix look like?

Answer 1

• [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)

Question 2

How does the Incidence Matrix look like?

Answer 2

• [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)

Question 3

True or false?

The Adjacency and the Incidence Matrix contain the same information.

Answer 3

True!

Question 4

How do the degree functions deg(i), outdeg(i), indeg(i) work?

Answer 4

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

Question 5

What is a walk?

Answer 5

• 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

Question 6

What is a trail?

Answer 6

• trail (“Pfad”)

- It is a walk in which no edge is travelled more than once

Question 7

What is a path?

Answer 7

• path (“Weg”)

- It is a trail in which no edge and no node is travelled more than once

Question 8

What is a cycle?

Answer 8

• cycle/circuit (“Kreis”)
• It is a trail with identical start- and ending point
• Trail: no edge is travelled more than once

Question 9

Flow conditions

Which conditions have to be satisfied by the raw flow function g(e)?

Answer 9

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

Question 10

Flow conditions

Which conditions have to be satisfied by the net flow function f(i,j)?

Answer 10

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

Question 11

True or false?

Every trail is a path.

Answer 11

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.

Question 12

What is the Max Flow Min Cut Theorem?

Answer 12

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

Question 13

Formulate the Max Flow Problem with the Raw Flow Function as a LP.

Answer 13

compare s. 15

Question 14

Formulate the Max Flow Problem with the Net Flow Function as a LP.

Answer 14

compare s. 16

Question 15

What is the goal of the Ford Fulkerson Algorithm?

Answer 15

The Ford Fulkerson Algorithm either shows that the max. flow is already found or it finds an augmenting path.

Question 16

How do you implement super sources and super sinks

Answer 16

• Link the super source to all sources by adding edges with unlimited capacity and costs of 0.

(analog for super sinks)

Question 17

What is the Minimum Cost Flow Problem used for?

Answer 17

Finding the cost-minimizing flow option for a given injection/flow.

The given injection/flow is specified by the parameter b(i).

Question 18

Set the Minimum Cost Flow Problem.

Answer 18

Compare s. 21-22

Question 19

What is the max flow problem as min cost flow problem used for?

Answer 19

Finding the max. flow.

Question 20

Set the Max Flow Problem as Min Cost Flow Problem.

Answer 20

Compare s. 22-23

Question 21

How does the Ford-Fulkerson Algorithm work?

Answer 21

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))