(W9) Network Flows

Question 1

What is a Bipartite Graph?

Answer 1

A graph where the vertices can be seperated into two disjoint subsets L and R.

every edge goes from a vertex in L to a vertex in R

Question 2

How to do Bipirtate Matching?

Answer 2

Suppose you want to match a vertex from L to a vertex in R.

This can be sold with the FordFulkerson method

Give each edge a capacity of 1, then run the ford fulkerson method - and inspect the edge to see if the flow is 1

Question 3

What does a circulation of demands graph look like (without modification)

Answer 3

No single source or sink, rather each vertex has a demand

Question 4

What is the meaning of the value of the Demand

Answer 4

• If demand > 0: then it wants to receive x more units of flow in than going out
• If demand = 0: then inbound = outbound
• If demand < 0: then it wants to expel x more units out than coming in

Question 5

What are the two constraints when dealing with Circulation of Demand problems?

Answer 5

1. (Capacity) The flow along an edge must not exceed the capacity of that edge
2. (Demand) Inbound - outbound = demand for each vertex

Question 6

How do you solve a circulation of demands problem

Answer 6

Create a super graph G’
1. Add a super-source vertex s
2. For each vertex v with demand < 0 - add an edge from super-source to v with -demand (so will be positive)
3. Add a super-sink vertex t
4. For each vertex v with demand > 0 - add an edge from v to super-sink with demand

Solve the max-flow problem on G’ to obtain the maximum flow

Question 7

What are two other notes to consider when looking at Circulation of Demands problems?

Answer 7

• The sum of all demands must be 0 (as otherwise - globally there would be an oversupply and an undersupply)
• The flow of the of G’ cannot be greater than the demand
  § As the cut S = {s} has the capacity equal to D by construction

Question 8

What are the constraints on a circulation of demands problem with lower bounds?

Answer 8

• (Capacity) the flow along the edge must be between min and capacity
• (Demand) Inbound - outbound = demand for each vertex

Question 9

What is our approach when doing circulation of demands with lower bounds?

Answer 9

• Reduce this to a normal circulation of demands problem - with no lower bound
• Basically, we will shift the lower bound into the demands

Question 10

What is the solution to a circulation of demands with lower bounds problem?

Answer 10

○ First - shift the lower bond
§ Preload the flow with f’ = fedge - lower_bound
§ Then, capacity = capacity - lower_bound
○ Second - adjust the node demands to account
§ For each edge (u,v)
□ Demand(u) += lower
□ Demand (v) -= lower
○ Then solve as a normal circulation of demands problem